JDK7 ConcurrentHashMap源码详细解读

悠悠 2022-11-01 14:00 219阅读 0赞

HashMap是线程不安全的，多线程并发情况下容易导致死循环，Hashtable是线程安全的类，他在进行put和get时会给表上一把锁，其他线程就不能访问到数据，必须等上一个线程执行结束后才能访问，效率比较低，于是引入了ConcurrentHashMap，采用分段锁机制。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTQyNzIw_size_16_color_FFFFFF_t_70][]

![20210224173537600.png][]

**ConcurrentHashMap内存图**：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTQyNzIw_size_16_color_FFFFFF_t_70 1][]

### **重要参数** ###

// 初始化默认值 16
    static final int DEFAULT_INITIAL_CAPACITY = 16; 
    // 默认加载因子 0.75
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 该表的默认并发级别
    static final int DEFAULT_CONCURRENCY_LEVEL = 16;
    // 数组最大容量 2的30次方
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 每段表的最小容量（每个HashEntry数组的长度）。必须是2的幂，至少是2，以避免在延迟构建之后在下次使用时立即调整大小。
    static final int MIN_SEGMENT_TABLE_CAPACITY = 2;
    // 允许的最大段数；用于绑定构造函数参数。必须是小于1<<24的二次幂。
    static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
    // 用于锁定之前大小和包含值方法的非同步重试次数
    static final int RETRIES_BEFORE_LOCK = 2;

### **构造函数** ###

// 传入Segment[]数组的容量为16，默认加载因子0.75，默认级别16
    public ConcurrentHashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
    }
    // 自定义传入Segment[]数组的容量，默认加载因子0.75，默认级别16
    public ConcurrentHashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
    }
    // 自定义传入Segment[]数组的容量、加载因子5，默认级别16
    public ConcurrentHashMap(int initialCapacity, float loadFactor) {
        this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
    }
    // 泛型上限，Map对象传入键值对，键-传入K类或K的子类，值-传入V类或V的子类
    public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                      DEFAULT_INITIAL_CAPACITY),
             DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
        putAll(m);
    }
    // 传入Segment[]数组的容量、加载因子、默认级别，初始化
    public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
        // 判断传入参数是否正确，否则抛非法参数异常
        if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
            throw new IllegalArgumentException();
        // 限制数组的最大并发级别
        if (concurrencyLevel > MAX_SEGMENTS)
            concurrencyLevel = MAX_SEGMENTS;
        // Find power-of-two sizes best matching arguments
        int sshift = 0;
        int ssize = 1;
        // 找到Segment数组长度，大于等于并发级别的2的幂次值，如：level=16,ssize=16;level=17,ssize=32
        // 这里的concurrencyLevel默认为16，所以此循环算出来sshift为4
        while (ssize < concurrencyLevel) {
            ++sshift;
            ssize <<= 1;
        }
        // segmentShift用于定位参与散列预算的位数，默认为28
        // 这里的sshift，因为上面位操作共移动了4次，2^4=16可以快速计算当前Segment数组容量，所以后面的put中计算j的值(将要存放的Segment数组中的下标) >>>(32-sshift)&15 的结果会在[0-15]区间上（其实就是让高4位参与计算）
        // 如果concurrencyLevel=17,ssize=32,sshift=5，就让高5位参与运算
        this.segmentShift = 32 - sshift;
        // 散列运算的掩码，默认为15，掩码的二进制各个位的值都是1，目的是为了计算得到key的hash值在Segment数组中的位置
        this.segmentMask = ssize - 1;
        // 限制数组容量最大数
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        // Segment里HashEntry数组的长度，如果c大于1，就会取大于等于c的2的N次幂值，所以cap不是1就是2的N次方。
        int c = initialCapacity / ssize;
        if (c * ssize < initialCapacity)
            ++c;
        // HashEntry数组的最小长度为2
        int cap = MIN_SEGMENT_TABLE_CAPACITY;
        while (cap < c)
            cap <<= 1;
        // create segments and segments[0]
        // 计算出segments[0]原型，下次put时，如果位置为空，则可以直接引用segments[0]中的参数，如：loadFactor、threshold 、HashEntry[]数组长度
        Segment<K,V> s0 = new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
                             (HashEntry<K,V>[])new HashEntry[cap]);
        // 创建Segment数组，默认为16大小
        Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
        // 设置ss对象数组中SBASE偏移地址对应的object型field的值为s0。这是一个有序或者有延迟的方法，并且不保证值的改变被其他线程立即看到。只有在field被volatile修饰并且期望被意外修改的时候使用才有用。
        UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
        this.segments = ss;
    }

