万字详解HashMap底层原理及jdk1.8源码解读

╰+哭是因爲堅強的太久メ 2024-03-22 12:29 51阅读 0赞

### 一、前言 ###

HashMap在我们日常开发中可谓经常遇到，HashMap 源码和底层原理在现在面试中是必问的。所以我们要掌握一下，也是作为两年开发经验必备的知识点！HashMap基于Map接口实现，元素以`<Key,Value>`的方式存储，并且允许使用null 键和null值，因为key不允许重复，因此只能有一个键为null，另外HashMap是`无序的、线程不安全`的。

**HashMap继承类图`快捷键Ctrl+alt+U`**

![format_png][]

### 二、存储结构介绍 ###

> Jdk7.0之前 数组 + 链表 Jdk8.0开始 数组 + 链表 + 二叉树 链表内元素个数>8个 由链表转成二叉树 链表内元素个数<6个 由二叉树转成链表 红黑树，是一个自平衡的二叉搜索树，因此可以使查询的时间复杂度降为`O(logn)` 链表的长度特别长的时候，查询效率将直线下降，查询的时间复杂度为 `O(n)` Jdk1.7中链表新元素添加到链表的头结点，先加到链表的头节点，再移到数组下标位置。简称`头插法（并发时可能出现死循环）` Jdk1.8中链表新元素添加到链表的尾结点。简称`尾插法（解决了头插法死循环）`

**底层结构实例图**

![format_png 1][]

### 三、源码分析之常用变量解读 ###

/**
     * 默认初始容量 - 必须是 2 的幂。
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
    /**
     * 最大容量，如果一个更高的值被任何一个带参数的构造函数隐式指定使用。必须是 2 <= 1<<30 的幂。
     * 简单理解为：最大容量2的30次幂，如果带容量也会转化为2的次幂
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;
    
    /**
     * 构造函数中未指定时使用的负载因子。经过官方测试测出减少hash碰撞的最佳值
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    /**
     * 使用红黑树的计数阈值，超过8则转化为红黑树
     */
    static final int TREEIFY_THRESHOLD = 8;
    
    /**
     * 使用红黑树的计数阈值，低于6则转化为链表
     */
    static final int UNTREEIFY_THRESHOLD = 6;
    
    /**
     * 链表转化为红黑树，除了有阈值的限制，还有另外一个限制，需要数组容量至少达到64，才会转化为红黑树。
     * 这是为了避免，数组扩容和树化阈值之间的冲突。
     */
    static final int MIN_TREEIFY_CAPACITY = 64;
    
    /**
     * 在首次使用时初始化，并根据需要调整大小。分配时，长度始终是 2 的幂。
     * （我们还在某些操作中允许长度为零，以允许当前不需要的引导机制）
     */
    transient Node<K,V>[] table;
    
    /**
     * 保存缓存的 entrySet()，也就是存放的键值对
     */
    transient Set<Map.Entry<K,V>> entrySet;
    
    /**
     * 此映射中包含的键值映射的数量，就是数组的大小
     */
    transient int size;
    
    /**
     * 记录集合的结构变化和操作次数（例如remove一次进行modCount++）。
     * 该字段用于使 HashMap 的 Collection-views 上的迭代器快速失败。如果失败也就是我们常见的CME
     * （ConcurrentModificationException）异常
     */
    transient int modCount;
    
    /**
     * 数组扩容的大小
     * 计算方法 capacity * load factor  容量 * 加载因子
     * @serial
     */
    int threshold;
    
    /**
     * 哈希表的负载因子。
     * @serial
     */
    final float loadFactor;
    复制代码

### 四、源码分析之构造方法解读 ###

