浅谈HashMap，LinkedHashMap，ConcurrentHashMap、synchronizedMap（三.ConcurrentHashMap）

我会带着你远行 2022-05-28 14:10 184阅读 0赞

我们前面说过了为什么要有HashMap，以及有序的HashMap——LinkedHashMap，那么我们随着深入，就想到了线程安全问题，可以看到，不论是HashMap还是LinkedHashMap源码中都没有锁的实现。那么也就是说HashMap以及LinkedHashMap都不是线程安全的。那么有没有线程安全的Map呢？当然有，那就是ConcurrentHashMap以及synchronizedMap，还要已经废弃的HashTable。

## Hashtable为什么废弃 ##

HashTable使用synchronized来保证线程安全，但在线程竞争激烈的情况下HashTable的**效率**非常低下。因为当一个线程访问HashTable的同步方法时，其他线程访问HashTable的同步方法时，可能会进入阻塞或轮询状态。如线程1使用put进行添加元素，线程2不但不能使用put方法添加元素，并且也不能使用get方法来获取元素，所以竞争越激烈效率越低。但是如果将数据一段一段锁起来，每把锁对应一段数据，那是不是就可以解决这个问题。

## ConcurrentHashMap ##

### 实现线程安全方式 ###

因为ConcurrentHashMap最重要的地方是实现线程安全。我们先看一下他是如何实现线程安全的。再1.7和1.8中，ConcurrentHashMap做了很大的改变。在1.7中ConcurrentHashMap使用了分段锁，1.8中则使用了CAS算法。

#### JDK1.7—分段锁 ####

分段锁不说太多，只是介绍其产生原因以及结构。  
HashTable容器在竞争激烈的并发环境下表现出效率低下的原因，是因为所有访问HashTable的线程都必须竞争同一把锁，那假如容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率，这就是ConcurrentHashMap所使用的锁分段技术，首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。  
ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment是一种可重入锁ReentrantLock，在ConcurrentHashMap里扮演锁的角色，HashEntry则用于存储键值对数据。一个ConcurrentHashMap里包含一个Segment数组，Segment的结构和HashMap类似，是一种数组和链表结构， 一个Segment里包含一个HashEntry数组，每个HashEntry是一个链表结构的元素， 每个Segment守护者一个HashEntry数组里的元素,当对HashEntry数组的数据进行修改时，必须首先获得它对应的Segment锁。  
![分段锁结构][70]

### JDK1.8—CAS算法 ###

CAS（Compare and Swap）：比较并交换算法。  
我们通过名字也可以猜到，CAS算法有两步，第一步是比较，第二步是交换。  
所以CAS原理：  
***CAS有3个操作数，内存值V，旧的预期值A，要修改的新值B。当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做。***  
CAS这里也不做具体解释，太多了。会单用一篇文章解释。

### 属性 ###

我现在的能力只能了解部分代码的含义，剩下的以后再解释吧。

