ConcurrentHashMap详解 jdk1.8源码分析

电玩女神 2021-11-29 09:44 349阅读 0赞

[HashMap源码详解分析，基于jdk1.8][HashMap_jdk1.8]

ConcurrentHashMap  jdk1.7简介和 jdk1.8源码分析

**目录**

一、ConcurrentHashMap，jdk1.7简介

1、ConcurrentHashMap产生背景

2、ConcurrentHashMap 1.7版本采用分段锁的简介：

3、put存元素操作时候

4、JDK1.7版本的ConcurrentHashMap简介到此，具体源码分析可参考贴：

二、ConcurrentHashMap源码，jdk1.8详解

1、1.8版本主要改变

2、基本属性常量和变量

3、对象中的基本结构对象信息:

（1）链表的Node对象

（2）、红黑树节点

（3）、包装TreeNode节点的TreeBin对象；

（4）、ForwardingNode对象

4、put，插入元素方法；

5、get()方法

6、扩容方法

7、size()方法，获取大小

--------------------

# 一、ConcurrentHashMap，jdk1.7简介 #

## 1、ConcurrentHashMap产生背景 ##

我们在前面已经介绍过HashMap  jdk1.8的源码分析；

为什么有了HashMap，我们还需要ConcurrentHashMap呢？

因为HashMap  在并发环境中不是线程安全的，有存取数据一致性的问题；

甚至，在多个线程，同时进行put操作的时候，链表存储过程中，，hash桶中的单链表可能形成环形结构，造成死循环，引起CPU100%，这是一段代码：

final HashMap<String, String> map = new HashMap<String, String>(2);
    for (int i = 0; i < 10000; i++) {
       new Thread(new Runnable() {
            @Override
            public void run() {
                map.put(UUID.randomUUID().toString(), "");
            }
        }).start();
    }

在ConcurrentHashMap之前，解决方案有Hashtable和

Collections.synchronizedMap(hashMap)，不过这两个方案基本上是对读写进行加锁操作，一个线程在读写元素，其余线程必须等待，性能极慢；

所以concurrent包的作者Doug Lea大师带来了ConcurrentHashMap；

## 2、ConcurrentHashMap 1.7版本采用分段锁的简介： ##

因为ConcurrentHashMap1.7和1.8版本的实现方式区别较大，这里我们可以先来简单看一下1.7中的实现方式，然后再看看1.8做了哪些改进;

在1.7中，主要是采用了分段锁的解决方案，分成很多个Segment，形成一个数组，我们可以把每一个Segment数组的元素，看成是一个小的Hashmap

； Segment \[\]数组，默认初始化大小16，但是Segment的数量初始化了,就不能修改；

每个Segment对象继承自ReentrantLock，代表一把锁；

所以说默认支持16个线程并发大小同时访问ConcurrentHashMap；

最小支持2个线程并发，最大支持1<<16(65536)个线程并发；

Segment 数组的大小ssize是由concurrentLevel来决定的，ssize一定是大于或等于concurrentLevel的最小的2的次幂；

例如concurrentLevel大小为14，那么Segment数组大小ssize是16；

每一个Segment数组元素里面又包含一个HashEntry\[\]数组，每个HashEntry是一个链表结构，当对HashEntry\[\]数组的数据进行修改时（如下图，在对HashEntryA和HashEntryB插入时，他们两个节点就竞争同一把锁，HashEntryD和HashEntryE他们竞争另外的一把锁），必须首先获得与它对应的Segment锁；这样，就形成了一个分段锁的控制；

每个Segment对象元素可以看做是一个小的hashMap，

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70][]

static final class Segment<K,V> extends ReentrantLock implements Serializable
    
    
    
    transient volatile HashEntry<K,V>[] table;

## 3、put存元素操作时候 ##

（1）、每一个Segment中进行put时，都会加锁先调用tryLock()方法获取锁，（2）、如果获取成功，则根据key的哈希值，计算put到哪个Segment上，

a、用hash值进行定位，hash值都是通过再hash后得到的（减少hash碰撞），

这里分为两步定位，首先是确定Segment，放在 Segment \[\]哪个index，如果定位Segment如果不存在，则创建；

b、其次是再确定放到Segment中的HashEntry数组中哪个index，

HashEntry长度cap同样也是2的N次方，默认情况，ssize = 16，initialCapacity = 16，loadFactor = 0.75f；

（3）、调用tryLock()方法获取锁，获取锁失败：失败调用scanAndLockForPut方法自旋获取锁,成功后也是接着往下执行；

## 4、JDK1.7版本的ConcurrentHashMap简介到此，具体源码分析可参考贴： ##