/**
     * 构造一个具有指定初始容量和负载因子的构造方法
     * 不建议使用这个构造方法，加载因子经过官方测试是效率最好的，所以为了效率应该保持默认
     */
    public HashMap(int initialCapacity, float loadFactor) {
    	// 参数为负数会抛出IllegalArgumentException异常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        // 传的值超过最大值则使用默认最大值                                     
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        // 哈希表的负载因子。                                      
        this.loadFactor = loadFactor;
        // 初始化的参数默认如果不是2的次幂，直接给你转化为2的次幂
        // 传的参数为11，会自动转化为比参数大的最近的2的次幂的值，也就是16。
        // 我们后面会详细说这个方法怎么进行转化的
        this.threshold = tableSizeFor(initialCapacity);
    }
    
    /**
     * 构造一个只有指定初始容量的方法
     */
    public HashMap(int initialCapacity) {
        // 我们会发现还是调用上面两个参数的构造方法，自动帮我们设置了加载因子
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    
    /**
     * 构造一个具有默认初始容量(16) 和默认负载因子(0.75)的构造方法
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
    
    /**
     * 指定map集合，转化为HashMap的构造方法
     */
    public HashMap(Map<? extends K, ? extends V> m) {
    	// 使用默认加载因子
        this.loadFactor = DEFAULT_LOAD_FACTOR;
    	//调用PutMapEntries()来完成HashMap的初始化赋值过程
        putMapEntries(m, false);
    }
    /**
     * 将传入的子Map中的全部元素逐个添加到HashMap中
     */
    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    	// 获得参数Map的大小，并赋值给s
        int s = m.size();
        // 判断大小是否大于0
        if (s > 0) {
        	// 证明有元素来插入HashMap
        	// 判断table是否已经初始化  如果table=null一般就是构造函数来调用的putMapEntries，或者构造后还没放过任何元素
            if (table == null) { // pre-size
            	// 如果未初始化，则计算HashMap的最小需要的容量（即容量刚好不大于扩容阈值）。这里Map的大小s就被当作HashMap的扩容阈值，然后用传入Map的大小除以负载因子就能得到对应的HashMap的容量大小（当前m的大小 / 负载因子 = HashMap容量）
                // ((float)s / loadFactor)但这样会算出小数来，但作为容量就必须向上取整，所以这里要加1。此时ft可以临时看作HashMap容量大小
                float ft = ((float)s / loadFactor) + 1.0F;
                // 判断ft是否超过最大容量大小，小于则用ft，大于则取最大容量
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                // 暂时存放到扩容阈值上,tableSizeFor会把t重新计算到2的次幂给扩容数组大小
                if (t > threshold)
                    threshold = tableSizeFor(t);
            }
            // 如果当前Map已经初始化,且这个map中的元素个数大于扩容的阀值就得扩容
            // 这种情况属于预先扩大容量，再put元素
            else if (s > threshold)
            	// 后面展开说
                resize();
            // 遍历map,将map中的key和value都添加到HashMap中
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                // 调用HashMap的put方法的具体实现方法putVal来对数据进行存放。该方法的具体细节在后面会进行讲解
                // putVal可能也会触发resize
                putVal(hash(key), key, value, false, evict);
            }
        }
    }
    复制代码

### 五、源码分析之常用方法解读 ###

#### 1、tableSizeFor方法解读 ####