**Unsafe类**：Unsafe类提供了硬件级别的原子操作，Java无法直接访问到操作系统底层（如系统硬件等)，为此Java使用native方法来扩展Java程序的功能。Java并发包(java.util.concurrent)中大量使用了CAS操作,涉及到并发的地方都调用了sun.misc.Unsafe类方法进行**CAS（Compare And Swap比较并交换）**操作。（该类其实就是**让Java直接操作内存中的值**，作用有点跟native相似）

[Unsafe类应用解析链接][Unsafe]

**Unsafe类中getUnsafe()方法****：获取当前Unsafe对象**

@CallerSensitive
    public static Unsafe getUnsafe() {
        // 获取当前是哪个类使用Unsafe的类加载器
        Class var0 = Reflection.getCallerClass();
        // 如果当前类加载器不为空，则抛出不安全异常
        if (var0.getClassLoader() != null) {
            throw new SecurityException("Unsafe");
        } else {
        // 否则直接返回当前unsafe实例
            return theUnsafe;
        }
    }

**Segment****对象**

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

Segment实现了ReentrantLock，也就带有锁的功能。由于put方法需要对共享变量进行写入操作，所以为了线程安全，在操作共享变量是，必须加锁。当执行put操作时，首先根据key的hash值定位到Segment，**若该Segment还没有初始化，则通过CAS操作进行赋值**，然后进行的二次hash操作，找到相应的HashEntry的位置。在加锁时，会通过继承ReentrantLock的tryLock()方法尝试获取锁，若获取成功，就直接在相应的位置插入；若已经有线程获取了该Segment的锁，那当前线程会以自旋的方式继续调用tryLock()方法获取锁，超过指定次数就挂起，等待唤醒。

**静态方法块，初始化加载参数**

// Unsafe mechanics
    private static final sun.misc.Unsafe UNSAFE;
    private static final long SBASE;
    private static final int SSHIFT;
    private static final long TBASE;
    private static final int TSHIFT;
    private static final long HASHSEED_OFFSET;
    private static final long SEGSHIFT_OFFSET;
    private static final long SEGMASK_OFFSET;
    private static final long SEGMENTS_OFFSET;
    static {
        int ss, ts;
        try {
            // 得到UNSAFE实例
            UNSAFE = sun.misc.Unsafe.getUnsafe();
            Class tc = HashEntry[].class;
            Class sc = Segment[].class;
            // 获取HashEntry数组中第一个元素的偏移地址。
            TBASE = UNSAFE.arrayBaseOffset(tc);
            // 获取Segment数组中第一个元素的偏移地址。
            SBASE = UNSAFE.arrayBaseOffset(sc);
            // 获取HashEntry数组寻址的换算因子
            ts = UNSAFE.arrayIndexScale(tc);
            // 获取Segment数组寻址的换算因子
            ss = UNSAFE.arrayIndexScale(sc);
            // 返回ConcurrentHashMap中hashSeed的内存地址偏移量
            HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
                ConcurrentHashMap.class.getDeclaredField("hashSeed"));
            // 返回ConcurrentHashMap中segmentShift的内存地址偏移量
            SEGSHIFT_OFFSET = UNSAFE.objectFieldOffset(
                ConcurrentHashMap.class.getDeclaredField("segmentShift"));
            // 返回ConcurrentHashMap中segmentMask的内存地址偏移量
            SEGMASK_OFFSET = UNSAFE.objectFieldOffset(
                ConcurrentHashMap.class.getDeclaredField("segmentMask"));
            // 返回ConcurrentHashMap中segments的内存地址偏移量
            SEGMENTS_OFFSET = UNSAFE.objectFieldOffset(
                ConcurrentHashMap.class.getDeclaredField("segments"));
        } catch (Exception e) {
            throw new Error(e);
        }
        if ((ss & (ss-1)) != 0 || (ts & (ts-1)) != 0)
            throw new Error("data type scale not a power of two");
        // 计算Segment数组寻址的换算因子，最高位前边0的个数
        SSHIFT = 31 - Integer.numberOfLeadingZeros(ss);
        // 计算HashEntry数组寻址的换算因子，最高位前边0的个数
        TSHIFT = 31 - Integer.numberOfLeadingZeros(ts);
    }