[https://blog.51cto.com/14220760/2364724][https_blog.51cto.com_14220760_2364724]

# 二、ConcurrentHashMap源码，jdk1.8详解 #

## 1、1.8版本主要改变 ##

在1.7版本，ConcurrentHashMap采用分段锁的概念，但是1.8已经改变了这种思路，取消了分段锁，底层采用数组+链表+红黑树的存储结构，使用CAS、Synchronized，volatile，final，lock-free等技术，将锁的级别控制在了更细粒度的table数组元素级别，也就是说只需要锁住这个链表的head节点，并不会影响其他的table元素的读写，好处在于并发的粒度更细，影响更小，从而并发效率更好；

## 2、基本属性常量和变量 ##

//最大容量
    private static final int MAXIMUM_CAPACITY = 1 << 30;
    
    //默认容量
    private static final int DEFAULT_CAPACITY = 16;
    //扩容因子
    private static final float LOAD_FACTOR = 0.75f;
    //数组槽的链表个数，转红黑树条件
    static final int TREEIFY_THRESHOLD = 8;
    //数组槽的红黑树反转链表条件
    static final int UNTREEIFY_THRESHOLD = 6;
    //转红黑树，数组最小容量
    static final int MIN_TREEIFY_CAPACITY = 64;
    //每个cpu强制处理的最小Map容量数
    private static final int MIN_TRANSFER_STRIDE = 16;
    
    //生成sizeCtl所使用的bit位数（还不大明白）
    private static int RESIZE_STAMP_BITS = 16;
    
    //参与扩容的最大线程数
    private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
    
    //移位量，把生成戳移位后保存在sizeCtl中当做扩容线程计数的基数，相反方//向移位后能够反解出生成戳（抄的）
    private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
    
    /*
     *sizeCtl：控制标识符，用来控制table初始化和扩容操作的，在不同的地方有不同的用途，其值也不同，所代表的含义也不同
    负数代表正在进行初始化或扩容操作
    -1代表正在初始化
    -N 表示有N-1个线程正在进行扩容操作
    正数或0代表hash表还没有被初始化，这个数值表示初始化或下一次进行扩容的大小
    重要内部类
     */
    static final int MOVED     = -1; // hash for forwarding nodes
    static final int TREEBIN   = -2; // hash for roots of trees
    static final int RESERVED  = -3; // hash for transient reservations
    static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
    
    // hash数组
    transient volatile Node<K,V>[] table;
    
    //扩容时新的hash数组，容量是以前的两倍 
    private transient volatile Node<K,V>[] nextTable;
    
    //用于节点计数
    private transient volatile long baseCount;
    
        //非常非常非常重要的一个参数，统御全局
        //sizeCtl = -1，表示有线程正在进行初始化操作，防止多线程同时初始化Map  
        //sizeCtl = -(1 + nThreads)，表示有nThreads个线程正在进行扩容操作  
        //sizeCtl > 0，表示接下来的初始化操作中的Map容量，或者表示初始化/ 扩容完成后的阈值
        //sizeCtl = 0，默认值
    private transient volatile int sizeCtl;
    
    //用以维护多线程扩容时候的线程安全
    private transient volatile int transferIndex;

## 3、对象中的基本结构对象信息: ##

数组节点、链表节点，key-value键值对。所有插入ConcurrentHashMap的中数据都将会包装在Node对象中，Node对象组成一个数组，并且在数组某个index上，如果有hash冲突的节点，都在这个index上构成节点的单向链表，这样构成了整个ConcurrentHashMap：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 1][]

### （1）链表的Node对象 ###

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V val;
        volatile Node<K,V> next;
      …
    
    }
    
    * 插入的时候，才初始化，大小必须是2的次幂
    
     */
    
    transient volatile Node<K,V>[] table;

### （2）、红黑树节点 ###

之前在介绍HashMap的时候就知道，如果链表的数据过长是会转换为红黑树来处理。这里也会，区别在于它并不是直接转换，而是将这些链表的节点包装成TreeNode放在TreeBin对象中，然后由TreeBin完成红黑树的转换。先来看TreeNode树节点类：

static final class TreeNode<K,V> extends Node<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // 删除节点的时候，会用到这个指向
        boolean red;
    
    …
    
    }

### （3）、包装TreeNode节点的TreeBin对象； ###

红黑树节点TreeNode实际上还保存有链表的指针，因此也可以用链表的方式进行遍历读取操作。TreeBin自身维护一个简单的读写锁，由于put/remove/replace方法在插入删除替换是会用synchronized锁住根结点，因此不用考虑写-写竞争的情况。只需解决读-写竞争的情况。

a、我们先来看对象类的基本信息

static final class TreeBin<K,V> extends Node<K,V> {
    
        //红黑树的根节点
        TreeNode<K,V> root;
    
        //链表头结点，TreeBin仍然保存了链表结构
        volatile TreeNode<K,V> first;
        //标记设置 WAITER 标识位的线程
    
         volatile Thread waiter;
    
        //锁状态标志位
        volatile int lockState;
        // values for lockState
    
        //写锁标志位
        static final int WRITER = 1; // set while holding write lock
    
