HashMap-源码解读

野性酷女 2023-09-30 22:00 10阅读 0赞

## 简介 ##

HashMap 的特点：

*  存取顺序无序
 *  键和值位置都可以是 null，但是键位置只能是一个 null
 *  键位置是唯一的，底层数据结构是：数组+链表+红黑树
 *  引入红黑树的目的是提高查询的速度

底层结构：

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

*  数组是一个 `Node<K,V>[]` 数组，这个数组也称为`哈希表`，表中的每个空间用于存放各链表或者红黑树的头节点，每一个子集合称为一个`哈希桶`。
 *  在往 `HashMap` 中添加元素的时候，会先通过 hash 算法得到该元素的索引位置，并以链表的形式添加其后
 *  当链表的长度大于等于 8，并且哈希表的长度大于 64 的时候，该链表会进化为 `红黑树`

## 源码解读 ##

`PS：HashMap 底层源码还是比较复杂的，建议通过 Debug 的方式去阅读源码`

首先我们可以看一下 HashMap 类的基本结构

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

public class HashMap<K,V> extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable {
        
    
        private static final long serialVersionUID = 362498820763181265L;
    	// 默认初始化容量 1×2^4 = 16
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
    	// 集合最大容量 1×2^30 = 10737411824
    	static final int MAXIMUM_CAPACITY = 1 << 30;
    	// 默认加载因子大小 0.75f
    	static final float DEFAULT_LOAD_FACTOR = 0.75f;
    	// hashMap的链表数组（哈希表，哈希桶）
    	transient Node<K,V>[] table;
    	// hashMap的大小
    	transient int size;
    	// 结构修改次数
    	transient int modCount;
    	// 扩容阈值
    	int threshold;
    	// 负载因子
    	final float loadFactor;
    
    	static class Node<K,V> implements Map.Entry<K,V> {
        
    		// hash 值
            final int hash;
            // 键
            final K key;
            // 值
            V value;
            // 后驱节点
            Node<K,V> next;
    
            Node(int hash, K key, V value, Node<K,V> next) {
        
                this.hash = hash;
                this.key = key;
                this.value = value;
                this.next = next;
            }
    
            ...
        }
    
    	// 方法
    	...
    }

从中我们可以看到 HashMap 类中有个内部类 `Node`，它是用于具体存放数据的类，`Node` 类中有四个属性 `hash`、`key`、`value` 和 `next`，它们分别存放 `hash 值（根据 key 通过算法计算得来）`、`键值对的键`、`键值对的值`和`后驱节点`，并且 `Node`类中重写了 `hashCode()` 和 `equals()` 方法。

`HashMap` 类有几个较为关键的属性，分别是：

*  Node<K,V>\[\] `table`：hashMap 的链表数组（哈希表，哈希桶）
 *  int `size`：hashMap的大小
 *  int `threshold`：扩容阈值
 *  float `loadFactor`：负载因子

接下来我大概解析下 HashMap 的这几个方法：

*  无参构造方法
 *  有参构造方法
 *  V put(K key, V value) 方法
 *  V get(Object key) 方法
 *  V remove(Object key) 方法

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

**无参构造方法**

/**
         * Constructs an empty <tt>HashMap</tt> with the default initial capacity
         * (16) and the default load factor (0.75).
         */
        public HashMap() {
        
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        }

它的无参构造方法中设置了`负载因子`的大小，跟进 `DEFAULT_LOAD_FACTOR` 可知负载因子为 `0.75f`

/**
         * The load factor used when none specified in constructor.
         */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;

`loadFactor` 加载因子的主要作用就是通过集合的大小计算出 `阈值`，在添加元素的时候，如果集合大小超过了这个 `阈值`，就会去扩容

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

**有参构造方法**

方法一：

public HashMap(int initialCapacity, float loadFactor) {
        
       		// 容量初始长度校验
            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;
            // 
            this.threshold = tableSizeFor(initialCapacity);
        }