**numberOfLeadingZeros****(int i)方法：返回i最高位前边0的个数（int型最高32位）**

如：numberOfLeadingZeros(1)     结果：31

numberOfLeadingZeros(2)     结果：30

numberOfLeadingZeros(16)   结果：27

**测试numberOfLeadingZeros()方法**：

public class Test {
        private static sun.misc.Unsafe UNSAFE;
        static {
            // 当前测试类使用了UNSAFE类，加载器是AppClassLoader，所以getClassLoader()不为空
            // 而ConcurrentHashMap加载器是BootstrapClassLoader，所以加载时所以getClassLoader()为空，则返回Unsafe实例
            // 报错：java.lang.SecurityException: Unsafe，不能使用直接获取Unsafe实例这种情况
            // UNSAFE = sun.misc.Unsafe.getUnsafe();
    
            // 使用反射获取，因为在Unsafe类中有个theUnsafe属性，在静态方法块中 theUnsafe = new Unsafe();
            try {
                Field unsafe = Unsafe.class.getDeclaredField("theUnsafe");
                unsafe.setAccessible(true);
                UNSAFE = (Unsafe)unsafe.get(null);
            } catch (NoSuchFieldException | IllegalAccessException e) {
                e.printStackTrace();
            }
        }
        public static void main(String[] args) throws Exception {
            // 获取String数组中一个元素占用的大小，假如算出来的ss为4
            int ss = UNSAFE.arrayIndexScale(String[].class);
            // j为数组中的下标
            int j = 2;
            // 计算要存放的地址：2 * 4 = 8
            System.out.println(ss * j);
            // 这里的j<<(31-Integer.numberOfLeadingZeros(ss))计算就是put中(j << SSHIFT)操作
            // 2 << (31 - 29) = 2 << 2 = 8   【注】：这里的29是4的最高位前边有29个0
            System.out.println(j << (31 - Integer.numberOfLeadingZeros(ss)));
        }
    }

结果：![20210224174404638.png][]

### put()方法 ###

在插入操作需要经过两个步骤，第一步判断是否需要对Segment里的HashEntry数组进行扩容，第二步定位添加元素的位置，然后将其放在HashEntry数组中。

**是否需要扩容？**

在插入元素前会先判断Segment里的HashEntry数组是否超过容量threshold，如果超过了阈值，则对数组进行扩容。这里的扩容方式与HashMap的扩容方式稍有不同，HashMap是在插入元素之后判断元素是否已经达到容量，如果达到了就进行扩容，但是有可能扩容之后就没有新元素插入，则HashMap就进行了一次无效的扩容。

**如何扩容？**

扩容时，首先建立一个容量是原来两倍的数组，然后将原数组中的元素再散列后插入到新数组中。为了高效，ConcurrentHashMap不会对整个容器进行扩容，而是只对某个segment进行扩容。

**问题**：put()方法中计算两次数组下标是什么？

在计算Segment数组定位时计算了一次hash值，是取的高4位做&运算**int j = (hash >>> segmentShift) & segmentMask;**。在HashEntry数组中定位时，又计算了一次hash值，是取的低4位参与的&运算**int index = (tab.length - 1) & hash;**。

// 这里的key和value都不能为null
    public V put(K key, V value) {
        Segment<K,V> s;
        // 传入的值不能为空
        if (value == null)
            throw new NullPointerException();
        // 计算key的hash值，HashMao中key可以为null，但是这里的key不能为null；假如key可以为null的话，你无法知道get(null)返回的null是什么意思
        int hash = hash(key);
        // 在创建时已经计算出this.segmentShift = 32 - sshift; 其中sshift默认为4
        // this.segmentMask = ssize - 1; 其中ssize默认为16
        // 先对计算出的hash值右移shift位，然后在&运算mask得到当前key要存放在哪个segment[]中
        int j = (hash >>> segmentShift) & segmentMask;
        // 这里的UNSAFE.getObject取的是内存中segments数组中第j个位置的元素。并赋值给s，判断是否为空
        // (j << SSHIFT)是计算的偏移量，SBASE是segments数组的开始地址，两者相加就是将要存放的地址
        if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
             (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
            // 如果当前位置上为空（没有Segment对象），则生成一个Segment对象，放在j个位置上，这里可能会产生并发问题
            s = ensureSegment(j);
        // 在Segment中的HashEntry[]中put数据
        return s.put(key, hash, value, false);
    }

其中**int j = (hash >>> segmentShift) & segmentMask;**举例：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTQyNzIw_size_16_color_FFFFFF_t_70 2][]

