HashMap源码研究——源码一行一行的注释

今天药忘吃喽~ 2023-10-08 13:17 11阅读 0赞

看过TreeMap的源码之后，终于来到了重头戏  
探究HashMap的源码

#### 文章目录 ####

*  类图
 *  结构参数
 *  构造
 *   *  \*\*1、无参构造方法HashMap()\*\*
     *  \*\*2、有一个初始容量参数的构造方法HashMap(int initialCapacity)\*\*
     *  \*\*3、有两个参数的构造方法HashMap(int initialCapacity, float loadFactor)\*\*
     *  \*\*4、有一个Map类型的参数的构造方法\*\*
 *  put
 *  第一次resize()
 *  为什么扩容重新计算位置后，还能找到以前数据的位置？
 *  链表转红黑树方法\`treeifyBin\`
 *  总结一下put方法的内容
 *  第二次扩容\`resize\`方法
 *  remove
 *  get

同学们反应看的比较吃力。。。。。。  
于是我连夜画了一张无敌的大图，大家看着图比较着文章看  
![在这里插入图片描述][75d46aa247d54dddba811c1c11af7229.png]

首先依旧是新建一个HashMap

HashMap hashMap = new HashMap();

让我们先看看类图

## 类图 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY4ODk3Mw_size_16_color_FFFFFF_t_70]  
很好，继承了`AbstractMap`，实现了`Map<K,V>, Cloneable, Serializable`三个接口，关于类图的打开方式请看这篇文章

[IDEA 查看 UML 类图][IDEA _ UML]

## 结构参数 ##

接下来按照惯例，先看看里面定义了什么参数  
(注释过长，这里只截取参数)

// 默认的HashMap中数组的长度 16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    // HashMap中的数组的最大容量 
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默认的扩容的平衡因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 链表转红黑树的 临界值
    static final int TREEIFY_THRESHOLD = 8;
    // 红黑树转链表的 临界值
    static final int UNTREEIFY_THRESHOLD = 6
    // 链表转红黑树的数组长度的临界值 
    static final int MIN_TREEIFY_CAPACITY = 64;
    
    // HashMap中的数组结构
    transient Node<K,V>[] table;
    // HashMap中的元素个数
    transient int size;
    // 对HashMap操作的次数
    transient int modCount;
    // 扩容的临界值
    int threshold;
    // 实际的扩容值
    final float loadFactor;

每一个参数都有对应的注释，这里要注意的是HashMap的底层结构

> Jdk1.7及以前是采用数组+链表  
> Jdk1.8之后 采用数组+链表 或者 数组+红黑树方式进行元素的存储  
> 存储在hashMap集合中的元素都将是一个Map.Entry的内部接口的实现

什么时候采用数组+链表，什么时候采用 数组+红黑树，以及相互转换，取决于链表(红黑树)的长度，已经在注释中写了。

## 构造 ##

按照惯例，首先看构造（基于JDK1.8）

### **1、无参构造方法HashMap()** ###

public HashMap() {
            //无参构造器
            //负载因子为默认值 0.75f
            //容量为默认初始值 16
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

### **2、有一个初始容量参数的构造方法HashMap(int initialCapacity)** ###

参数：`initialCapacity` 初始容量

public HashMap(int initialCapacity) {
        
            //此处通过把第二个参数负载因子使用默认值0.75f，然后调用有两个参数的构造方法
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }

> 这个一个参数的构造方法，使用HashMap的默认负载因子，把该初始容量和默认负载因子作为入参，调用HashMap的两个参数的构造方法

### **3、有两个参数的构造方法HashMap(int initialCapacity, float loadFactor)** ###

参数：`initialCapacity` 初始容量  
参数：`loadFactor` 负载因子

/**
         * Constructs an empty <tt>HashMap</tt> with the specified initial
         * capacity and load factor.
         * 通过指定的初始容量和负载因子初始化一个空的HashMap
         *
         * @param  initialCapacity the initial capacity   初始化容量
         * @param  loadFactor      the load factor        负载因子
         * @throws IllegalArgumentException if the initial capacity is negative
         *         or the load factor is nonpositive
         * 如果初始容量或者负载因子为负数，则会抛出非法数据异常
         */
        public HashMap(int initialCapacity, float loadFactor) {
        
            if (initialCapacity < 0)   //如果初始容量小于0，抛出异常
                throw new IllegalArgumentException("Illegal initial capacity: " +
                                                   initialCapacity);
            if (initialCapacity > MAXIMUM_CAPACITY)  //如果初始容量超过最大容量（1<<32）
                initialCapacity = MAXIMUM_CAPACITY;  //则使用最大容量作为初始容量
            if (loadFactor <= 0 || Float.isNaN(loadFactor))  //如果负载因子小于等于0或者不是数字，则抛出异常
                throw new IllegalArgumentException("Illegal load factor: " +
                                                   loadFactor);
            this.loadFactor = loadFactor;                //把负载因子赋值给成员变量loadFactor
     
    //调用tableSizeFor方法计算出不小于initialCapacity的最小的2的幂的结果，并赋给成员变量threshold
            this.threshold = tableSizeFor(initialCapacity); 
        }

我们下面看看tableSizeFor()这个方法是如何计算的，这个方法的实现原理很巧妙，源码如下：

/**
         * Returns a power of two size for the given target capacity.
         */
        static final int tableSizeFor(int cap) {
        
            int n = cap - 1;      //容量减1，为了防止初始化容量已经是2的幂的情况，最后有+1运算。
            n |= n >>> 1;         //将n无符号右移一位再与n做或操作
            n |= n >>> 2;         //将n无符号右移两位再与n做或操作
            n |= n >>> 4;         //将n无符号右移四位再与n做或操作
            n |= n >>> 8;         //将n无符号右移八位再与n做或操作
            n |= n >>> 16;        //将n无符号右移十六位再与n做或操作
            //如果入参cap为小于或等于0的数，那么经过cap-1之后n为负数，n经过无符号右移和或操作后仍未负 
            //数,所以如果n<0,则返回1;如果n大于或等于最大容量，则返回最大容量;否则返回n+1
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }

首先，为什么要对cap做减1操作。int n = cap - 1;  
这是为了防止，cap已经是2的幂。如果cap已经是2的幂， 又没有执行这个减1操作，则执行完后面的几条无符号右移操作之后，返回的capacity将是这个cap的2倍。如果不懂，要看完后面的几个无符号右移之后再回来看看。  
下面看看这几个无符号右移操作：  
如果n这时为0了（经过了cap-1之后），则经过后面的几次无符号右移依然是0，最后返回的capacity是1（最后有个n+1的操作）。  
这里只讨论n不等于0的情况。  
第一次右移

n |= n >> 1;

由于n不等于0，则n的二进制表示中总会有一bit为1，这时考虑最高位的1。通过无符号右移1位，则将最高位的1右移了1位，再做或操作，使得n的二进制表示中与最高位的1紧邻的右边一位也为1，如000011xxxxxx。  
第二次右移

n |= n >>> 2;

注意，这个n已经经过了n |= n >>> 1; 操作。假设此时n为000011xxxxxx ，则n无符号右移两位，会将最高位两个连续的1右移两位，然后再与原来的n做或操作，这样n的二进制表示的高位中会有4个连续的1。如00001111xxxxxx 。  
第三次右移

n |= n >>> 4;

这次把已经有的高位中的连续的4个1，右移4位，再做或操作，这样n的二进制表示的高位中会有8个连续的1。如00001111 1111xxxxxx 。  
以此类推  
注意，容量最大也就是32bit的正数，因此最后n |= n >>> 16; ，最多也就32个1，但是这时已经大于了MAXIMUM\_CAPACITY ，所以取值到MAXIMUM\_CAPACITY 。

> 但是，请注意，在构造方法中，并没有对table这个成员变量进行初始化，table的初始化被推迟到了put方法中，在put方法中会对threshold重新计算。

### **4、有一个Map类型的参数的构造方法** ###

/**
         * Constructs a new <tt>HashMap</tt> with the same mappings as the
         * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
         * default load factor (0.75) and an initial capacity sufficient to
         * hold the mappings in the specified <tt>Map</tt>.
         * 根据传入的指定的Map参数去初始化一个新的HashMap，该HashMap拥有着和原Map中相同的映射关系
         *  以及默认的负载因子（0.75f）和一个大小充足的初始容量
         * @param   m the map whose mappings are to be placed in this map
         * 参数 m  一个映射关系将会被新的HashMap所取代的Map
         * @throws  NullPointerException if the specified map is null
         * 如果这个Map为空的话，将会抛出空指针异常
         */
        public HashMap(Map<? extends K, ? extends V> m) {
        
            this.loadFactor = DEFAULT_LOAD_FACTOR;      //将默认的负载因子赋值给成员变量loadFactor
            putMapEntries(m, false);                    //调用PutMapEntries()来完成HashMap的初始化赋值过程
        }

这里要注意`putMapEntries()`方法，这个方法调用了HashMap的`resize()`扩容方法和`putVal()`存入数据方法  
接下来我们分析`put操作`，来研究下这几个方法

## put ##

首先点进put  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY4ODk3Mw_size_16_color_FFFFFF_t_70 1]  
源码如下  
**put源码：**  
这里我们想一下，如果让你去设计这个结构，你怎么设计？  
假如这是真实的业务场景，是不是得想一下业务是怎么样的？  
![在这里插入图片描述][936cfa6cd50d4dbd9b3c691564014c2c.png]  
带着问题，点进put方法

public V put(K key, V value) {
        
        return putVal(hash(key), key, value, false, true);
    }

首先看下这个hash(key)方法

static final int hash(Object key) {
        
        int h;
        // key.hashCode() 32长度的二进制的值
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }//右移16位的原因：是为了让哈希后的结果更均匀的分布，减少哈希碰撞，提升hashmap的运行效率

![在这里插入图片描述][b11fc38dd30c4cc583e7499503a3c321.png]

> 这里有一个经典的面试题  
> hashmap的key可以为空嘛？  
> 可以，因为在源码中key==null时会将哈希值取0

一个根据key值返回对应hash值的方法，普普通通  
emmmm，继续，让我们进去putVal这个方法：  
**putVal方法源码：**

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
        
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            if ((tab = table) == null || (n = tab.length) == 0)
                // 初始的判断
                // resize() 初始数组  扩容 初始的时候 获取了一个容量为16的数组
                n = (tab = resize()).length; // n 数组长度
            // 确定插入的key在数组中的下标 
            if ((p = tab[i = (n - 1) & hash]) == null)
                // 通过hash值找到的数组的下标  里面没有内容就直接赋值
                tab[i] = newNode(hash, key, value, null);
            else {
        
                Node<K,V> e; K k;
                if (p.hash == hash &&  // hash值相同&& 
                    // key也相同
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    // 插入的值的key 和 数组当前位置的 key是同一个 那么直接修改里面内容也就是覆盖
                    e = p;
                else if (p instanceof TreeNode)
                    // 表示 数组中存放的节点是一个 红黑树节点
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {
        
                    // 表示节点就是普通的链表
                    for (int binCount = 0; ; ++binCount) {
        
                        if ((e = p.next) == null) {
        
                            // 到了链表的尾部
                            p.next = newNode(hash, key, value, null);
                            // 将新的节点添加到了链表的尾部
                            // 判断是否满足 链表转红黑树的条件
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                // 转红黑树
                                treeifyBin(tab, hash);
                            break;
                        }
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
                if (e != null) {
         // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
            if (++size > threshold)//判断是否需要扩容
                resize();
            afterNodeInsertion(evict);
            return null;
        }

解析都写在注释中了，这里要注意的是扩容方法`resize`的使用，和链表转红黑树方法`treeifyBin`的使用  
这里介绍下扩容方法`resize`第一次调用的解析

## 第一次resize() ##

final Node<K,V>[] resize() {
        
            // table = null
            Node<K,V>[] oldTab = table;
            // oldCap = 0
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            // 原来的扩容因子 0
            int oldThr = threshold;
            // 新的容量和新的扩容因子
            int newCap, newThr = 0;
            if (oldCap > 0) {
         // 初始不执行 0
                if (oldCap >= MAXIMUM_CAPACITY) {
        
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    newThr = oldThr << 1; // double threshold
            }// 初始为0
            else if (oldThr > 0) // initial capacity was placed in threshold
                newCap = oldThr;
            else {
          
                // 新的数组容量 16
                newCap = DEFAULT_INITIAL_CAPACITY;
                // 新的扩容因子 0.75 * 16 = 12
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            if (newThr == 0) {
        
                float ft = (float)newCap * loadFactor;
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }// 更新了 扩容的临界值 12
            threshold = newThr;
            @SuppressWarnings({
        "rawtypes","unchecked"})
            // 创建了一个容量为16的Node数组
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            table = newTab; // 更新了table
            if (oldTab != null) {
        
                for (int j = 0; j < oldCap; ++j) {
        
                    Node<K,V> e;
                    if ((e = oldTab[j]) != null) {
        
                        oldTab[j] = null;
                        if (e.next == null)
                            newTab[e.hash & (newCap - 1)] = e;
                        else if (e instanceof TreeNode)
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                        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;
                                if ((e.hash & oldCap) == 0) {
        
                                    if (loTail == null)
                                        loHead = e;
                                    else
                                        loTail.next = e;
                                    loTail = e;
                                }
                                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;
        }

## 为什么扩容重新计算位置后，还能找到以前数据的位置？ ##

进行扩容，会伴随着一次重新hash分配，并且会遍历hash表中所有的元素，是非常耗时的。在编写程序中，要尽量避免resize。

HashMap在进行扩容时，使用的rehash方式非常巧妙，因为每次扩容都是翻倍，与原来计算的 (n-1)&hash的结果相比，只是多了一个bit位，所以节点要么就在原来的位置，要么就被分配到"原位置+旧容量"这个位置。  
怎么理解呢？例如我们从16扩展为32时，具体的变化如下所示：  
![在这里插入图片描述][8960568c08074ccbbbf22e43d97c18d9.png]  
因此元素在重新计算hash之后，因为n变为2倍，那么n-1的标记范围在高位多1bit(红色)，因此新的index就会发生这样的变化：  
![在这里插入图片描述][5d3a2835dbbb4837b7fdb0ad091c3e6b.png]  
说明：5是假设计算出来的原来的索引。这样就验证了上述所描述的：扩容之后所以节点要么就在原来的位置，要么就被分配到"原位置+旧容量"这个位置。

因此，我们在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就可以了，是0的话索引没变，是1的话索引变成“原索引+oldCap(原位置+旧容量)”。可以看看下图为16扩充为32的resize示意图：  
![在这里插入图片描述][d484eb01e9804240956e7ed5d3f55dd8.png]  
正是因为这样巧妙的rehash方式，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，在resize的过程中保证了rehash之后每个桶上的节点数一定小于等于原来桶上的节点数，保证了rehash之后不会出现更严重的hash冲突，均匀的把之前的冲突的节点分散到新的桶中了。

然后介绍下**链表转红黑树方法`treeifyBin`：**

## 链表转红黑树方法`treeifyBin` ##

final void treeifyBin(Node<K,V>[] tab, int hash) {
        
            int n, index; Node<K,V> e;
            // tab为空 或者 数组的长度小于64
            if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
                resize(); // 扩容
            else if ((e = tab[index = (n - 1) & hash]) != null) {
        
                // 链表转红黑树的逻辑
                TreeNode<K,V> hd = null, tl = null;
                do {
        
                    TreeNode<K,V> p = replacementTreeNode(e, null);
                    if (tl == null)
                        hd = p;
                    else {
        
                        p.prev = tl;
                        tl.next = p;
                    }
                    tl = p;
                } while ((e = e.next) != null);
                if ((tab[index] = hd) != null)
                    hd.treeify(tab);
            }
        }

## 总结一下put方法的内容 ##

1.  找到要插入的位置
2.  判断里面是否有值  
    2.1 **有值**：  
    判断当前节点是树型还是链表  
      2.1.1**链表：**  
      加到链表尾部，然后判断长度是否满足转红黑树的临界值  
      **2.1.2树型：**  
      直接插到树上  
    2.2 **无值**：  
    插入
3.  判断长度是否满足扩容（长度\*扩容因子）  
    若满足，则动态扩容

中间还有hash值的比较、红黑树转回链表等情况，不过这些情况比较少见，这里就不讨论了，接下来看下动态扩容的代码逻辑 ，也就是第二次扩容时`resize`方法的解析：

## 第二次扩容`resize`方法 ##

final Node<K,V>[] resize() {
        
            // [1,2,3,4,5,6,7,8,9,10,11,,,,]
            Node<K,V>[] oldTab = table;
            // 16
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            // 12
            int oldThr = threshold;
            int newCap, newThr = 0;
            if (oldCap > 0) {
        
                if (oldCap >= MAXIMUM_CAPACITY) {
        
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                // 新的容量是 原来容量的两倍
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    // 扩容的临界值  原来的两倍 24
                    newThr = oldThr << 1; // double threshold
            }
            else if (oldThr > 0) // initial capacity was placed in threshold
                newCap = oldThr;
            else {
                       // zero initial threshold signifies using defaults
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            if (newThr == 0) {
        
                float ft = (float)newCap * loadFactor;
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }
            threshold = newThr;
            @SuppressWarnings({
        "rawtypes","unchecked"})
            // 创建的数组的长度是32
            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;
                        if (e.next == null)
                            // 数组中的元素就一个 找到元素在新的数组中的位置 赋值
                            newTab[e.hash & (newCap - 1)] = e;
                        else if (e instanceof TreeNode)
                            // 移动红黑树节点
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                        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;
                                if ((e.hash & oldCap) == 0) {
        
                                    if (loTail == null)
                                        loHead = e;
                                    else
                                        loTail.next = e;
                                    loTail = e;
                                }
                                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;
        }

put搞明白了，剩下的就显得容易了  
看完添加了，再来看下删除：

## remove ##

解析都写在注释上了

public V remove(Object key) {
        
            //临时变量
            Node<K,V> e;
            /**调用removeNode(hash(key), key, null, false, true)进行删除，第三个value为null，表示，把key的节点直接都删除了，不需要用到值，如果设为值，则还需要去进行查找操作**/
            return (e = removeNode(hash(key), key, null, false, true)) == null ?
                null : e.value;
        }
        
        /**第一参数为哈希值，第二个为key，第三个value，第四个如果为false，则表示删除后，不移动节点，第五个为是为true的话，则表示删除它key对应的value，不删除key**/
        final Node<K,V> removeNode(int hash, Object key, Object value,
                                   boolean matchValue, boolean movable) {
        
            //tab 哈希数组，p 数组下标的节点，n 长度，index 当前数组下标
            Node<K,V>[] tab; Node<K,V> p; int n, index;
            //哈希数组不为null，且长度大于0，然后获得到要删除key的节点所在是数组下标位置
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (p = tab[index = (n - 1) & hash]) != null) {
        
                //nodee 存储要删除的节点，e 临时变量，k 当前节点的key，v 当前节点的value
                Node<K,V> node = null, e; K k; V v;
                //如果数组下标的节点正好是要删除的节点，把值赋给临时变量node
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    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 = e;
                                break;
                            }
                            /**注意，如果进入了链表中的遍历，那么此处的p不再是数组下标的节点，而是要删除结点的上一个结点**/
                            p = e;
                        } while ((e = e.next) != null);
                    }
                }
                //找到要删除的节点后，判断!matchValue，我们正常的remove删除，!matchValue都为true
                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;
                    //修改计数器
                    ++modCount;
                    //长度减一
                    --size;
                    /**此方法在hashMap中是为了让子类去实现，主要是对删除结点后的链表关系进行处理**/
                    afterNodeRemoval(node);
                    //返回删除的节点
                    return node;
                }
            }
            //返回null则表示没有该节点，删除失败
            return null;
        }

删除还有`clear方法，把所有的数组下标元素都置为null`，下面在来看看较为简单的获取元素与修改元素操作。

## get ##

public V get(Object key) {
        
            Node<K,V> e;
            //也是调用getNode方法来完成的
            return (e = getNode(hash(key), key)) == null ? null : e.value;
        }
     
        final Node<K,V> getNode(int hash, Object key) {
        
            //first 头结点，e 临时变量，n 长度,k key
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
            //头结点也就是数组下标的节点
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
        
                //如果是头结点，则直接返回头结点
                if (first.hash == hash && 
                    ((k = first.key) == key || (key != null && key.equals(k))))
                    return first;
                //不是头结点
                if ((e = first.next) != null) {
        
                    //判断是否是红黑树结构
                    if (first instanceof TreeNode)
                        //去红黑树中找，然后返回
                        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);
                }
            }
            //找不到，表示不存在该节点
            return null;
        }

代码注释不易，重要的也都看完了，点个赞呗

[75d46aa247d54dddba811c1c11af7229.png]: https://img-blog.csdnimg.cn/75d46aa247d54dddba811c1c11af7229.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY4ODk3Mw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/1c320ef518cb4083a8ad3a093e44dbc1.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY4ODk3Mw==,size_16,color_FFFFFF,t_70
[IDEA _ UML]: https://blog.csdn.net/weixin_44688973/article/details/119733370?spm=1001.2014.3001.5501
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY4ODk3Mw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/c4e776253f214d76a076e4e19da3b8f8.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY4ODk3Mw==,size_16,color_FFFFFF,t_70
[936cfa6cd50d4dbd9b3c691564014c2c.png]: https://img-blog.csdnimg.cn/936cfa6cd50d4dbd9b3c691564014c2c.png
[b11fc38dd30c4cc583e7499503a3c321.png]: https://img-blog.csdnimg.cn/b11fc38dd30c4cc583e7499503a3c321.png
[8960568c08074ccbbbf22e43d97c18d9.png]: https://img-blog.csdnimg.cn/8960568c08074ccbbbf22e43d97c18d9.png
[5d3a2835dbbb4837b7fdb0ad091c3e6b.png]: https://img-blog.csdnimg.cn/5d3a2835dbbb4837b7fdb0ad091c3e6b.png
[d484eb01e9804240956e7ed5d3f55dd8.png]: https://img-blog.csdnimg.cn/d484eb01e9804240956e7ed5d3f55dd8.png