        //等待锁标志位
        static final int WAITER = 2; // set when waiting for write lock
    
        //读锁标志位
        static final int READER = 4; // increment value for setting read lock

b、再来看Treebin中的构造方法，构造红黑树：

/**
     * Creates bin with initial set of nodes headed by b.
     */
    TreeBin(TreeNode<K,V> b) {
        super(TREEBIN, null, null, null);
        this.first = b;
        TreeNode<K,V> r = null;
    
        //遍历链表的节点，转为红黑树节点
        for (TreeNode<K,V> x = b, next; x != null; x = next) {
            next = (TreeNode<K,V>)x.next;
            x.left = x.right = null;
    
             //初始化根节点
            if (r == null) {
                x.parent = null;
                x.red = false;
                r = x;
            }
            else {
                K k = x.key;
                int h = x.hash;
                Class<?> kc = null;
                for (TreeNode<K,V> p = r;;) {
                    int dir, ph;
                    K pk = p.key;
    
                    //dir标志存放在左边还是右边
                    //hash值小，dir小于等于0时，存左子节点，反之右子节点
                    if ((ph = p.hash) > h)
                        dir = -1;
                    else if (ph < h)
                        dir = 1;
                    else if ((kc == null &&
                              (kc = comparableClassFor(k)) == null) ||
                             (dir = compareComparables(kc, k, pk)) == 0)
                        dir = tieBreakOrder(k, pk);
                        TreeNode<K,V> xp = p;
                    if ((p = (dir <= 0) ? p.left : p.right) == null) {
                        x.parent = xp;
                        if (dir <= 0)
                            xp.left = x;
                        else
                            xp.right = x;
    
                        //做平衡操作
                        r = balanceInsertion(r, x);
                        break;
                    }
                }
            }
        }
        this.root = r;
        assert checkInvariants(root);
      }
    
    …
    
    }

c、获取根节点写锁，重构树结构的时候会用到

/**
     * Acquires write lock for tree restructuring.
     */
    private final void lockRoot() {
    	//调用CAS更改锁状态标志位，将其置为WRITER，并调用contendedLock();
        if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
            contendedLock(); // offload to separate method
    }

d、释放写锁

/**
    
     * Releases write lock for tree restructuring.
    
     */
    
    private final void unlockRoot() {
    
        lockState = 0;
    
    }

e、写线程会调用该方法。由于不需要考虑写-写的情况（为什么不用考虑写-写的情况，一会儿在下面说明），因此只需要考虑读锁阻塞线程获取写锁

/**
     * Possibly blocks awaiting root lock.
     */
    private final void contendedLock() {
        boolean waiting = false;
    	//循环一直到拿到锁
        for (int s;;) {
    	//状态为0或者waiter时候，才可进入
            if (((s = lockState) & ~WAITER) == 0) {
    		//CAS替换锁状态为WRITER
                if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
    		//若当前线程注册过waiter状态，则清除，返回写锁
                    if (waiting)
                        waiter = null;
                    return;
                }
            }
    	//锁状态为非Waiter状态则进入
    	//由于不可能是写-写，所以锁状态这时候若为读状态
    	//即若锁状态有读状态时，且没有waiter状态，会进入该else if
            else if ((s & WAITER) == 0) {
    	//尝试占据 WAITER 状态标识位
                if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
    		//设置waiting标志位,设置waiter为当前线程
                    waiting = true;
                    waiter = Thread.currentThread();
                }
            }
    	//如果是waiting状态，线程park挂起
            else if (waiting)
                LockSupport.park(this);
        }
    }

f、查找树节点：在红黑树中查找"相等"的结点，有两种查找方式：

以链表的方式进行查找；

以红黑树的方式进行查找；

final Node<K,V> find(int h, Object k) {
        if (k != null) {
            for (Node<K,V> e = first; e != null; ) {
                int s; K ek;
                //当锁状态为等待或写的状态时，以链表的方式的方式查找结点
                //当为写状态的时候，读则采取遍历链表的方式，
                //这样虽然查找复杂度提高，但读写不阻塞
                //当为等待状态的时候，不继续加写锁，能让被阻塞的写线程尽快恢复运行，
                //或者刚好让某个写线程不被阻塞
                if (((s = lockState) & (WAITER|WRITER)) != 0) {
                    if (e.hash == h &&
                        ((ek = e.key) == k || (ek != null && k.equals(ek))))
                        return e;
                    e = e.next;
                }
                //否则，设置读锁状态
                else if (U.compareAndSwapInt(this, LOCKSTATE, s,
                                             s + READER)) {
                    TreeNode<K,V> r, p;
                    try {
                        //利用红黑树来查找，速度很快
                        p = ((r = root) == null ? null :
                             r.findTreeNode(h, k, null));
                    } finally {
                        Thread w;
                        //如果是最后一个读线程，并且有写线程因为读锁而阻塞，
                        //那么要通知它，告诉它可以尝试获取写锁了
                        if (U.getAndAddInt(this, LOCKSTATE, -READER)   
    			==
                            (READER|WAITER) && (w = waiter) != null)
                            LockSupport.unpark(w);
                    }
                    return p;
                }
            }
        }
        return null;
    }