**ensureSegment****()方法**：Segment类中的方法，多个线程进来时生成Segment对象时可能会并发问题

private Segment<K,V> ensureSegment(int k) {
        // 获取当前Segment[]对象
        final Segment<K,V>[] ss = this.segments;
        // 定位操作，跟上边 j << SSHIFT) + SBASE 一样
        long u = (k << SSHIFT) + SBASE; // raw offset
        Segment<K,V> seg;
        // double check，保证多个线程并发情况下，只有一个线程创建成功
        // 判断当前位置Segemnt对象是否为空
        if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
            // 得到Segemnt[0]的信息，记录表长、加载因子、计算阈值，采用原型模式
            Segment<K,V> proto = ss[0]; // use segment 0 as prototype
            int cap = proto.table.length;
            float lf = proto.loadFactor;
            int threshold = (int)(cap * lf);
            // 根据Segemnt[0]中HashEntry[]，创建HashEntry[]数组，为了放入当前Segment中
            HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
            // 这里再次判断是否已经有线程已经创建好了Segment
            if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) { // recheck
                // 创建Segment对象，并赋值
                Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
                // 这里采用while循环，目的是在多线程情况下，让它一直判断是否已经创建好了Segemnt
                while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
                    // CAS操作，保证只有一个线程创建
                    // 如果还是为null，则往里面添加Segment
                    if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
                        // 这里的break目的是为了结束while循环判断
                        break;
                }
            }
        }
        // 返回创建好的Segment对象
        return seg;
    }

**Segment中的put()方法**：传入的数据：**s.put(key, hash, value, false)**;

final V put(K key, int hash, V value, boolean onlyIfAbsent) {
        // tryLock()和lock()方法：
        //    tryLock()：不会阻塞。如果能拿到锁，返回true；如果不能拿到锁，返回false。
        //    lock()：会阻塞。会一直等待拿锁
        // 尝试对当前Segment对象上锁，如果能拿到锁，则返回null；如果不能拿到锁，则用scanAndLockForPut()方法去尝试获取锁的等待的过程中去执行一些其他操作。比如：去创建HashEntry对象出来
        HashEntry<K,V> node = tryLock() ? null :
            scanAndLockForPut(key, hash, value);
        V oldValue;
        try {
            // 取当前Segment对象里面的HashEntry[]
            HashEntry<K,V>[] tab = table;
            // 计算要存放在HashEntry[]中的下标值，做的是低位&运算
            int index = (tab.length - 1) & hash;
            // 取HashEntry[]中第index中的位置，这里entryAt()方法采用的是直接取内存中的值
            HashEntry<K,V> first = entryAt(tab, index);
            // 从头开始遍历HashEntry链表
            for (HashEntry<K,V> e = first;;) {
                // 如果当前HashEntry对象不为空
                if (e != null) {
                    K k;
                    // 判断循环到当前的key值是否等于要存放的key值
                    if ((k = e.key) == key || (e.hash == hash && key.equals(k))) {
                        // 如果相等，则记录当前HashEntry的值，需要返回
                        oldValue = e.value;
                        // 这里的onlyIfAbsent默认传入为false
                        if (!onlyIfAbsent) {
                            // 更新当前的最新值，并且把hash映射的次数++
                            e.value = value;
                            ++modCount;
                        }
                        // 找到有相同的key，停止循环
                        break;
                    }
                    // 没有找到相同的key，则把下一个元素赋值给当前元素，继续遍历链表
                    e = e.next;
                }
                // 如果当前HashEntry对象为空
                else {
                    // 如果node在上边已经创建好了，则添加进去
                    if (node != null)
                        node.setNext(first);
                    else
                        // 创建一个HashEntry对象，也就是要插入的对象
                        node = new HashEntry<K,V>(hash, key, value, first);
                    // 给HashEntry中元素+1
                    int c = count + 1;
                    // 如果数量超过HashEntry的阈值
                    if (c > threshold && tab.length < MAXIMUM_CAPACITY)
                        // 则给HashEntry[]扩容
                        rehash(node);
                    else
                        // 否则将当前node头插法添加到HashEntry[]的index下标中
                        setEntryAt(tab, index, node);
                    // 哈希映射被修改的次数++
                    ++modCount;
                    // 更新当前HashEntry[]中的元素个数
                    count = c;
                    // 当前的key在链表中没有，已经添加到HashEntry中的情况，返回null
                    oldValue = null;
                    break;
                }
            }
        } finally {
            // 解锁
            unlock();
        }
        return oldValue;
    }

