java需要关注的知识点---ConcurrentHashMap

ConcurrentHashMap默认初始大小 16，临界值：12：基数：0.75
1.ConcurrentHashMap是一个线程安全的hashMap。相对hashMap多出以下一些特殊属性：

    //默认能够同时运行的线程数目
    static final int DEFAULT_CONCURRENCY_LEVEL = 16;
    //最大同时运行的线程数目
    static final int MAX_SEGMENTS = 1 << 16; // slightly conservative

2.ConcurrentHashMap的链表实例HashEntry：

 static final class HashEntry<K,V> {
        final K key;
        final int hash;
        volatile V value;
        final HashEntry<K,V> next;

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

	@SuppressWarnings("unchecked")
	static final <K,V> HashEntry<K,V>[] newArray(int i) {
	    return new HashEntry[i];
	}
    }

这里需要注意的是Value，value并不是final的，而是一个volatile.
volatile修饰符告诉编译程序不要对该变量所参与的操作进行某些优化。在两种特殊的情况下需要使用volatile修饰符：
第一种情况涉及到内存映射硬件(memory-mapped hardware，如图形适配器，这类设备对计算机来说就好象是内存的一部分一样)，
第二种情况涉及到共享内存(shared memory，即被两个以上同时运行的程序所使用的内存)。
    大多数计算机拥有一系列寄存器，其存取速度比计算机主存更快。好的编译程序能进行一种被称为“冗余装入和存储的删去”(redundant load and store removal)的优化，即编译程序会在程序中寻找并删去这样两类代码：一类是可以删去的从内存装入数据的指令，因为相应的数据已经被存放在寄存器中；另一种是可以删去的将数据存入内存的指令，因为相应的数据在再次被改变之前可以一直保留在寄存器中。
    如果一个指针变量指向普通内存以外的位置，如指向一个外围设备的内存映射端口，那么冗余装入和存储的优化对它来说可能是有害的。

ConcurrentHashMap不同于HashMap中的一点是，concurrentHashMap的put,get,remvoer等方法的实现都是由其内部类Segment实现的，该内部类：

static final class Segment<K,V> extends ReentrantLock implements Serializable {.....}

可以看出，该类实现了重入锁保证线程安全，使用final修饰保证方法不被篡改。


3.ConcurrentHashMap 中的 readValueUnderLock

 V readValueUnderLock(HashEntry<K,V> e) {
            lock();
            try {
                return e.value;
            } finally {
                unlock();
            }
        }

该代码是在值为空的情况才调用；该方法在锁定的情况下获取值。由该方法的注释可以得知,这样做是为了防止在编译器重新定制一个指定的HashEntry实例初始化时，在内存模型中发生意外。

  /**
         * Reads value field of an entry under lock. Called if value
         * field ever appears to be null. This is possible only if a
         * compiler happens to reorder a HashEntry initialization with
         * its table assignment, which is legal under memory model
         * but is not known to ever occur.
         */

3.ConcurrentHashMa中的put方法：

   public V put(K key, V value) {
        if (value == null)
            throw new NullPointerException();
        int hash = hash(key.hashCode());
        return segmentFor(hash).put(key, hash, value, false);
    }

不允许null的键
可以看出，ConcurrentHashMap和HashMap在对待null键的情况下截然不同，HashMap专门开辟了一块空间用于存储null键的情况，而ConcurrentHashMap则直接抛出空值针异常。
4.ConcurrentHashMa中segment的put方法：

