concurrentHashMap and Hashtable简单总结

参考 ： 探索 ConcurrentHashMap 高并发性的实现机制

 

这两个类都是线程安全的，但是 Hashtable 是通过给每一个方法加锁，（synchronized） ,这样每次操作都会锁住整个表！

   看源码 ：

     

public synchronized V get(Object key) {
        Entry tab[] = table;
        int hash = hash(key);
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return e.value;
            }
        }
        return null;
    }

 

    而 concurretHashMap ,同样它也要加锁，但是它并不是这么霸道，每次不会把整个表都会给锁住！而是只锁住一部分！那么，它是怎么做到的了？

     ConcurrentHashMap 类中包含两个静态内部类 HashEntry 和 Segment。HashEntry 用来封装映射表的键 / 值对；Segment 用来充当锁的角色，每个 Segment 对象守护整个散列映射表的若干个桶。每  个桶是由若干个 HashEntry 对象链接起来的链表。一个 ConcurrentHashMap 实例中包含由若干个 Segment 对象组成的数组。

     HashEntry :

    

static final class HashEntry<K,V> { 
        final K key;                       // 声明 key 为 final 型 ，他们是线程安全的
        final int hash;                   // 声明 hash 值为 final 型 
        volatile V value;                 // volatile ，对所有线程都是可见的
        final HashEntry<K,V> next;      // 声明 next 为 final 型 

        HashEntry(K key, int hash, HashEntry<K,V> next, V value) { 
            this.key = key; 
            this.hash = hash; 
            this.next = next; 
            this.value = value; 
        } 
 }

   Segment类 ：如果键能均匀散列，每个 Segment 大约守护整个散列表中桶总数的 1/16。

static final class Segment<K,V> extends ReentrantLock implements Serializable { 
        /** 
         * 在本 segment 范围内，包含的 HashEntry 元素的个数
         * 该变量被声明为 volatile 型
         */ 
        transient volatile int count; 

        /** 
         * table 被更新的次数
         */ 
        transient int modCount; 

        /** 
         * 当 table 中包含的 HashEntry 元素的个数超过本变量值时，触发 table 的再散列
         */ 
        transient int threshold; 

        /** 
         * table 是由 HashEntry 对象组成的数组
         * 如果散列时发生碰撞，碰撞的 HashEntry 对象就以链表的形式链接成一个链表
         * table 数组的数组成员代表散列映射表的一个桶
         * 每个 table 守护整个 ConcurrentHashMap 包含桶总数的一部分
         * 如果并发级别为 16，table 则守护 ConcurrentHashMap 包含的桶总数的 1/16 
         */ 
        transient volatile HashEntry<K,V>[] table; 

        /** 
         * 装载因子
         */ 
        final float loadFactor; 

        Segment(int initialCapacity, float lf) { 
            loadFactor = lf; 
            setTable(HashEntry.<K,V>newArray(initialCapacity)); 
        } 

        /** 
         * 设置 table 引用到这个新生成的 HashEntry 数组
         * 只能在持有锁或构造函数中调用本方法
         */ 
        void setTable(HashEntry<K,V>[] newTable) { 
            // 计算临界阀值为新数组的长度与装载因子的乘积
            threshold = (int)(newTable.length * loadFactor); 
            table = newTable; 
        } 

        /** 
         * 根据 key 的散列值，找到 table 中对应的那个桶（table 数组的某个数组成员）
         */ 
        HashEntry<K,V> getFirst(int hash) { 
            HashEntry<K,V>[] tab = table; 
            // 把散列值与 table 数组长度减 1 的值相“与”，
 // 得到散列值对应的 table 数组的下标
            // 然后返回 table 数组中此下标对应的 HashEntry 元素
            return tab[hash & (tab.length - 1)]; 
        } 
 }

    concurrentHashMap的结构示意图：

       

    在 ConcurrentHashMap 中，线程对映射表做读操作时，一般情况下不需要加锁就可以完成，因为hashEntry的value是volatile的！一定读到的是最新的值！

    对容器做结构性修改的操作才需要加锁，像put(),看下面的源码就知道，它锁住的不是整个表，而是这个segment，同样，这个map包含一个segment数组，

    访问其他的segment的线程还是可以并发的访问的！

    

public V put(K key, V value) { 
        if (value == null)          //ConcurrentHashMap 中不允许用 null 作为映射值
            throw new NullPointerException(); 
        int hash = hash(key.hashCode());        // 计算键对应的散列码
        // 根据散列码找到对应的 Segment 
        return segmentFor(hash).put(key, hash, value, false); 
 }

 

   总结 ：

  

ConcurrentHashMap 的高并发性主要来自于三个方面：

1. 用分离锁实现多个线程间的更深层次的共享访问。
2. 用 HashEntery 对象的不变性(final)来降低执行读操作的线程在遍历链表期间对加锁的需求。
3. 通过对同一个 Volatile 变量的写 / 读访问，协调不同线程间读 / 写操作的内存可见性。

使用分离锁，减小了请求 同一个锁的频率。

通过 HashEntery 对象的不变性及对同一个 Volatile 变量的读 / 写来协调内存可见性，使得 读操作大多数时候不需要加锁就能成功获取到需要的值。由于散列映射表在实际应用中大多数操作都是成功的 读操作，所以 2 和 3 既可以减少请求同一个锁的频率，也可以有效减少持有锁的时间。

通过减小请求同一个锁的频率和尽量减少持有锁的时间 ，使得 ConcurrentHashMap 的并发性相对于 HashTable 和用同步包装器包装的 HashMap有了质的提高。