hashMap 中哈希表的长度只能是 `2 的次方数`，并不会根据传进来的 `initialCapacity` 的值来创建指定大小的数组，而是需要通过 `tableSeizFor()` 这个方法去计算得到的值作为初始化数组的长度。`tableSeizFor()` 方法会返回一个大于等于当前 cap 的一个数字，而且该数字一定是 2 的次方数。

/**
         * Returns a power of two size for the given target capacity.
         */
        // 返回一个大于等于当前 cap 的一个数字，而且该数字一定是 2 的次方数
        static final int tableSizeFor(int cap) {
        
            int n = cap - 1;
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }

方法二：

/**
         * Constructs an empty <tt>HashMap</tt> with the specified initial
         * capacity and the default load factor (0.75).
         *
         * @param  initialCapacity the initial capacity.
         * @throws IllegalArgumentException if the initial capacity is negative.
         */
        public HashMap(int initialCapacity) {
        
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }

方法三：

/**
         * 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>.
         *
         * @param   m the map whose mappings are to be placed in this map
         * @throws  NullPointerException if the specified map is null
         */
        public HashMap(Map<? extends K, ? extends V> m) {
        
            this.loadFactor = DEFAULT_LOAD_FACTOR;
            putMapEntries(m, false);
        }

`initialCapacity` 是集合的`初始容量`。

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

**V put(K key, V value) 方法**

该方法的作用是：往 Map 集合中添加一对键值对数据 key-value

这个方法是 HashMap 中一个比较重要，也是比较复杂的方法，我先大概说下`put()`方法的逻辑：

*  在添加键值对前会先通过 key 计算出一个 hash 值
 *  如果是第一次添加数据，数组的长度会扩容到 16
 *  数据添加时会先通过数组长度和 hash 值计算出当前添加的数据应处于哪个索引上
    
     *  如果索引上没有节点，则创建新的节点将数据赋值该节点上并置于索引上
     *  如果索引上有节点，则遍历链表或者红黑树，对比 key 是否存在
        
         *  存在，则替换原 value 的值，结束方法
         *  不存在，则创建新的节点将数据赋值该节点上并挂载到链表或者红黑树后
 *  集合大小 + 1
 *  判断当前集合大小是否超过阈值
    
     *  超过，则扩容

OK，上源码：

/**
         * Associates the specified value with the specified key in this map.
         * If the map previously contained a mapping for the key, the old
         * value is replaced.
         *
         * @param key key with which the specified value is to be associated
         * @param value value to be associated with the specified key
         * @return the previous value associated with <tt>key</tt>, or
         *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
         *         (A <tt>null</tt> return can also indicate that the map
         *         previously associated <tt>null</tt> with <tt>key</tt>.)
         */
        public V put(K key, V value) {
        
            return putVal(hash(key), key, value, false, true);
        }

该方法中会先取键值对数据的 `key` ，通过 `hash()` 方法计算出一个 `hash值`。

static final int hash(Object key) {
        
            int h;
            // 如果 key 为 null 则 返回 0
            // 如果 key 不为 null 则将 hashCode 值无符号右移16位再进行异或操作 得到的值返回
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }

*  当 key `为 null` 时，得到的 `hash值` 为`0`
 *  当 key `不为 null` 时，该方法计算出的 `hash值` 是 `hashCode 无符号右移 16 位再进行异或操作计算出来的值`

> 这样计算 hash 值时为了让不同的 key 尽量避免得到相同的 hash 值，降低 hash 冲突  
> 哈希碰撞：两个元素的 key 计算的 hash 码值相同就会发生 hash 碰撞

跟进 `putVal()` 方法