g、插入红黑树节点：

final TreeNode<K,V> putTreeVal(int h, K k, V v) {
    
        Class<?> kc = null;
    
        boolean searched = false;
    
        for (TreeNode<K,V> p = root;;) {
    
            int dir, ph; K pk;
    
            if (p == null) {
    
                first = root = new TreeNode<K,V>(h, k, v, null, null);
    
                break;
    
            }
    
            else if ((ph = p.hash) > h)
    
                dir = -1;
    
            else if (ph < h)
    
                dir = 1;
    
            else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
    
                return p;
    
            else if ((kc == null &&
    
                      (kc = comparableClassFor(k)) == null) ||
    
                     (dir = compareComparables(kc, k, pk)) == 0) {
    
                if (!searched) {
    
                    TreeNode<K,V> q, ch;
    
                    searched = true;
    
                    if (((ch = p.left) != null &&
    
                         (q = ch.findTreeNode(h, k, kc)) != null) ||
    
                        ((ch = p.right) != null &&
    
                         (q = ch.findTreeNode(h, k, kc)) != null))
    
                        return q;
    
                }
    
                dir = tieBreakOrder(k, pk);
    
            }
    
    
    
            TreeNode<K,V> xp = p;
    
            if ((p = (dir <= 0) ? p.left : p.right) == null) {
    
                TreeNode<K,V> x, f = first;
    
                first = x = new TreeNode<K,V>(h, k, v, f, xp);
    
                if (f != null)
    
                    f.prev = x;
    
                if (dir <= 0)
    
                    xp.left = x;
    
                else
    
                    xp.right = x;
    
                if (!xp.red)
    
                    x.red = true;
    
                else {
    
                    lockRoot();
    
                    try {
    
                        root = balanceInsertion(root, x);
    
                    } finally {
    
                        unlockRoot();
    
                    }
    
                }
    
                break;
    
            }
    
        }
    
        assert checkInvariants(root);
    
        return null;
    
    }

这里要区分一个概念：红黑树的 读锁状态 和 写锁状态 是互斥的，但是从ConcurrentHashMap角度来说，读写操作实际上是不互斥的(get操作是无锁的)。

当有线程持有红黑树的 读锁 时，写线程可能会阻塞，不过因为红黑树的查找很快，写线程阻塞的时间很短 。而当有线程持有红黑树的 写锁 时，读线程不会以红黑树方式进行读取操作，而是使用简单的链表方式进行读取，此时读操作和写操作可以并发执行。

上文中的find函数和putTreeVal函数就是基本的读写操作。从注释中可以看出，find函数不会发生阻塞（利用遍历链表而不是红黑树，虽然提高了搜索时间复杂度，但避免了阻塞），而putTreeVal在插入时若红黑树需要进行平衡调整的情况下会调用lockRoot()，若此时又其他的读操作，则会发生读写阻塞；若红黑树插入后不需要调整则根本不会调用lockRoot()。

### （4）、ForwardingNode对象 ###

只在扩容时出现，实现了扩容时旧表和新表的连接

static final class ForwardingNode<K,V> extends Node<K,V> {
    
        final Node<K,V>[] nextTable;
    
        ForwardingNode(Node<K,V>[] tab) {
    
            super(MOVED, null, null, null);
    
            this.nextTable = tab;
    
        }
    ...
    }

## 4、put，插入元素方法； ##

ConcurrentHashMap最常用的就是put和get两个方法。现在来介绍put方法，这个put方法依然沿用HashMap的put方法的思想，根据hash值计算这个新插入的点在table中的位置i，如果i位置是空的，直接放进去，否则进行判断，如果i位置是树节点，按照树的方式插入新的节点，否则把i插入到链表的末尾。ConcurrentHashMap中依然沿用这个思想，有一个最重要的不同点就是ConcurrentHashMap不允许key或value为null值。另外由于涉及到并发，put方法要复杂一点。在多线程中可能有以下两个情况:

如果一个或多个线程正在对ConcurrentHashMap进行扩容操作，当前线程也要进入扩容的操作中。这个扩容的操作之所以能被检测到，是因为transfer方法中在空结点上插入forward节点，如果检测到需要插入的位置被forward节点占有，就帮助进行扩容；

如果检测到要插入的节点是非空且不是forward节点，就对这个节点加锁，这样就保证了线程安全。尽管这个有一些影响效率，但是还是会比hashTable的synchronized要好得多。

插入节点流程：对于每一个放入的值，首先利用spread方法对key的hashcode进行一次hash计算，由此来确定这个值在table中的位置。

如果这个位置是空的，那么直接放入，而且不需要加锁操作。