/** * 最大容量 */
        private static final int MAXIMUM_CAPACITY = 1 << 30;
    
        /** * 初始化大小 */
        private static final int DEFAULT_CAPACITY = 16;
    
        /** * The largest possible (non-power of two) array size. * Needed by toArray and related methods. * 最大可能（不是二的次方）数组大小。需要用toArray 和related 方法。 */
        static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
        /** * The default concurrency level for this table. Unused but * defined for compatibility with previous versions of this class. * 此表的默认并发级别。未使用的，但定义为与该类以前版本兼容。 */
        private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
    
        /** * 默认加载因子大小 */
        private static final float LOAD_FACTOR = 0.75f;
    
        /** * 所以当链表长度大于8的时候，链表将会转换为红黑树，加快查询速度 */
        static final int TREEIFY_THRESHOLD = 8;
    
        /** * 当链表长度小于6的时候，红黑树将会转换为链表。 */
        static final int UNTREEIFY_THRESHOLD = 6;
    
        /** * The smallest table capacity for which bins may be treeified. * (Otherwise the table is resized if too many nodes in a bin.) * The value should be at least 4 * TREEIFY_THRESHOLD to avoid * conflicts between resizing and treeification thresholds. */
        static final int MIN_TREEIFY_CAPACITY = 64;
    
        /** * Minimum number of rebinnings per transfer step. Ranges are * subdivided to allow multiple resizer threads. This value * serves as a lower bound to avoid resizers encountering * excessive memory contention. The value should be at least * DEFAULT_CAPACITY. */
        private static final int MIN_TRANSFER_STRIDE = 16;
    
        /** * The number of bits used for generation stamp in sizeCtl. * Must be at least 6 for 32bit arrays. */
        private static int RESIZE_STAMP_BITS = 16;
    
        /** * The maximum number of threads that can help resize. * Must fit in 32 - RESIZE_STAMP_BITS bits. */
        private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
    
        /** * The bit shift for recording size stamp in sizeCtl. */
        private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
    
        /* * Encodings for Node hash fields. See above for explanation. */
        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
    
        /** Number of CPUS, to place bounds on some sizings */
        static final int NCPU = Runtime.getRuntime().availableProcessors();
    
        /** For serialization compatibility. */
        private static final ObjectStreamField[] serialPersistentFields = {
            new ObjectStreamField("segments", Segment[].class),
            new ObjectStreamField("segmentMask", Integer.TYPE),
            new ObjectStreamField("segmentShift", Integer.TYPE)
        };
    
        /** * The array of bins. Lazily initialized upon first insertion. * Size is always a power of two. Accessed directly by iterators. */
        transient volatile Node<K,V>[] table;
    
        /** * The next table to use; non-null only while resizing. */
        private transient volatile Node<K,V>[] nextTable;
    
        /** * Base counter value, used mainly when there is no contention, * but also as a fallback during table initialization * races. Updated via CAS. */
        private transient volatile long baseCount;
    
        /** * 1.负数代表正在进行初始化或扩容操作 * 2.-N 表示有N-1个线程正在进行扩容操作 * 3.正数或0代表hash表还没有被初始化，这个数值表示初始化或下一次进行扩容的大小， * 这一点类似于扩容阈值的概念。还后面可以看到，它的值始终是当前ConcurrentHashMap容量的0.75倍，这与loadfactor是对应的。 */
        private transient volatile int sizeCtl;
    
        /** * The next table index (plus one) to split while resizing. */
        private transient volatile int transferIndex;
    
        /** * Spinlock (locked via CAS) used when resizing and/or creating CounterCells. */
        private transient volatile int cellsBusy;
    
        /** * Table of counter cells. When non-null, size is a power of 2. */
        private transient volatile CounterCell[] counterCells;

### 构造方法 ###

/** * 创建一个空的默认大小（16）Map */
        public ConcurrentHashMap() {
        }
    
        /** * 创建一个指定大小的Map */
        public ConcurrentHashMap(int initialCapacity) {
            if (initialCapacity < 0)
                throw new IllegalArgumentException();
            int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
                       MAXIMUM_CAPACITY :
                       tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
            this.sizeCtl = cap;
        }
    
        /** * 新建一个哈希表，同时将另一个map m 里的所有元素加入表中。 */
        public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
            this.sizeCtl = DEFAULT_CAPACITY;
            putAll(m);
        }
    
        /** * 创建一个指定大小，指定加载因子的Map */
        public ConcurrentHashMap(int initialCapacity, float loadFactor) {
            this(initialCapacity, loadFactor, 1);
        }
    
        /** * 根据传入的大小，以及加载因子大小创建Map * concurrentLevel：在JDK1.8之前本质是ConcurrentHashMap分段锁总数， * 表示同时更新ConcurrentHashMap且不产生锁竞争的最大线程数； * 在JDK1.8中，仅在构造器中确保初始容量>=concurrentLevel，为兼容旧版本而保留； */
        public ConcurrentHashMap(int initialCapacity,
                                 float loadFactor, int concurrencyLevel) {
            if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
                throw new IllegalArgumentException();
            if (initialCapacity < concurrencyLevel)   // Use at least as many bins
                initialCapacity = concurrencyLevel;   // as estimated threads
            long size = (long)(1.0 + (long)initialCapacity / loadFactor);
            int cap = (size >= (long)MAXIMUM_CAPACITY) ?
                MAXIMUM_CAPACITY : tableSizeFor((int)size);
            this.sizeCtl = cap;
        }

### 内部类 ###

#### Node ####

Node是最核心的内部类，它包装了key-value键值对，所有插入ConcurrentHashMap的数据都包装在这里面。它与HashMap中的定义很相似，但是有一些差别它对value和next属性设置了volatile同步锁，它不允许调用setValue方法直接改变Node的value域，它增加了find方法辅助map.get()方法。