/**
         * Implements Map.put and related methods
         *
         * @param hash hash for key
         * @param key the key
         * @param value the value to put
         * @param onlyIfAbsent if true, don't change existing value
         * @param evict if false, the table is in creation mode.
         * @return previous value, or null if none
         */
        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)
            	// 第一次扩容数组到16个空间
                n = (tab = resize()).length;
            // 通过(数组长度-1)和hash值进行 & 运算，得到当前键值对应存放的索引位置
            // 判断该索引位置上是否为空
            if ((p = tab[i = (n - 1) & hash]) == null)
            	// 为空则创建新的节点存放键值对数据并赋值在 tab[i] 索引处
                tab[i] = newNode(hash, key, value, null);
            else {
        
            	// 如果不为空，则表示当前索引位置已添加过节点
            	// 定义一些变量
                Node<K,V> e; K k;
                // 通过hash值和equals()方法比较索引位置上节点 p 的key是否和当前插入的一样
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    // 如果一样，则将 p 赋值给 e
                    e = p;
                // 判断索引位置上节点 p 是否为树节点    
                else if (p instanceof TreeNode)
                	// 将当前数据挂载到树上（方法内部也会通过 hash 和 equals 去对比 key）
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {
        
                	// 死循环遍历数组下的链表，每循环一次 binCount+1
                    for (int binCount = 0; ; ++binCount) {
        
                    	// 判断是否为链表的最后一个节点
                        if ((e = p.next) == null) {
        
                        	// 尾插法：如果是，则将节点挂载到当前链表后
                            p.next = newNode(hash, key, value, null);
                            // 判断当前链表上的节点是否大于或者等于8个
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            	// 如果是，则会进入当下方法对链表进行树化
                            	// treeifBin 方法还会去判断数组的长度是否小于 64，没有则会进行扩容
                                treeifyBin(tab, hash);
                            // 结束循环    
                            break;
                        }
                        // 如果链表上有节点的 key 和当前需存放键值对的 key 相同
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            // 结束循环
                            break;
                        // e 赋值给 p，这段代码可以理解为指针在链表上往下游
                        p = e;
                    }
                }
                // 判断 e 是否不为空
                if (e != null) {
         // existing mapping for key
                	// 不为空说明当前 key 已在 map 中存在
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                    	// 替换掉原来 key 所对应的 value 值
                        e.value = value;
                    // 该方法供子类实现，自己什么都不干   
                    afterNodeAccess(e);
                    // 返回原 value 值
                    return oldValue;
                }
            }
            // 修改次数+1
            ++modCount;
            // 判断集合大小是否大于它的阈值
            if (++size > threshold)
            	// 是，则进行扩容
                resize();
            // 该方法供子类实现，自己什么都不干
            afterNodeInsertion(evict);
            // 插入成功会返回 null
            return null;
        }

我已经将上面代码的注释尽可能写得较详细了，所以就不再写一遍该方法的逻辑，这里我就挑几个点深入：

*  通过 (n - 1) & hash 计算出当前元素应插入到哈希表中的哪个索引上
 *  newNode() 为创建节点的方法，同时也会将键值对的数据封装到该节点中
 *  resize() 方法为 `hashMap` 底层的扩容方法，在以下情况中会调用
    
     *  第一次添加元素，哈希表扩容至 16 格
     *  集合大小超过阈值，哈希表扩容为原数组长度的 2 倍
     *  执行 treeifyBin() 进行树化，未满足树化条件时
 *  treeifyBin() 链表树化的方法

> `(n - 1) & hash` 为什么这句代码能够得到当前元素应插入的索引位置？  
> 这里的 `n` 为哈希表的长度，假设哈希表的长度为 16，hash 值为 `5847`，即 15 & 5847  
> 15 ====== 0000 0000 0000 1111  
> 5847 === & 0001 0110 1101 0111  
> 计算结果： 0000 0000 0000 0111 ==> 为 7  
> 由此可见当两个数进行 `&` 运算的时候得到的结果一定是小于等于低位数

`newNode()` 方法源码：

// Create a regular (non-tree) node
        Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
        
            return new Node<>(hash, key, value, next);
        }

该方法就很简单，创建一个 `Node` 对象，然后进行赋值。

`resize()` 方法源码：