如果这个位置存在结点，说明发生了hash碰撞，首先判断这个节点的类型。如果是链表节点（fh>0）,则得到的结点就是hash值相同的节点组成的链表的头节点。需要依次向后遍历确定这个新加入的值所在位置。如果遇到hash值与key值都与新加入节点是一致的情况，则只需要更新value值即可。否则依次向后遍历，直到链表尾插入这个结点。  如果加入这个节点以后链表长度大于数8，就把这个链表转换成红黑树。如果这个节点的类型已经是树节点的话，直接调用树节点的插入方法进行插入新的值：

public V put(K key, V value) {
        return putVal(key, value, false);
    }
    
    /** Implementation for put and putIfAbsent */
    final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        int hash = spread(key.hashCode());
        int binCount = 0;
    	//一直循环到插入成功
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;
    	    //初始化时
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
    	    //计算在数组中下标
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
    	        //如果该节点没有元素，直接cas放进去
                if (casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null)))
                    break;
            }
    		//如果头结点hash值为-1，则为ForwardingNode结点，说明在扩容
            //调用hlepTransfer帮助扩容
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
    		// 锁住hash数组槽的链表头节点，开始插入链表到尾部
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    //根据方法传入的onlyIfAbsent是否覆盖旧value值
                                    //key值相同时，onlyIfAbsent传入false，旧value被替换掉
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node<K,V>(hash,  
                                        key, value, null);
                                    break;
                                }
                            }
                        }
    			        //红黑树插入节点
                        else if (f instanceof TreeBin) {
                           Node<K,V> p;
                           binCount = 2;
                           if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                  value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
    	        //如果大于阈值，则转为红黑树
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }

## 5、get()方法 ##

首先定位到具体的hash槽，若hash槽不为空，判断第一个结点是否是要查找的结点（判断方法是先比较hash值，若相等则需要地址相等或者equals为true中的一个成立，则是要查找的结点），否则根据hash值是否为负数，将查找操作分派给相应的find函数。若是ForwardingNode，则用find函数转发到nextTable上查找；若是TreeBin结点，调用TreeBin的find函数，根据自身读写锁情况，去红黑树中查找。最后如果是普通结点，则遍历链表来寻找。

从代码上也可以看出，get操作是无锁的 。后文中即使TreeBin的find函数虽然有可能会加TreeBin的内部读锁，但也是非阻塞的。定位方法和HashMap基本一致

public V get(Object key) {
        Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    	//得到hash扰动后的值，必须是一个正数
    	//负数会代表其他节点
    	//-1是ForwardingNode，则用find函数转发到nextTable上查找
        //-2是TreeBin，调用TreeBin的find函数。根据自身读写锁情况，
        //判断是用红黑树方式查找，还是用链表方式查找
        int h = spread(key.hashCode());
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (e = tabAt(tab, (n - 1) & h)) != null) {
            if ((eh = e.hash) == h) {
                if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                    return e.val;
            }
            else if (eh < 0)
                return (p = e.find(h, key)) != null ? p.val : null;
            while ((e = e.next) != null) {
                if (e.hash == h &&
                    ((ek = e.key) == key || (ek != null && key.equals(ek))))
                    return e.val;
            }
        }
        return null;
    }

## 6、扩容方法 ##

扩容方法分析，以下内容转自：[https://www.jianshu.com/p/2829fe36a8dd][https_www.jianshu.com_p_2829fe36a8dd]

构建一个nextTable，其大小为原来大小的两倍，这个步骤是在单线程环境下完成的；将原来table里面的内容复制到nextTable中，这个步骤是允许多线程操作的，所以性能得到提升；

（1）、通过计算 CPU 核心数和 Map 数组的长度得到每个线程（CPU）要帮助处理多少个桶，并且这里每个线程处理都是平均的。默认每个线程处理 16 个桶。因此，如果长度是 16 的时候，扩容的时候只会有一个线程扩容。

（2）、初始化临时变量 nextTable。将其在原有基础上扩容两倍。

（3）、死循环开始转移。多线程并发转移就是在这个死循环中，根据一个 finishing 变量来判断，该变量为 true 表示扩容结束，否则继续扩容。

a、进入一个 while 循环，分配数组中一个桶的区间给线程，默认是 16. 从大到小进行分配。当拿到分配值后，进行 i-- 递减。这个 i 就是数组下标。（其中有一个 bound 参数，这个参数指的是该线程此次可以处理的区间的最小下标，超过这个下标，就需要重新领取区间或者结束扩容，还有一个 advance 参数，该参数指的是是否继续递减转移下一个桶，如果为 true，表示可以继续向后推进，反之，说明还没有处理好当前桶，不能推进)