/**
     * 返回给定目标容量的 2 次方。
     */
    static final int tableSizeFor(int cap) {
    	// cap = 10
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        // 小于0就是1，如果大于0在判断是不是超过最大容量就是n=15+1 = 16，超过就按最大容量
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
    复制代码

以`cap为10`为例：（右移规则为：==无符号位右移==）

10的二进制为：`0000 0000 0000 0000 0000 0000 0000 1010`

执行`int n = cap - 1;`

二进制结果为：`0000 0000 0000 0000 0000 0000 0000 1001`

执行`n |= n >>> 1;（先进行右移，结果和原来的数进行或运算[==有1则1==]）`

0000 0000 0000 0000 0000 0000 0000 1001 0000 0000 0000 0000 0000 0000 0000 0100 n>>1结果 ———————————————————— 0000 0000 0000 0000 0000 0000 0000 1101 n |= n >> 1 结果

二进制结果为：`0000 0000 0000 0000 0000 0000 0000 1101`

执行`n |= n >>> 2;`

0000 0000 0000 0000 0000 0000 0000 1101

0000 0000 0000 0000 0000 0000 0000 0011 n>>2结果

———————————————————— 0000 0000 0000 0000 0000 0000 0000 1111 n |= n >> 2 结果

二进制结果为：`0000 0000 0000 0000 0000 0000 0000 1111`

执行`n |= n >>> 4;`

0000 0000 0000 0000 0000 0000 0000 1111

0000 0000 0000 0000 0000 0000 0000 0000 n>>4结果

———————————————————— 0000 0000 0000 0000 0000 0000 0000 1111 n |= n >> 4 结果

二进制结果为：`0000 0000 0000 0000 0000 0000 0000 1111`

执行`n |= n >>> 8;`

0000 0000 0000 0000 0000 0000 0000 1111

0000 0000 0000 0000 0000 0000 0000 0000 n>>8结果

———————————————————— 0000 0000 0000 0000 0000 0000 0000 1111 n |= n >> 8 结果

二进制结果为：`0000 0000 0000 0000 0000 0000 0000 1111`

执行`n |= n >>> 16;`

0000 0000 0000 0000 0000 0000 0000 1111

0000 0000 0000 0000 0000 0000 0000 0000 n>>16结果

———————————————————— 0000 0000 0000 0000 0000 0000 0000 1111 n |= n >> 16 结果

二进制结果为：`0000 0000 0000 0000 0000 0000 0000 1111`

我们会发现，当数小的的时候进行到4时就不会变了我们得到的值为15，即输入10，经过此方法后得到`15`。遇到大的数才会明显，大家可以找个大的数字进行试试就是先`右移`在进行`或运算`。最后进行三门运算进行`+1`操作，最后结果为`16=2^4`

#### 2、hash方法解读 ####

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    复制代码

先判断key是否为空，若为空则返回0。上面说了HashMap仅支持一个key为null的。若非空，则先计算key的hashCode值，赋值给h，然后把h右移16位，并与原来的h进行异或处理（`相同为1，不同为0`）。 注释进行谷歌翻译： 计算 key.hashCode() 并传播（XOR）更高位的哈希降低。 由于该表使用二次幂掩码，因此仅在当前掩码之上位变化的散列集将始终发生冲突。 （已知的例子是在小表中保存连续整数的 Float 键集。）因此，我们应用了一种变换，将`高位的影响向下传播`。 在位扩展的速度、实用性和质量之间存在折衷。 因为许多常见的散列集已经合理分布（所以不要从传播中受益），并且因为我们使用树来处理 bin 中的大量冲突，我们只是以最简单的方式对一些`移位的位进行异或`，以`减少系统损失`， 以及`合并最高位的影响`，否则由于表边界，这些最高位将永远不会用于索引计算。

==总结==：`使用最简易的方式，及减少系统损失又减少了hash碰撞`。

#### 3、put方法解读 ####

![format_png 2][]

/**
    * 将指定的值与此映射中的指定键相关联。即当前key应该存放在数组的哪个下标位置
    * 如果映射先前包含键的映射，则替换旧的值。
    */
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    /**
    * 这才是真正的保存方法
    * @param hash   			经过hash运算后的key
    * @param key    			你要添加的key
    * @param value  			你要添加的value
    * @param onlyIfAbsent 		如果为真，则不要更改现有值，本次为FALSE，可以替换更改
    * @param evict 				如果为 false，则表处于创建模式。我们为true
    */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                  boolean evict) {
       Node<K,V>[] tab; Node<K,V> p; int n, i;
       // 判断table是否为空
       if ((tab = table) == null || (n = tab.length) == 0)
       	   // 如果空的话，会先调用resize扩容,resize我们后面展开讲解
           n = (tab = resize()).length;
       // 把通过hash得到的值与数组大小-1进行与运算，这个运算就可以实现取模运算，而且位运算还有个好处，就是速度比较快。
       // 得到key所对应的数组的节点，然后把该数组节点赋值给p,然后判断这个位置是不是有元素
       if ((p = tab[i = (n - 1) & hash]) == null)
       	   // key、value包装成newNode节点，直接添加到此位置。
           tab[i] = newNode(hash, key, value, null);
       // 如果当前数组下标位置已经有元素了，又分为三种情况。
       else {
           Node<K,V> e; K k;
           // 当前位置元素的hash值等于传过来的hash，并且他们的key值也相等
           if (p.hash == hash &&
               ((k = p.key) == key || (key != null && key.equals(k))))
               // 则把p赋值给e，后续需要新值把旧值替换
               e = p;
           // 来到这里说明该节点的key与原来的key不同，则看该节点是红黑树，还是链表
           else if (p instanceof TreeNode)
           	   // 如果是红黑树，则通过红黑树的方式，把key-value存到红黑树中。后面再讲解这个方法
               e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
           else {
           	   // 来到这里说明结构为链表，把key-value使用尾插法插到链表尾。
               // jdk1.7 链表是头插入法，在并发扩容时会造成死循环
               // jdk1.8 就把头插入法换成了尾插入法，虽然效率上有点稍微降低一些，但是不会出现死循环
               for (int binCount = 0; ; ++binCount) {
               	   // 遍历该链表，知道知道下一个节点为null。
                   if ((e = p.next) == null) {
                   	   // 说明到链表尾部，然后把尾部的next指向新生成的对象
                       p.next = newNode(hash, key, value, null);
                       // 如果链表的长度大于等于8
                       if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                       	   // 则链表转化成为红黑树 后面再补充
                           treeifyBin(tab, hash);
                       break;
                   }
                   // 如果在链表中找到了相同key的话，直接退出循环
                   if (e.hash == hash &&
                       ((k = e.key) == key || (key != null && key.equals(k))))
                       break;
                   p = e;
               }
           }
           // 说明发生了碰撞，e代表的是旧值，需要替换为新值
           if (e != null) { // existing mapping for key
               V oldValue = e.value;
               // 判断是不是允许覆盖旧值，和旧值是否为空
               if (!onlyIfAbsent || oldValue == null)
               		// 把旧值替换
                   e.value = value;
               // hashmap没有任何实现，我们先不考虑
               afterNodeAccess(e);
               // 返回新值
               return oldValue;
           }
       }
       // fail-fast机制每次对结构改变进行+1
       ++modCount;
       // 判断HashMap中的存的数据大小，如果大于数组长度*0.75，就要进行扩容
       if (++size > threshold)
           resize();
       // 也是一个空的实现
       afterNodeInsertion(evict);
       return null;
    }
    复制代码