/**
         * Initializes or doubles table size.  If null, allocates in
         * accord with initial capacity target held in field threshold.
         * Otherwise, because we are using power-of-two expansion, the
         * elements from each bin must either stay at same index, or move
         * with a power of two offset in the new table.
         *
         * @return the table
         */
        final Node<K,V>[] resize() {
        
        	// 获取扩容前的哈希表 oldTab
            Node<K,V>[] oldTab = table;
            // 获取扩容前 table 的长度 oldCap
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            // 获取当前扩容的阈值 oldThr
            int oldThr = threshold;
            // 定义扩容后的 table 大小 newCap 和扩容之后的扩容阈值大小 newThr
            int newCap, newThr = 0;
            // 判断当前数组大小是否大于 0
            if (oldCap > 0) {
        
            	// 条件成立则表示 hashMap 中的散列表已经初始化过了，这是一次正常的扩容
            	// 判断扩容前的数组大小是否 >= 最大容量
                if (oldCap >= MAXIMUM_CAPACITY) {
        
                	// 将阈值设置到最大
                    threshold = Integer.MAX_VALUE;
                    // 不扩容，直接返回当前数组
                    return oldTab;
                }
                // 设置 newCap = oldCap × 2；新数组的长度为原来的2倍
                // 判断新数组长度是否小于最大容量，并且当前数组长度需要 >= 16
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    // 如果满足，新扩容阈值 = 原扩容阈值 × 2
                    newThr = oldThr << 1; // double threshold
            }
            // 	oldCap == 0，说明 hashMap 中的散列表是 null
            // 1. new HashMap(initCap,loadFactor);
            // 2. new hashMap(initCap);
            // 3. new HashMap(map); 并且 map 中有数据
            else if (oldThr > 0) // initial capacity was placed in threshold
            	// 新数组的长度 = tableSizeFor()方法计算出的扩容阈值，这个数一定是 2 的次方数
                newCap = oldThr;
            // oldCap == 0，oldThr == 0
            // new HashMap();	
            else {
                       // zero initial threshold signifies using defaults
            	// 数组大小 = 16
                newCap = DEFAULT_INITIAL_CAPACITY;
                // 扩容阈值 = 16 × 0.75 = 12
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            // 判读新的扩容阈值是否等于 0
            if (newThr == 0) {
        
            	// 通过 newCap 和 loadFactor 计算出一个扩容阈值
                float ft = (float)newCap * loadFactor;
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }
            // 设置 hashMap 新的扩容阈值
            threshold = newThr;
            // 压制警告
            @SuppressWarnings({
        "rawtypes","unchecked"})
            	// 根据 newCap 新建一个数组 newTab
                Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            // 新创建的数组赋值给 table    
            table = newTab;
            // 判断原哈希表是否为空
            if (oldTab != null) {
        
            	// 遍历原数组，进行数据迁移
                for (int j = 0; j < oldCap; ++j) {
        
                	// 当前 node 节点
                    Node<K,V> e;
                    // 将原数组中索引位置上的节点 oldTab[j] 赋值给 e
                    // 判断 e 是否为空
                    if ((e = oldTab[j]) != null) {
        
                    	// 如果 e 不为 null，说明在原数组中 j 处索引上是有数据的
                    	// 清空老数组中的数据，方便 JVM GC
                        oldTab[j] = null;
                        // 判断 e 的后驱节点为 null
                        if (e.next == null)
                        	// 是，则说明当前桶位只有一个元素，从未发生过 hash 碰撞，直接计算出当前元素应存放在新数组中的位置，然后扔进去即可
                            newTab[e.hash & (newCap - 1)] = e;
                        // 	判断当前节点是否已经树化    
                        else if (e instanceof TreeNode)
                        	// 作为红黑树的节点，调用split方法进行处理
                            ((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;
                            // 定义变量 next，表示当前链表的下一个节点
                            Node<K,V> next;
                            do {
        
                                next = e.next;
                                // 判断节点 e 是存放在低位链表还是高位链表上
                                if ((e.hash & oldCap) == 0) {
        
                                	//表明节点 e 为低位节点，将低位节点存放到低位链表上
                                    if (loTail == null)
                                        loHead = e;
                                    else
                                        loTail.next = e;
                                    loTail = e;
                                }
                                else {
        
                                	// 表明节点 e 为高位节点，将高位节点存放到高位链表上
                                    if (hiTail == null)
                                        hiHead = e;
                                    else
                                        hiTail.next = e;
                                    hiTail = e;
                                }
                            // 链表遍历结束，则跳出循环
                            } while ((e = next) != null);
                            // 判断低位链表尾节点是否存在
                            if (loTail != null) {
        
                            	// 将低位链表尾节点指向 null
                                loTail.next = null;
                                // 将低位链表挂载到原数组索引位置上
                                newTab[j] = loHead;
                            }
                            // 判断高位俩表尾节点是否存在
                            if (hiTail != null) {
        
                            	// 将高位链表尾节点指向 null
                                hiTail.next = null;
                                // 将高位链表挂载到(原数组索引 + 原数组大小)的索引位置上
                                newTab[j + oldCap] = hiHead;
                            }
                        }
                    }
                }
            }
            return newTab;
        }

> 为什么 HashMap 需要扩容？  
> 为了解决哈希冲突导致的链化影响查询效率的问题

这个方法会先去计算扩容后的哈希表长度 `newCap` 和扩容后的扩容阈值 `newThr`，根据 `newCap` 新键一个 `Node[] 数组` 作为扩容后的哈希表，再将原数组 `oldTab` 里面的元素迁移到新数组 `newTab` 中。

比较难理解的地方就是数据迁移那块代码了，分为三种情况：

*  第一种情况是`哈希桶`中只有`一个节点`，这种情况也是最简单的，可直接通过 `hash & (newCap - 1)` 来确定该节点在扩容后的数组中存放的位置，直接添加上去即可，该节点在新数组的坐标位置要么和原坐标位置相同，要么在原坐标的位置上加上原数组的长度
 *  第二中情况是哈希桶中存放的是`红黑树`，会调用 `split()` 方法进行处理
 *  第三种情况是哈希桶中存放的是`单链表`，就去遍历该链表中的元素，将这些元素通过 `hash & oldCap` 分为两组（低位链表和高位链表），将低位链表中的节点保存在`原索引`位置下，高位链表中的节点保存在`(原索引+原数组长度)` 计算得来的索引位置上

> 为什么能通过 `hash & oldCap` 将哈希桶中的子集分为高、低两组？  
> 因为哈希表的长度为 2n ，也就是说在进行 & 操作的时候得到的结果只可能是 `0` 或者`大于 0`，为 0 则加入低链表组，`大于 0` 则加入高链表组，例如：  
> 16 ====== 0000 0000 000`1` 0000  
> 5847 === & 0001 0110 110`1` 0111  
> 计算结果： 0000 0000 0001 0000==> 在第 5 位的两个数进行 & 运算只有两种结果，0 或 1  
> 这也间接说明了为何哈希表的长度`必须`是 2n 了

`treeifyBin()` 方法

/**
         * Replaces all linked nodes in bin at index for given hash unless
         * table is too small, in which case resizes instead.
         */
        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);
            }
        }