b、 出 while 循环，进 if 判断，判断扩容是否结束，如果扩容结束，清空临死变量，更新 table 变量，更新库容阈值。如果没完成，但已经无法领取区间（没了），该线程退出该方法，并将 sizeCtl 减一，表示扩容的线程少一个了。如果减完这个数以后，sizeCtl 回归了初始状态，表示没有线程再扩容了，该方法所有的线程扩容结束了。（这里主要是判断扩容任务是否结束，如果结束了就让线程退出该方法，并更新相关变量）。然后检查所有的桶，防止遗漏。

c、 如果没有完成任务，且 i 对应的槽位是空，尝试 CAS 插入占位符，让 putVal 方法的线程感知。

d、 如果 i 对应的槽位不是空，且有了占位符，那么该线程跳过这个槽位，处理下一个槽位。

e、 如果以上都是不是，说明这个槽位有一个实际的值。开始同步处理这个桶。

f、 到这里，都还没有对桶内数据进行转移，只是计算了下标和处理区间，然后一些完成状态判断。同时，如果对应下标内没有数据或已经被占位了，就跳过了。

（4）、处理每个桶的行为都是同步的。防止 putVal 的时候向链表插入数据。

a、如果这个桶是链表，那么就将这个链表根据 length 取于拆成两份，取于结果是 0 的放在新表的低位，取于结果是 1 放在新表的高位。

b、如果这个桶是红黑数，那么也拆成 2 份，方式和链表的方式一样，然后，判断拆分过的树的节点数量，如果数量小于等于 6，改造成链表。反之，继续使用红黑树结构。

c、 到这里，就完成了一个桶从旧表转移到新表的过程。

（5）、好，以上，就是 transfer 方法的总体逻辑。还是挺复杂的。再进行精简，分成以下步骤：

计算每个线程可以处理的桶区间。默认 16.

初始化临时变量 nextTable，扩容 2 倍。

死循环，计算下标。完成总体判断。

如果桶内有数据，同步转移数据。通常会像链表拆成 2 份。

（6）、源码分析