V put(K key, int hash, V value, boolean onlyIfAbsent) {
            lock();
            try {
                int c = count;
                if (c++ > threshold) // ensure capacity
                    rehash();
                HashEntry<K,V>[] tab = table;
                int index = hash & (tab.length - 1);
                HashEntry<K,V> first = tab[index];
                HashEntry<K,V> e = first;
                while (e != null && (e.hash != hash || !key.equals(e.key)))
                    e = e.next;

                V oldValue;
                if (e != null) {
                    oldValue = e.value;
                    if (!onlyIfAbsent)
                        e.value = value;
                }
                else {
                    oldValue = null;
                    ++modCount;
                    tab[index] = new HashEntry<K,V>(key, hash, first, value);
                    count = c; // write-volatile
                }
                return oldValue;
            } finally {
                unlock();
            }

从该方法可以看出，根据key的hash值，计算到table下标位置之后，获取该下标位置的Entry链表，然后从链表第一个位置开始向后遍历，分别比对entry的hash值和key的值，如果都相等且entry不为空，则获取 该entry，设置该entry的value为传入的value，否则往后遍历直到链表中最后一个位置,直到找到相匹配的key和hash；如果e为空，则往该index下插入一个新的entry链表。
该方法使用了重入锁用以保证在同步时候线程的安全。

5.ConcurrentHashMa中segment的rehash方法(当前数组容量不够，进行扩充的操作)：

 void rehash() {
            HashEntry<K,V>[] oldTable = table;
            int oldCapacity = oldTable.length;
            //如果数组的长度大于或等于临界值，数组不再进行扩容。
            if (oldCapacity >= MAXIMUM_CAPACITY)
                return;  
            //扩充数组容量为原来大小的两倍。
            HashEntry<K,V>[] newTable = HashEntry.newArray(oldCapacity<<1);
            //重新计算临界值
            threshold = (int)(newTable.length * loadFactor);
            
            int sizeMask = newTable.length - 1;
            for (int i = 0; i < oldCapacity ; i++) {
                // We need to guarantee that any existing reads of old Map can
                //  proceed. So we cannot yet null out each bin.
                HashEntry<K,V> e = oldTable[i];

                if (e != null) {
                    HashEntry<K,V> next = e.next;
                    //获取该链表在数组新的下标
                    int idx = e.hash & sizeMask;

                    //该链表不存在后续节点，直接把该链表存入新数组，无需其他操作
                    if (next == null)
                        newTable[idx] = e;

                    else {
                        // 存在后续节点，使用临时变量存储该链表，假设当前节点是最后节点。
                        HashEntry<K,V> lastRun = e;
                        //获取下标
                        int lastIdx = idx;
                        //遍历该链表的后续节点
                        for (HashEntry<K,V> last = next;
                             last != null;
                             last = last.next) {
                            //获取后一个节点的index
                            int k = last.hash & sizeMask;
                            //如果后一个节点的index值和前一个不相同,
                            //则使用后节点的index覆盖前一个节点并且设置该节点为最后节点，依次
                            //做相同的操作，直到链表的最后一个节点。
                            if (k != lastIdx) {
                                lastIdx = k;
                                lastRun = last;
                            }
                        }                       
                      //把链表最后节点的值传递给数组
                      //该数组下标为最后获取到的下标
                      newTable[lastIdx] = lastRun;

                        // 遍历老数组下得到的链表的节点值，复制到新的扩容后的数组中。
                        for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {                   
                            //计算链表在新数组的下标
                            int k = p.hash & sizeMask;
                            //获取数组k下标的链表值。
                            HashEntry<K,V> n = newTable[k];
                            //把获取到的链表作为需要插入的新的entry的后续节点。
                            newTable[k] = new HashEntry<K,V>(p.key, p.hash,
                                                             n, p.value);
                        }
                    }
                }
            }
            //把扩容后的数组返回
            table = newTable;
        }

该方法的描述见代码注释
6.ConcurrentHashMap中的remove方法：

  public V remove(Object key) {
	int hash = hash(key.hashCode());
        return segmentFor(hash).remove(key, hash, null);
    }

7.ConcurrentHashMa中segment的remove方法:

 V remove(Object key, int hash, Object value) {
            lock();
            try {
                int c = count - 1;
                HashEntry<K,V>[] tab = table;
                int index = hash & (tab.length - 1);
                HashEntry<K,V> first = tab[index];
                HashEntry<K,V> e = first;
                while (e != null && (e.hash != hash || !key.equals(e.key)))
                    e = e.next;

                V oldValue = null;
                if (e != null) {
                    V v = e.value;
                    if (value == null || value.equals(v)) {
                        oldValue = v;
                        // All entries following removed node can stay
                        // in list, but all preceding ones need to be
                        // cloned.
                        ++modCount;
                        HashEntry<K,V> newFirst = e.next;
                        for (HashEntry<K,V> p = first; p != e; p = p.next)
                            newFirst = new HashEntry<K,V>(p.key, p.hash,
                                                          newFirst, p.value);
                        tab[index] = newFirst;
                        count = c; // write-volatile
                    }
                }
                return oldValue;
            } finally {
                unlock();
            }
        }

类似于put方法，remove方法也使用了重入锁来保证线程安全；concurrentHashMap的remove方法不同于HashMap的remove方法，在需要删除元素的index下的entry链表没有后续节点时候；后者的remove方法自己会负责回收删除元素的内存并且会移动删除元素后面的元素来覆盖删除元素的位置，concurrentHashMap的remove方法只会回收内存却不会和HashMap一样移动元素。