可以看到链表如果想要进化成 `红黑树` 结构，还必须要求哈希表的长度大于等于 `64`。

以上就是 HashMap 的 `put()` 方法的源码解读了，关于如何进化成红黑树，以及红黑树中怎么添加节点，就不放在本文赘述了，到时候再盘一盘红黑树的底层逻辑。

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

**V get(Object key) 方法**

该方法的作用是通过 key 来获取对应的 value 值的。

源码如下：

/**
         * Returns the value to which the specified key is mapped,
         * or {@code null} if this map contains no mapping for the key.
         *
         * <p>More formally, if this map contains a mapping from a key
         * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
         * key.equals(k))}, then this method returns {@code v}; otherwise
         * it returns {@code null}.  (There can be at most one such mapping.)
         *
         * <p>A return value of {@code null} does not <i>necessarily</i>
         * indicate that the map contains no mapping for the key; it's also
         * possible that the map explicitly maps the key to {@code null}.
         * The {@link #containsKey containsKey} operation may be used to
         * distinguish these two cases.
         *
         * @see #put(Object, Object)
         */
        public V get(Object key) {
        
            Node<K,V> e;
            return (e = getNode(hash(key), key)) == null ? null : e.value;
        }

可以看到该方法会先通过 hash() 方法计算出哈希值，然后再调用了 `getNode()` 方法