/**
    
     * Moves and/or copies the nodes in each bin to new table. See
    
     * above for explanation.
    
     *
    
     * transferIndex 表示转移时的下标，初始为扩容前的 length。
    
     *
    
     * 我们假设长度是 32
    
     */
    
    private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    
        int n = tab.length, stride;
    
        // 将 length / 8 然后除以 CPU核心数。如果得到的结果小于 16，那么就使用 16。
    
        // 这里的目的是让每个 CPU 处理的桶一样多，避免出现转移任务不均匀的现象，如果桶较少的话，默认一个 CPU（一个线程）处理 16 个桶
    
        if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
    
            stride = MIN_TRANSFER_STRIDE; // subdivide range 细分范围 stridea：TODO
    
        // 新的 table 尚未初始化
    
        if (nextTab == null) {            // initiating
    
            try {
    
                // 扩容  2 倍
    
                Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
    
                // 更新
    
                nextTab = nt;
    
            } catch (Throwable ex) {      // try to cope with OOME
    
                // 扩容失败， sizeCtl 使用 int 最大值。
    
                sizeCtl = Integer.MAX_VALUE;
    
                return;// 结束
    
            }
    
            // 更新成员变量
    
            nextTable = nextTab;
    
            // 更新转移下标，就是 老的 tab 的 length
    
            transferIndex = n;
    
        }
    
        // 新 tab 的 length
    
        int nextn = nextTab.length;
    
        // 创建一个 fwd 节点，用于占位。当别的线程发现这个槽位中是 fwd 类型的节点，则跳过这个节点。
    
        ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
    
        // 首次推进为 true，如果等于 true，说明需要再次推进一个下标（i--），反之，如果是 false，那么就不能推进下标，需要将当前的下标处理完毕才能继续推进
    
        boolean advance = true;
    
        // 完成状态，如果是 true，就结束此方法。
    
        boolean finishing = false; // to ensure sweep before committing nextTab
    
        // 死循环,i 表示下标，bound 表示当前线程可以处理的当前桶区间最小下标
    
        for (int i = 0, bound = 0;;) {
    
            Node<K,V> f; int fh;
    
            // 如果当前线程可以向后推进；这个循环就是控制 i 递减。同时，每个线程都会进入这里取得自己需要转移的桶的区间
    
            while (advance) {
    
                int nextIndex, nextBound;
    
                // 对 i 减一，判断是否大于等于 bound （正常情况下，如果大于 bound 不成立，说明该线程上次领取的任务已经完成了。那么，需要在下面继续领取任务）
    
                // 如果对 i 减一大于等于 bound（还需要继续做任务），或者完成了，修改推进状态为 false，不能推进了。任务成功后修改推进状态为 true。
    
                // 通常，第一次进入循环，i-- 这个判断会无法通过，从而走下面的 nextIndex 赋值操作（获取最新的转移下标）。其余情况都是：如果可以推进，将 i 减一，然后修改成不可推进。如果 i 对应的桶处理成功了，改成可以推进。
    
                if (--i >= bound || finishing)
    
                    advance = false;// 这里设置 false，是为了防止在没有成功处理一个桶的情况下却进行了推进
    
                // 这里的目的是：1. 当一个线程进入时，会选取最新的转移下标。2. 当一个线程处理完自己的区间时，如果还有剩余区间的没有别的线程处理。再次获取区间。
    
                else if ((nextIndex = transferIndex) <= 0) {
    
                    // 如果小于等于0，说明没有区间了 ，i 改成 -1，推进状态变成 false，不再推进，表示，扩容结束了，当前线程可以退出了
    
                    // 这个 -1 会在下面的 if 块里判断，从而进入完成状态判断
    
                    i = -1;
    
                    advance = false;// 这里设置 false，是为了防止在没有成功处理一个桶的情况下却进行了推进
    
                }// CAS 修改 transferIndex，即 length - 区间值，留下剩余的区间值供后面的线程使用
    
                else if (U.compareAndSwapInt
    
                         (this, TRANSFERINDEX, nextIndex,
    
                          nextBound = (nextIndex > stride ?
    
                                       nextIndex - stride : 0))) {
    
                    bound = nextBound;// 这个值就是当前线程可以处理的最小当前区间最小下标
    
                    i = nextIndex - 1; // 初次对i 赋值，这个就是当前线程可以处理的当前区间的最大下标
    
                    advance = false; // 这里设置 false，是为了防止在没有成功处理一个桶的情况下却进行了推进，这样对导致漏掉某个桶。下面的 if (tabAt(tab, i) == f) 判断会出现这样的情况。
    
                }
    
            }// 如果 i 小于0 （不在 tab 下标内，按照上面的判断，领取最后一段区间的线程扩容结束）
    
            //  如果 i >= tab.length(不知道为什么这么判断)
    
            //  如果 i + tab.length >= nextTable.length  （不知道为什么这么判断）
    
            if (i < 0 || i >= n || i + n >= nextn) {
    
                int sc;
    
                if (finishing) { // 如果完成了扩容
    
                    nextTable = null;// 删除成员变量
    
                    table = nextTab;// 更新 table
    
                    sizeCtl = (n << 1) - (n >>> 1); // 更新阈值
    
                    return;// 结束方法。
    
                }// 如果没完成
    
                if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {// 尝试将 sc -1. 表示这个线程结束帮助扩容了，将 sc 的低 16 位减一。
    
                    if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)// 如果 sc - 2 不等于标识符左移 16 位。如果他们相等了，说明没有线程在帮助他们扩容了。也就是说，扩容结束了。
    
                        return;// 不相等，说明没结束，当前线程结束方法。
    
                    finishing = advance = true;// 如果相等，扩容结束了，更新 finising 变量
    
                    i = n; // 再次循环检查一下整张表
    
                }
    
            }
    
            else if ((f = tabAt(tab, i)) == null) // 获取老 tab i 下标位置的变量，如果是 null，就使用 fwd 占位。
    
                advance = casTabAt(tab, i, null, fwd);// 如果成功写入 fwd 占位，再次推进一个下标
    
            else if ((fh = f.hash) == MOVED)// 如果不是 null 且 hash 值是 MOVED。
    
                advance = true; // already processed // 说明别的线程已经处理过了，再次推进一个下标
    
            else {// 到这里，说明这个位置有实际值了，且不是占位符。对这个节点上锁。为什么上锁，防止 putVal 的时候向链表插入数据
    
                synchronized (f) {
    
                    // 判断 i 下标处的桶节点是否和 f 相同
    
                    if (tabAt(tab, i) == f) {
    
                        Node<K,V> ln, hn;// low, height 高位桶，低位桶
    
                        // 如果 f 的 hash 值大于 0 。TreeBin 的 hash 是 -2
    
                        if (fh >= 0) {
    
                            // 对老长度进行与运算（第一个操作数的的第n位于第二个操作数的第n位如果都是1，那么结果的第n为也为1，否则为0）
    
                            // 由于 Map 的长度都是 2 的次方（000001000 这类的数字），那么取于 length 只有 2 种结果，一种是 0，一种是1
    
                            //  如果是结果是0 ，Doug Lea 将其放在低位，反之放在高位，目的是将链表重新 hash，放到对应的位置上，让新的取于算法能够击中他。
    
                            int runBit = fh & n;
    
                            Node<K,V> lastRun = f; // 尾节点，且和头节点的 hash 值取于不相等
    
                            // 遍历这个桶
    
                            for (Node<K,V> p = f.next; p != null; p = p.next) {
    
                                // 取于桶中每个节点的 hash 值
    
                                int b = p.hash & n;
    
                                // 如果节点的 hash 值和首节点的 hash 值取于结果不同
    
                                if (b != runBit) {
    
                                    runBit = b; // 更新 runBit，用于下面判断 lastRun 该赋值给 ln 还是 hn。
    
                                    lastRun = p; // 这个 lastRun 保证后面的节点与自己的取于值相同，避免后面没有必要的循环
    
                                }
    
                            }
    
                            if (runBit == 0) {// 如果最后更新的 runBit 是 0 ，设置低位节点
    
                                ln = lastRun;
    
                                hn = null;
    
                            }
    
                            else {
    
                                hn = lastRun; // 如果最后更新的 runBit 是 1， 设置高位节点
    
                                ln = null;
    
                            }// 再次循环，生成两个链表，lastRun 作为停止条件，这样就是避免无谓的循环（lastRun 后面都是相同的取于结果）
    
                            for (Node<K,V> p = f; p != lastRun; p = p.next) {
    
                                int ph = p.hash; K pk = p.key; V pv = p.val;
    
                                // 如果与运算结果是 0，那么就还在低位
    
                                if ((ph & n) == 0) // 如果是0 ，那么创建低位节点
    
                                    ln = new Node<K,V>(ph, pk, pv, ln);
    
                                else // 1 则创建高位
    
                                    hn = new Node<K,V>(ph, pk, pv, hn);
    
                            }
    
                            // 其实这里类似 hashMap
    
                            // 设置低位链表放在新链表的 i
    
                            setTabAt(nextTab, i, ln);
    
                            // 设置高位链表，在原有长度上加 n
    
                            setTabAt(nextTab, i + n, hn);
    
                            // 将旧的链表设置成占位符
    
                            setTabAt(tab, i, fwd);
    
                            // 继续向后推进
    
                            advance = true;
    
                        }// 如果是红黑树
    
                        else if (f instanceof TreeBin) {
    
                            TreeBin<K,V> t = (TreeBin<K,V>)f;
    
                            TreeNode<K,V> lo = null, loTail = null;
    
                            TreeNode<K,V> hi = null, hiTail = null;
    
                            int lc = 0, hc = 0;
    
                            // 遍历
    
                            for (Node<K,V> e = t.first; e != null; e = e.next) {
    
                                int h = e.hash;
    
                                TreeNode<K,V> p = new TreeNode<K,V>
    
                                    (h, e.key, e.val, null, null);
    
                                // 和链表相同的判断，与运算 == 0 的放在低位
    
                                if ((h & n) == 0) {
    
                                    if ((p.prev = loTail) == null)
    
                                        lo = p;
    
                                    else
    
                                        loTail.next = p;
    
                                    loTail = p;
    
                                    ++lc;
    
                                } // 不是 0 的放在高位
    
                                else {
    
                                    if ((p.prev = hiTail) == null)
    
                                        hi = p;
    
                                    else
    
                                        hiTail.next = p;
    
                                    hiTail = p;
    
                                    ++hc;
    
                                }
    
                            }
    
                            // 如果树的节点数小于等于 6，那么转成链表，反之，创建一个新的树
    
                            ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
    
                                (hc != 0) ? new TreeBin<K,V>(lo) : t;
    
                            hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
    
                                (lc != 0) ? new TreeBin<K,V>(hi) : t;
    
                            // 低位树
    
                            setTabAt(nextTab, i, ln);
    
                            // 高位数
    
                            setTabAt(nextTab, i + n, hn);
    
                            // 旧的设置成占位符
    
                            setTabAt(tab, i, fwd);
    
                            // 继续向后推进
    
                            advance = true;
    
                        }
    
                    }
    
                }
    
            }
    
        }
    
    }