**【问题】以下两段代码使用tryLock()和lock()，两者加锁一样吗？**

ReentrantLock lock = new ReentrantLock();
    while (lock.tryLock()){
        // 这个循环里面一直等待锁，可以做其他事情
        System.out.println("其他事情");
    }
    lock.lock();

答：**不一样**。while (lock.tryLock())\{\} 这段代码循环**会消耗CPU内存**，但是lock.lock() 进入等待队列，**不会消耗CPU内存**，而且在等待锁的过程中还可以做其他事情。

**scanAndLockForPut()方法**：

private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
        // 通过Hash值计算Segment中相应位置上的第一个HashEntry链表元素
        HashEntry<K,V> first = entryForHash(this, hash);
        HashEntry<K,V> e = first;
        HashEntry<K,V> node = null;
        // 重试的次数
        int retries = -1; // negative while locating node
        // 循环尝试去拿锁，如果拿到锁了则返回node，没有拿到锁则进行循环
        // 也就是每次遍历链表中的节点时都会去尝试拿锁
        while (!tryLock()) {
            // 进行重新检查
            HashEntry<K,V> f; // to recheck first below
            // 刚开始为-1，则进入条件
            if (retries < 0) {
                // 一种情况是得到的链表为空，没有元素
                // 这里还有一种情况就是链表遍历到尾结点
                if (e == null) {
                    // 再次判断是否有线程创建了HashEntry对象
                    if (node == null) // speculatively create node
                        // 如果都满足以上条件，则创建HashEntry对象
                        node = new HashEntry<K,V>(hash, key, value, null);
                    // 将重试次数置为0，不让他进入retries < 0这个条件
                    // 说明此时已经创建HashEntry对象了
                    retries = 0;
                }
                // 说明遍历到当前链表的key已经存在
                else if (key.equals(e.key))
                    // 将重试次数置为0，不让他进入retries < 0这个条件
                    // 说明此时链表中有这个HashEntry对象了
                    retries = 0; 
                else
                    // 继续遍历链表，向下找
                    e = e.next;
            }
            // 如果当前重试次数超过最大值，则阻塞，一直等待去拿锁，拿到锁就返回
            else if (++retries > MAX_SCAN_RETRIES) {
                lock();
                break;
            }
            // (retries & 1) == 0 说明在retries为偶数的时候重新进行链表的判断
            else if ((retries & 1) == 0 &&
                    // 这里的entryForHash()方法跟上边的一样，目的是判断通过Hash值计算Segment中相应位置上的第一个HashEntry链表元素有没有被修改（头插法的原因）。如果有改变，则说明有新元素被插入了
                     (f = entryForHash(this, hash)) != first) {
                // 将当前链表重新赋值，进行遍历
                e = first = f; // re-traverse if entry changed
                // 重新初始化retries 
                retries = -1;
            }
        }
        // 返回拿到锁的node节点
        return node;
    }

Get到新知识：利用位操作判断奇偶

for (int i = 1; i <= 10; i++) {
        // 判断i是否为偶数
        if((i & 1) == 0){
            System.out.println(i);
        }
    }

结果：![20210224175220718.png][]

**entryAt()方法**：取当前内存中的HashEntry对象

static final <K,V> HashEntry<K,V> entryAt(HashEntry<K,V>[] tab, int i) {
        // 如果HashEntry[]数组为空，则返回NULL;否则计算并返回当前位置内存中的值
        return (tab == null) ? null :
            (HashEntry<K,V>) UNSAFE.getObjectVolatile(tab, ((long)i << TSHIFT) + TBASE);
    }

**头插法**示意图：

![20210224175303564.png][]![20210224175308780.png][]

**rehash()方法：**