static class Node<K,V> implements Map.Entry<K,V> {
            final int hash;
            final K key;
            volatile V val;// volatile保证可见性
            volatile Node<K,V> next;
    
            Node(int hash, K key, V val, Node<K,V> next) {
                this.hash = hash;
                this.key = key;
                this.val = val;
                this.next = next;
            }
    
            public final K getKey()       { return key; }
            public final V getValue()     { return val; }
            public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
            public final String toString(){ return key + "=" + val; }
            /** * 并不提供set方法，报错。 */
            public final V setValue(V value) {
                throw new UnsupportedOperationException();
            }
    
            public final boolean equals(Object o) {
                Object k, v, u; Map.Entry<?,?> e;
                return ((o instanceof Map.Entry) &&
                        (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
                        (v = e.getValue()) != null &&
                        (k == key || k.equals(key)) &&
                        (v == (u = val) || v.equals(u)));
            }
    
            /** * Virtualized support for map.get(); overridden in subclasses. * 提供find方法，支持get方法。HashMap中的Node类中没有此方法 */
            Node<K,V> find(int h, Object k) {
                Node<K,V> e = this;
                if (k != null) {
                    do {
                        K ek;
                        if (e.hash == h &&
                            ((ek = e.key) == k || (ek != null && k.equals(ek))))
                            return e;
                    } while ((e = e.next) != null);
                }
                return null;
            }
        }

#### TreeNode ####

树节点类，另外一个核心的数据结构。当链表长度过长的时候，会转换为TreeNode。但是与HashMap不相同的是，它并不是直接转换为红黑树，而是把这些结点包装成TreeNode放在TreeBin对象中，由TreeBin完成对红黑树的包装。而且TreeNode在ConcurrentHashMap集成自Node类，而并非HashMap中的集成自LinkedHashMap.Entry

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;    // needed to unlink next upon deletion
            boolean red;
    
            TreeNode(int hash, K key, V val, Node<K,V> next,
                     TreeNode<K,V> parent) {
                super(hash, key, val, next);
                this.parent = parent;
            }
    
            Node<K,V> find(int h, Object k) {
                return findTreeNode(h, k, null);
            }
    
            /** * Returns the TreeNode (or null if not found) for the given key * starting at given root. */
            final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
                if (k != null) {
                    TreeNode<K,V> p = this;
                    do  {
                        int ph, dir; K pk; TreeNode<K,V> q;
                        TreeNode<K,V> pl = p.left, pr = p.right;
                        if ((ph = p.hash) > h)
                            p = pl;
                        else if (ph < h)
                            p = pr;
                        else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
                            return p;
                        else if (pl == null)
                            p = pr;
                        else if (pr == null)
                            p = pl;
                        else if ((kc != null ||
                                  (kc = comparableClassFor(k)) != null) &&
                                 (dir = compareComparables(kc, k, pk)) != 0)
                            p = (dir < 0) ? pl : pr;
                        else if ((q = pr.findTreeNode(h, k, kc)) != null)
                            return q;
                        else
                            p = pl;
                    } while (p != null);
                }
                return null;
            }
        }

#### TreeBean ####

这个类并不负责包装用户的key、value信息，而是包装的很多TreeNode节点。它代替了TreeNode的根节点，也就是说在实际的ConcurrentHashMap“数组”中，存放的是TreeBin对象，而不是TreeNode对象，这是与HashMap的区别。另外这个类还带有了读写锁。这个类的代码太长了，就不粘贴了。

#### ForwardingNode ####

一个用于连接两个table的节点类。它包含一个nextTable指针，用于指向下一张表。而且这个节点的key value next指针全部为null，它的hash值为-1. 这里面定义的find的方法是从nextTable里进行查询节点，而不是以自身为头节点进行查找

/** * A node inserted at head of bins during transfer operations. */
        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;
            }
    
            Node<K,V> find(int h, Object k) {
                // loop to avoid arbitrarily deep recursion on forwarding nodes
                outer: for (Node<K,V>[] tab = nextTable;;) {
                    Node<K,V> e; int n;
                    if (k == null || tab == null || (n = tab.length) == 0 ||
                        (e = tabAt(tab, (n - 1) & h)) == null)
                        return null;
                    for (;;) {
                        int eh; K ek;
                        if ((eh = e.hash) == h &&
                            ((ek = e.key) == k || (ek != null && k.equals(ek))))
                            return e;
                        if (eh < 0) {
                            if (e instanceof ForwardingNode) {
                                tab = ((ForwardingNode<K,V>)e).nextTable;
                                continue outer;
                            }
                            else
                                return e.find(h, k);
                        }
                        if ((e = e.next) == null)
                            return null;
                    }
                }
            }
        }