## 7、size()方法，获取大小 ##

public int size() {
        long n = sumCount();
        return ((n < 0L) ? 0 :
                (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
                (int)n);
    }
    final long sumCount() {
        CounterCell[] as = counterCells; CounterCell a;
        long sum = baseCount;
        if (as != null) {
            for (int i = 0; i < as.length; ++i) {
                if ((a = as[i]) != null)
                    sum += a.value;
            }
        }
        return sum;
    }

参考贴：[http://www.jinrongtong5.com/article/47][http_www.jinrongtong5.com_article_47]

[https://www.cnblogs.com/zerotomax/p/8687425.html\#go4][https_www.cnblogs.com_zerotomax_p_8687425.html_go4]

[HashMap_jdk1.8]: https://blog.csdn.net/lejustdoit/article/details/95776023
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70]: /images/20211129/f987c8f8d6e84bae89faffce78e1cbe3.png
[https_blog.51cto.com_14220760_2364724]: https://blog.51cto.com/14220760/2364724
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlanVzdGRvaXQ_size_16_color_FFFFFF_t_70 1]: /images/20211129/9ed7ce607fd94ca993f99de3e0ddb8fd.png
[https_www.jianshu.com_p_2829fe36a8dd]: https://www.jianshu.com/p/2829fe36a8dd
[http_www.jinrongtong5.com_article_47]: http://www.jinrongtong5.com/article/47
[https_www.cnblogs.com_zerotomax_p_8687425.html_go4]: https://www.cnblogs.com/zerotomax/p/8687425.html#go4