private void rehash(HashEntry<K,V> node) {
        // 记录原来的HashEntry数组信息，表长
        HashEntry<K,V>[] oldTable = table;
        int oldCapacity = oldTable.length;
        // 成倍扩容
        int newCapacity = oldCapacity << 1;
        // 计算新数组的阈值
        threshold = (int)(newCapacity * loadFactor);
        // 创建新数组
        HashEntry<K,V>[] newTable = (HashEntry<K,V>[]) new HashEntry[newCapacity];
        // 记录表的最大下标，方便&运算
        int sizeMask = newCapacity - 1;
        // 转移原数组
        for (int i = 0; i < oldCapacity ; i++) {
            // 记录每一个HahsEntry[]中链表的第一个结点
            HashEntry<K,V> e = oldTable[i];
            // 如果第一个节点不为空，则开始遍历它
            if (e != null) {
                // 记录第一个节点的下一个节点
                HashEntry<K,V> next = e.next;
                // 计算在新数组中的下标位置
                int idx = e.hash & sizeMask;
                // 如果第一个节点的下个节点不存在，则直接将第一个节点转移到新数组中去
                if (next == null)   //  Single node on list
                    newTable[idx] = e;
                // 否则遍历链表，进行转移
                else { // Reuse consecutive sequence at same slot
                    // 从第一个节点开始，记录计算好每一次相同最后一个元素
                    HashEntry<K,V> lastRun = e;
                    int lastIdx = idx;
                    // 寻找旧表中在新表中顺序不相同的位置，相同则不进行操作
                    // 目的是为了减少移动操作
                    for (HashEntry<K,V> last = next; last != null; last = last.next) {
                        // 计算原来的hash值再新表中的下标
                        int k = last.hash & sizeMask;
                        // 如果不等于原来数组下标中的位置，则记录它
                        if (k != lastIdx) {
                            lastIdx = k;
                            lastRun = last;
                        }
                    }
                    // 将原来不相同的位置上的元素放到新数组中来
                    newTable[lastIdx] = lastRun;
                    // 移动不相同的元素
                    for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
                        V v = p.value;
                        int h = p.hash;
                        int k = h & sizeMask;
                        HashEntry<K,V> n = newTable[k];
                        newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
                    }
                }
            }
        }
        // 插入新节点
        // 计算将要存放的位置，头插法插入，最后赋值给table
        int nodeIndex = node.hash & sizeMask; // add the new node
        node.setNext(newTable[nodeIndex]);
        newTable[nodeIndex] = node;
        table = newTable;
    }

**数组扩容图示：**

假设第1、2、3个计算出在新数组中的下标一样，则移动第1个元素就完成了移动，然后继续找下一个节点，循环下去，直到链表遍历完。（提高效率）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTQyNzIw_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTQyNzIw_size_16_color_FFFFFF_t_70 4][]

![20210224175443889.png][]

### **get()方法** ###

// 都是去取内存中的值
    public V get(Object key) {
        Segment<K,V> s; // manually integrate access methods to reduce overhead
        HashEntry<K,V>[] tab;
        // 计算key的hash值
        int h = hash(key);
        // 计算当前key在Segemnts数组中的位置
        long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
        // 如果当前Segments中第u个位置不为空则进行查找
        if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
            (tab = s.table) != null) {
            // 循环遍历当前key在HashEntry数组上的位置
            for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
                     (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
                 e != null; e = e.next) {
                K k;
                // 如果找到，则返回值
                if ((k = e.key) == key || (e.hash == h && key.equals(k)))
                    return e.value;
            }
        }
        // 没有找到则返回null
        return null;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTQyNzIw_size_16_color_FFFFFF_t_70]: /images/20221024/9b70cc05cb8f4c708c9289434052a1f6.png
[20210224173537600.png]: /images/20221024/c59688dcde054c4eb01f7e80b8dee168.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTQyNzIw_size_16_color_FFFFFF_t_70 1]: /images/20221024/c7ee1326e4fc417a95ec16ab5d64dec4.png
[Unsafe]: http://blog.itpub.net/31559353/viewspace-2636126/
[20210224174404638.png]: /images/20221024/662af0fc5e7d489492b72d962420c9eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTQyNzIw_size_16_color_FFFFFF_t_70 2]: /images/20221024/d50919022fbd404093c982c45e530393.png
[20210224175220718.png]: /images/20221024/d6aa1afee996418e814dce3b725fafd4.png
[20210224175303564.png]: https://img-blog.csdnimg.cn/20210224175303564.png
[20210224175308780.png]: /images/20221024/e7b8cd4c78844c86814cfc3b00013a63.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTQyNzIw_size_16_color_FFFFFF_t_70 3]: /images/20221024/e281f1a47fa4400eb0ccc3788004be1f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTQyNzIw_size_16_color_FFFFFF_t_70 4]: /images/20221024/52aec86b73f74db3b4078f3accb71f9b.png
[20210224175443889.png]: /images/20221024/9d2d26e97f2d410e902767b5178830c1.png