ConcurrentHashMap源码解析（2）

    /**
     * 创建ConcurrentHashMap
     */
    public ConcurrentHashMap() {
        this(DEFAULT_INITIAL_CAPACITY, // 16
                DEFAULT_LOAD_FACTOR, // 0.75f
                DEFAULT_CONCURRENCY_LEVEL);// 16
    }

    /**
     * 将key-value放入map
     * 注意：key和value都不可以为空
     * 步骤：
     * 1)计算key.hashCode()的hash值
     * 2)根据hash值定位到某个Segment
     * 3)调用Segment的put()方法
     * Segment的put()方法:
     * 1)上锁
     * 2)从主内存中读取key-value对个数count
     * 3)count+1如果大于threshold，执行rehash()
     * 4)计算将要插入的HashEntry[]的下标index
     * 5)获取HashEntry的头节点HashEntry[index]-->first
     * 6)从头结点开始遍历整个HashEntry链表，
     * 6.1)若找到与key和hash相同的节点，则判断onlyIfAbsent如果为false，新值覆盖旧值，返回旧值；如果为true，则直接返回旧值（相当于不添加重复key的元素）
     * 6.2)若没有找到与key和hash相同的节点，则创建新节点HashEntry，并将之前的有节点作为新节点的next，即将新节点放入链头，然后将新节点赋值给HashEntry[index],将count强制写入主内存，最后返回null
     */
    public V put(K key, V value) {
        if (key == null || value == null)
            throw new NullPointerException();
        int hash = hash(key.hashCode());//计算key.hashCode()的hash值
        /**
         * 根据hash值定位到某个Segment，调用Segment的put()方法
         */
        return segmentFor(hash).put(key, hash, value, false);
    }

        /**
         * 往当前segment中添加key-value
         * 注意：
         * 1)onlyIfAbsent-->false如果有旧值存在,新值覆盖旧值,返回旧值；true如果有旧值存在,则直接返回旧值,相当于不添加元素(不可添加重复key的元素)
         * 2)ReentrantLock的用法
         * 3)volatile只能配合锁去使用才能实现原子性
         */
        V put(K key, int hash, V value, boolean onlyIfAbsent) {
            lock();//加锁：ReentrantLock
            try {
                int c = count;//当前Segment中的key-value对（注意：由于count是volatile型的，所以读的时候工作内存会从主内存重新加载count值）
                if (c++ > threshold) // 需要扩容
                    rehash();//扩容
                
                HashEntry<K, V>[] tab = table;
                int index = hash & (tab.length - 1);//按位与获取数组下标：与HashMap相同
                HashEntry<K, V> first = tab[index];//获取相应的HashEntry[i]中的头节点
                HashEntry<K, V> e = first;
                //一直遍历到与插入节点的hash和key相同的节点e；若没有，最后e==null
                while (e != null && (e.hash != hash || !key.equals(e.key)))
                    e = e.next;

                V oldValue;//旧值
                if (e != null) {//table中已经有与将要插入节点相同hash和key的节点
                    oldValue = e.value;//获取旧值
                    if (!onlyIfAbsent)
                        e.value = value;//false 覆盖旧值  true的话，就不添加元素了
                } else {//table中没有与将要插入节点相同hash或key的节点
                    oldValue = null;
                    ++modCount;
                    tab[index] = new HashEntry<K, V>(key, hash, first, value);//将头节点作为新节点的next，所以新加入的元素也是添加在链头
                    count = c; //设置key-value对（注意：由于count是volatile型的，所以写的时候工作内存会立即向主内存重新写入count值）
                }
                return oldValue;
            } finally {
                unlock();//手工释放锁
            }
        }

    /**
     * 对key.hashCode()进行hash计算
     * @param h key.hashCode()
     */
    private static int hash(int h) {
        // Spread bits to regularize both segment and index locations,
        // using variant of single-word Wang/Jenkins hash.
        h += (h << 15) ^ 0xffffcd7d;
        h ^= (h >>> 10);
        h += (h << 3);
        h ^= (h >>> 6);
        h += (h << 2) + (h << 14);
        return h ^ (h >>> 16);
    }

    /**
     * 根据给定的key的hash值定位到一个Segment
     * @param hash
     */
    final Segment<K, V> segmentFor(int hash) {
        return segments[(hash >>> segmentShift) & segmentMask];
    }

        /**
         * 步骤：
         * 需要注意的是：同一个桶下边的HashEntry链表中的每一个元素的hash值不一定相同，只是hash&(table.length-1)的结果相同
         * 1)创建一个新的HashEntry数组，容量为旧数组的二倍
         * 2)计算新的threshold
         * 3)遍历旧数组的每一个元素，对于每一个元素
         * 3.1)根据头节点e重新计算将要存入的新数组的索引idx
         * 3.2)若整个链表只有一个节点e，则是直接将e赋给newTable[idx]即可
         * 3.3)若整个链表还有其他节点，先算出最后一个节点lastRun的位置lastIdx，并将最后一个节点赋值给newTable[lastIdx]
         * 3.4)最后将从头节点开始到最后一个节点之前的所有节点计算其将要存储的索引k，然后创建新节点，将新节点赋给newTable[k]，并将之前newTable[k]上存在的节点作为新节点的下一节点
         */
        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]即可
                        newTable[idx] = e;
                    else {
                        // Reuse trailing consecutive sequence at same slot
                        HashEntry<K, V> lastRun = e;
                        int lastIdx = idx;//存放最后一个元素将要存储的数组索引
                        
                        //查找到最后一个元素，并设置相关信息
                        for (HashEntry<K, V> last = next; last != null; last = last.next) {
                            int k = last.hash & sizeMask;
                            if (k != lastIdx) {
                                lastIdx = k;
                                lastRun = last;
                            }
                        }
                        newTable[lastIdx] = lastRun;//存放最后一个元素

                        // Clone all remaining nodes
                        for (HashEntry<K, V> p = e; p != lastRun; p = p.next) {
                            int k = p.hash & sizeMask;
                            HashEntry<K, V> n = newTable[k];//获取newTable[k]已经存在的HashEntry，并将此HashEntry赋给n
                            //创建新节点，并将之前的n作为新节点的下一节点
                            newTable[k] = new HashEntry<K, V>(p.key, p.hash, n,p.value);
                        }
                    }
                }
            }
            table = newTable;
        }

        /**
         * 步骤：
         * 需要注意的是：同一个桶下边的HashEntry链表中的每一个元素的hash值不一定相同，只是hash&(table.length-1)的结果相同
         * 1)创建一个新的HashEntry数组，容量为旧数组的二倍
         * 2)计算新的threshold
         * 3)遍历旧数组的每一个元素，对于每一个元素（即一个链表）
         * 3.1)获取头节点e
         * 3.2)从头节点开始到最后一个节点（null之前的那个节点）的所有节点计算其将要存储的索引k，然后创建新节点，将新节点赋给newTable[k]，并将之前newTable[k]上存在的节点作为新节点的下一节点
         */
        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) {
                    for (HashEntry<K, V> p = e; p != null; p = p.next) {//遍历数组元素中的链表
                        int k = p.hash & sizeMask;
                        HashEntry<K, V> n = newTable[k];//获取newTable[k]已经存在的HashEntry，并将此HashEntry赋给n
                        //创建新节点，并将之前的n作为新节点的下一节点
                        newTable[k] = new HashEntry<K, V>(p.key, p.hash, n,p.value);
                    }
                }
            }
            table = newTable;
        }