#### 4、resize方法解读 ####

看不清查看原链接：[高清图链接][Link 1]

![format_png 3][]

/**
     * 初始化或者是将table大小加倍,如果为空，则按threshold分配空间，
     * 否则加倍后，每个容器中的元素在新table中要么呆在原索引处，要么有一个2的次幂的位移
     */
    final Node<K,V>[] resize() {
    	// 原来的数据
        Node<K,V>[] oldTab = table;
        // 获取原来的数组大小
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 旧数组的扩容阈值，注意看，这里取的是当前对象的 threshold 值，下边的第2种情况会用到。
        int oldThr = threshold;
        // 初始化新数组的容量和阈值
        int newCap, newThr = 0;
        // 1.当旧数组的容量大于0时，说明在这之前肯定调用过 resize扩容过一次，才会导致旧容量不为0。
        if (oldCap > 0) {
        	// 容量达到最大
            if (oldCap >= MAXIMUM_CAPACITY) {
            	// 扩容的大小设置为上限
                threshold = Integer.MAX_VALUE;
                // 直接返回默认原来的，无法在扩了
                return oldTab;
            }
            // 如果旧容量是在16到上限之间
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                // 新数组的容量和阈值都扩大原来的2倍
                newThr = oldThr << 1; // double threshold
        }
        // 2. 到这里 oldCap <= 0， oldThr(threshold) > 0，这就是 map 初始化的时候，
        // 第一次调用 resize的情况
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        // 3. 到这里，说明 oldCap 和 oldThr 都是小于等于0的。也说明我们的map是通过默认无参构造来创建的
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;// 16
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);// 12
        }
        // 只有经过2.才会进入
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            // 把计算后的ft符合大小，则赋值newThr 
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        // 最后得到要扩容的大小
        threshold = newThr;
        // 用于抑制编译器产生警告信息
        @SuppressWarnings({"rawtypes","unchecked"})
        	// 在构造函数时，并没有创建数组，在第一次调用put方法，导致resize的时候，才会把数组创建出来。
        	// 这是为了延迟加载，提高效率。
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        // 判断原来的数组有没有值，如果没有则把刚刚创建的数组进行返回
        if (oldTab != null) {
        	// 便利旧数组
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                // 判断当前元素是否为空
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    // 如果第一个元素的下一个元素为null，说明链表只有一个
                    if (e.next == null)
                    	// 则直接用它的hash值和新数组的容量取模就行(这样运算效率高)，得到新的下标位置
                        newTab[e.hash & (newCap - 1)] = e;
                    // 如果是红黑树
                    else if (e instanceof TreeNode)
                    	// 则拆分红黑树，这个小编就不带着往下深究了,感兴趣可以自己点进去看看
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    // 说明是链表且长度大于1
                    else { // preserve order
                    	// 链表旧位置的头尾节点
                        Node<K,V> loHead = null, loTail = null;
                        // 链表新位置的头尾节点
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        // 这里小编不太明白了，只能参考大佬的讲解，还是有点懵逼，等有时间懂了再来重新梳理
                        do {
                            next = e.next;
                            // 如果当前元素的hash值和oldCap做与运算为0，则原位置不变
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            // 不为0则把数据移动到新位置
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        // 原位置不变的一条链表，数组下标不变
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        // 移动到新位置的一条链表，数组下标为原下标加上旧数组的容量
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }
    复制代码

#### 5、get和containsKey方法解读 ####

/**
    * 根据key获取对应的value
    */
    public V get(Object key) {
        Node<K,V> e;
        // 调用后存在就获取元素的value返回
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    /**
    * 判断key是否在map中存在
    */
    public boolean containsKey(Object key) {
    	// 调用方法存在及不为null
        return getNode(hash(key), key) != null;
    }
    /**
    * 我们发现底层都是getNode来进行干活的
    */
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        // 判断数组不能为空，然后取到当前hash值计算出来的下标位置的第一个元素
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            // 如果hash值和key都相等并不为null，则说明我们要找的就是第一个元素
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                // 返回第一个元素
                return first;
            // 如果不是第一个就接着往下找
            if ((e = first.next) != null) {
            	// 如果是红黑树
                if (first instanceof TreeNode)
                    // 则以红黑树的查找方式进行获取到我们想要的key对应的值
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                // 这里说明为普通链表，我们依次往下找即可
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        // 找不到key对应的值，返回null
        return null;
    }
    复制代码

#### 6、remove方法解读 ####

/**
     * 如果key存在，就把元素删除
     */
    public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }
    
    /**
     * 删除方法的具体实现
    * @param hash   			经过hash运算后的key
    * @param key    			你要移除的key
    * @param value  			你要移除的value
     * @param matchValue 		如果为真，则仅在值相等时删除，我们为FALSE，key相同即删除
     * @param movable 			如果为假，则在删除时不要移动其他节点，我们为TRUE，删除移动其他节点
     */
    final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        // 判断table不为空，链表不为空
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
            // 数组中的第一个节点就是我们要删除的节点
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                // 要删除的节点给node
                node = p;
            // 第一个不是，并且后面还有节点
            else if ((e = p.next) != null) {
                // 如果是红黑树
                if (p instanceof TreeNode)
                	// 在红黑树中找到返回
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                	// 遍历链表
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            // 找到要删除的node
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            // 这里说明我们要删除的节点已找到
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                // 如果为红黑树，就按红黑树进行删除
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                //我们要删除的是头节点
                else if (node == p)
                     tab[index] = node.next;// 由于删除的是首节点，那么直接将节点数组对应位置指向到第二个节点即可
                //不是头节点，将当前节点指向删除节点的下一个节点
                else
                    p.next = node.next;// p的下一个节点指向到node的下一个节点即可把node从链表中删除了
                // 操作+1
                ++modCount;
                // map大小-1
                --size;
                // 空的实现
                afterNodeRemoval(node);
                // 返回删除的节点
                return node;
            }
        }
        return null;
    }
    复制代码

### 六、总结 ###

Has和Map得底层还是很多的，里面用的一些逻辑和算法，都是很牛皮的、耐人琢磨的。

[format_png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/3859404fa2fa411790f25aa9598580f1.png
[format_png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/e2cacca5b157467bbf04347286aa69bf.png
[format_png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/88ce9bb4029e45b2afcfba649f823066.png
[Link 1]: https://link.juejin.cn?target=https%3A%2F%2Fwww.processon.com%2Fview%2Flink%2F5c126926e4b0ed122da58975
[format_png 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/97b643a56d304767a4ba7fe7b602e4ac.png