### 三个CAS方法 ###

/** * 获得在i位置上的Node节点 */
        @SuppressWarnings("unchecked")
        static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
            return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
        }
        /** * 利用CAS算法设置i位置上的Node节点（将c和table[i]比较，相同则插入v）。 */
        static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                            Node<K,V> c, Node<K,V> v) {
            return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
        }
        /** * 利用volatile方法设置节点位置的值，仅在上锁区被调用 */
        static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
            U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
        }

### 重要方法 ###

#### put() ####

/** Implementation for put and putIfAbsent */
        final V putVal(K key, V value, boolean onlyIfAbsent) {
                //不允许 key或value为null
            if (key == null || value == null) throw new NullPointerException();
            //计算hash值
            int hash = spread(key.hashCode());
            int binCount = 0;
            //死循环,直到插入成功
            for (Node<K,V>[] tab = table;;) {
                Node<K,V> f; int n, i, fh;
                //如果table为空的话，初始化table
                if (tab == null || (n = tab.length) == 0)
                    tab = initTable();
                // 根据hash值计算出在table里面的位置 
                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;             // no lock when adding to empty bin
                }
                // 检查table[i]的节点的hash是否等于MOVED
                // 如果等于，则检测到正在扩容，则帮助其扩容
                else if ((fh = f.hash) == MOVED)
                    tab = helpTransfer(tab, f);//帮助扩容
                else {
                    V oldVal = null;
                    //结点上锁 这里的结点可以理解为hash值相同组成的链表的头结点
                    synchronized (f) {
       //上锁，（Hash值相同的头结点）
                        if (tabAt(tab, i) == f) {
                            if (fh >= 0) {
       //说明这个节点是一个链表的节点 不是树的节点
                                binCount = 1;
                                //在这里遍历链表所有的结点
                                for (Node<K,V> e = f;; ++binCount) {
                                    K ek;
                                    //如果hash值和key值相同 则修改对应结点的value值
                                    if (e.hash == hash &&
                                        ((ek = e.key) == key ||
                                         (ek != null && key.equals(ek)))) {
                                        oldVal = e.val;
                                        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) {
                        //如果链表长度已经达到临界值8 就需要把链表转换为树结构
                        if (binCount >= TREEIFY_THRESHOLD)
                            treeifyBin(tab, i);
                        if (oldVal != null)
                            return oldVal;
                        break;
                    }
                }
            }
            //将当前ConcurrentHashMap的元素数量+1
            addCount(1L, binCount);
            return null;
        }

#### transfer() ####

/** * 一个过渡的table表 只有在扩容的时候才会使用 */
       private transient volatile Node<K,V>[] nextTable;
    
    /** * Moves and/or copies the nodes in each bin to new table. See * above for explanation. */
       private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
           int n = tab.length, stride;
           if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
               stride = MIN_TRANSFER_STRIDE; // subdivide range
           if (nextTab == null) {            // initiating
               try {
                   @SuppressWarnings("unchecked")
                   Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];//构造一个nextTable对象 它的容量是原来的两倍
                   nextTab = nt;
               } catch (Throwable ex) {      // try to cope with OOME
                   sizeCtl = Integer.MAX_VALUE;
                   return;
               }
               nextTable = nextTab;
               transferIndex = n;
           }
           int nextn = nextTab.length;
           ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);//构造一个连节点指针 用于标志位
           boolean advance = true;//并发扩容的关键属性 如果等于true 说明这个节点已经处理过
           boolean finishing = false; // to ensure sweep before committing nextTab
           for (int i = 0, bound = 0;;) {
               Node<K,V> f; int fh;
               //这个while循环体的作用就是在控制i-- 通过i--可以依次遍历原hash表中的节点
               while (advance) {
                   int nextIndex, nextBound;
                   if (--i >= bound || finishing)
                       advance = false;
                   else if ((nextIndex = transferIndex) <= 0) {
                       i = -1;
                       advance = false;
                   }
                   else if (U.compareAndSwapInt
                            (this, TRANSFERINDEX, nextIndex,
                             nextBound = (nextIndex > stride ?
                                          nextIndex - stride : 0))) {
                       bound = nextBound;
                       i = nextIndex - 1;
                       advance = false;
                   }
               }
               if (i < 0 || i >= n || i + n >= nextn) {
                   int sc;
                   if (finishing) {
                       //如果所有的节点都已经完成复制工作 就把nextTable赋值给table 清空临时对象nextTable
                       nextTable = null;
                       table = nextTab;
                       sizeCtl = (n << 1) - (n >>> 1);//扩容阈值设置为原来容量的1.5倍 依然相当于现在容量的0.75倍
                       return;
                   }
                   //利用CAS方法更新这个扩容阈值，在这里面sizectl值减一，说明新加入一个线程参与到扩容操作
                   if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                       if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                           return;
                       finishing = advance = true;
                       i = n; // recheck before commit
                   }
               }
               //如果遍历到的节点为空 则放入ForwardingNode指针
               else if ((f = tabAt(tab, i)) == null)
                   advance = casTabAt(tab, i, null, fwd);
               //如果遍历到ForwardingNode节点 说明这个点已经被处理过了 直接跳过 这里是控制并发扩容的核心
               else if ((fh = f.hash) == MOVED)
                   advance = true; // already processed
               else {
                       //节点上锁
                   synchronized (f) {
                       if (tabAt(tab, i) == f) {
                           Node<K,V> ln, hn;
                           //如果fh>=0 证明这是一个Node节点
                           if (fh >= 0) {
                               int runBit = fh & n;
                               //以下的部分在完成的工作是构造两个链表 一个是原链表 另一个是原链表的反序排列
                               Node<K,V> lastRun = f;
                               for (Node<K,V> p = f.next; p != null; p = p.next) {
                                   int b = p.hash & n;
                                   if (b != runBit) {
                                       runBit = b;
                                       lastRun = p;
                                   }
                               }
                               if (runBit == 0) {
                                   ln = lastRun;
                                   hn = null;
                               }
                               else {
                                   hn = lastRun;
                                   ln = null;
                               }
                               for (Node<K,V> p = f; p != lastRun; p = p.next) {
                                   int ph = p.hash; K pk = p.key; V pv = p.val;
                                   if ((ph & n) == 0)
                                       ln = new Node<K,V>(ph, pk, pv, ln);
                                   else
                                       hn = new Node<K,V>(ph, pk, pv, hn);
                               }
                               //在nextTable的i位置上插入一个链表
                               setTabAt(nextTab, i, ln);
                               //在nextTable的i+n的位置上插入另一个链表
                               setTabAt(nextTab, i + n, hn);
                               //在table的i位置上插入forwardNode节点 表示已经处理过该节点
                               setTabAt(tab, i, fwd);
                               //设置advance为true 返回到上面的while循环中 就可以执行i--操作
                               advance = true;
                           }
                           //对TreeBin对象进行处理 与上面的过程类似
                           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);
                                   if ((h & n) == 0) {
                                       if ((p.prev = loTail) == null)
                                           lo = p;
                                       else
                                           loTail.next = p;
                                       loTail = p;
                                       ++lc;
                                   }
                                   else {
                                       if ((p.prev = hiTail) == null)
                                           hi = p;
                                       else
                                           hiTail.next = p;
                                       hiTail = p;
                                       ++hc;
                                   }
                               }
                               //如果扩容后已经不再需要tree的结构 反向转换为链表结构
                               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;
                                //在nextTable的i位置上插入一个链表 
                               setTabAt(nextTab, i, ln);
                               //在nextTable的i+n的位置上插入另一个链表
                               setTabAt(nextTab, i + n, hn);
                                //在table的i位置上插入forwardNode节点 表示已经处理过该节点
                               setTabAt(tab, i, fwd);
                               //设置advance为true 返回到上面的while循环中 就可以执行i--操作
                               advance = true;
                           }
                       }
                   }
               }
           }
       }

#### get() ####

public V get(Object key) {
            Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
            //计算hash值
            int h = spread(key.hashCode());
            //根据hash值确定节点位置
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (e = tabAt(tab, (n - 1) & h)) != null) {
                //如果搜索到的节点key与传入的key相同且不为null,直接返回这个节点 
                if ((eh = e.hash) == h) {
                    if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                        return e.val;
                }
                //如果eh<0 说明这个节点在树上 直接寻找
                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;
        }

[70]: /images/20220528/673a8ed6f92c425d9f63b7016858cc5b.png