/**
         * Implements Map.get and related methods
         *
         * @param hash hash for key
         * @param key the key
         * @return the node, or null if none
         */
        final Node<K,V> getNode(int hash, Object key) {
        
        	// tab：引用当前 hashMap 的散列表
        	// first：桶位中的头元素
        	// e：临时节点
        	// n：table 数组长度
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
            // 判断 table 是否为空，并且定位的哈希桶里面是否有数据
            if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
        
                // 情况一：定位出来的桶位元素，就是需要 get 的数据
                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)
                    	// 从树节点中获取数据
                        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;
        }

*  先通过 `(n - 1) & hash` 定位坐标，获取对应的哈希桶
 *  如果桶位节点是 get 的目标节点，则直接返回
 *  不是，则分为两种情况
    
     *  红黑树，通过 `getThreeNode()` 方法获取目标节点，返回
     *  链表，通过遍历的方式获取目标节点，返回

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

**V remove(Object key) 方法**

该方法的作用就是移除指定 key 的数据。

/**
         * Removes the mapping for the specified key from this map if present.
         *
         * @param  key key whose mapping is to be removed from the map
         * @return the previous value associated with <tt>key</tt>, or
         *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
         *         (A <tt>null</tt> return can also indicate that the map
         *         previously associated <tt>null</tt> with <tt>key</tt>.)
         */
        public V remove(Object key) {
        
            Node<K,V> e;
            return (e = removeNode(hash(key), key, null, false, true)) == null ?
                null : e.value;
        }

方法内部其实是调用了 `removeNode()` 方法移除节点，`matchValue` 的参数为 `false`

/**
         * Implements Map.remove and related methods
         *
         * @param hash hash for key
         * @param key the key
         * @param value the value to match if matchValue, else ignored
         * @param matchValue if true only remove if value is equal
         * @param movable if false do not move other nodes while removing
         * @return the node, or null if none
         */
        final Node<K,V> removeNode(int hash, Object key, Object value,
                                   boolean matchValue, boolean movable) {
        
            // tab：引用当前 hashMap 中的散列表
            // p：当前 node 元素
            // n：表示散列表数组长度
    		// index：表示寻址结果
            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：表示查找到的结果
                // e：表示当前 node 的后驱节点
                Node<K,V> node = null, e; K k; V v;
                // 情况一：定位出来的桶位元素，就是需要 remove 的数据
                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 = e;
                        } while ((e = e.next) != null);
                    }
                }
                // node 不为空，表示获取到需要删除的数据
                // 看是否满足删除的条件
                if (node != null && (!matchValue || (v = node.value) == value ||
                                     (value != null && value.equals(v)))) {
        
                    // 判断节点是否为树节点                 
                    if (node instanceof TreeNode)
                    	// removeTreeNode() 方法删除节点
                        ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                    // 删除的为链表中的首位元素 
                    else if (node == p)
                    	// 将 node 节点的后驱节点作为头节点
                        tab[index] = node.next;
                    else
                    	// 将 node 节点的后驱节点作为当前节点的后驱节点
                        p.next = node.next;
                    // 修改次数+1
                    ++modCount;
                    // 集合大小-1
                    --size;
                    // 供子类实现的方法
                    afterNodeRemoval(node);
                    return node;
                }
            }
            return null;
        }

该方法的大概逻辑就是先找到需要删除的 node 节点，然后判断是否满足删除的条件，根据节点的位置 `remove` 节点数据。

[c31f5898dd8347aebaa3035dbfd4957a.png]: https://img-blog.csdnimg.cn/c31f5898dd8347aebaa3035dbfd4957a.png
[ad3fd385ea654dca898f04eadb6588fb.png]: https://img-blog.csdnimg.cn/ad3fd385ea654dca898f04eadb6588fb.png