别再问HashMap原理和扩容机制了一篇彻底搞定HashMap源码

小灰灰 2022-12-17 08:39 124阅读 0赞

### 文章目录 ###

*   *  HashMap结构
     *  存放的key-value的Node节点
     *  看懂一条语句
     *  几个核心参数
     *  初始化方法
     *  核心方法 public V get(Object key)
     *  核心方法 public V put(K key, V value)
     *  核心方法V remove(Object key)
     *  核心方法Node K,V \[\] resize()
     *  初始化时候调用resize
     *  扩容调用resize 重点来了
     *  扩容中读懂一行代码

## HashMap结构 ##

数组+链表+红黑树  
链表大于8转红黑树，红黑树节点数小于6退回链表。  
![在这里插入图片描述][20201024225357324.png_pic_center]

## 存放的key-value的Node节点 ##

static class Node<K,V> implements Map.Entry<K,V> { 
            final int hash;
            final K key;
            V value;
            Node<K,V> next;
        }

树形结构的Node节点

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { 
            TreeNode<K,V> parent;  // red-black tree links
            TreeNode<K,V> left;
            TreeNode<K,V> right;
            TreeNode<K,V> prev;    // needed to unlink next upon deletion
            boolean red;
     }

他的继承结构是这样，可以看到继承了Node节点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center]

## 看懂一条语句 ##

hash & tab.length-1

代码中多处都可以看到这条代码，实际上这条语句只是做了一个取余（%）的动作。一个&怎么做的取余的操作：  
**HashMap的容量为2^n**其二进制结构如下

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

任何数&2^n-1（01111…）其结果都是去& 0xxxx，将值代表容量的二进制以及更高的二进制位都置为0。所有权重高于数组容量的都变成了0，可以想象剩下的所有低二进制位相加都不会大于容量值。做快速取余的操作。  
后续会看到该条语句频繁出现  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70]

## 几个核心参数 ##

*  Node<K,V>\[\] table：存放Node的数组
 *  int size：表示当前HashMap包含的键值对数量
 *  int threshold：表示当前HashMap能够承受的最多的键值对数量，一旦超过这个数量HashMap就会进行扩容
 *  final float loadFactor：负载因子，用于扩容
 *  int DEFAULT\_INITIAL\_CAPACITY = 16：默认的table初始容量
 *  float DEFAULT\_LOAD\_FACTOR = 0.75f：默认的负载因子
 *  int TREEIFY\_THRESHOLD = 8: 链表长度大于该参数转红黑树
 *  int UNTREEIFY\_THRESHOLD = 6: 当树的节点数小于等于该参数转成链表

## 初始化方法 ##

指定了具体的容量，以及负载因子的初始化方法。**当知道需要放入的元素的个数时可以先指定避免多次扩容造成性能浪费。**

public HashMap(int initialCapacity) { 
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }  
    public HashMap(int initialCapacity, float loadFactor) { 
            this.loadFactor = loadFactor;
            this.threshold = tableSizeFor(initialCapacity);
    }

## 核心方法 public V get(Object key) ##

参数key，以及该key的hash  
先判断数组是否已经初始化了，以及数组长度。  
在判断tab\[(n - 1) & hash\]，前文提到的那一条语句，用key的hash取余数组长度判断数组中的位置是否存在元素。

*  不存在元素  
    数组中不存在元素，肯定没有产生hash冲突，那么元素肯定不存在
 *  数组当前位置存在元素  
    判断key的hsah相等并且（key的地址相等或者equals相等）。那么可以确定元素在数组中。
 *  数组当前位置存在元素，但是key不相等  
    接下来会去判断数组中当前位置是否存在next元素（Node节点结构），如果有next说明存在链表或者树形结构。  
    接下来判断Node是否是TreeNode，如果是则按照遍历树方式遍历得到结果，不是则按照遍历链表的形式遍历得到结果。

final Node<K,V> getNode(int hash, Object key) { 
            Node<K,V>[] tab = table; 
            Node<K,V> first = tab[(n - 1) & hash]; 
            Node<K,V> e = first.next; 
            int n = tab.length; 
            K k;
            //数组是否已经初始化
            if (tab!= null && n > 0 && first != null) { 
                //table中是否有节点，key是否相等
                if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
                    return first;
                //key不相等，判断是否有next，并且判断是树的节点还是链表的节点，再以不同的方式去遍历获取
                if (e != 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;
        }

## 核心方法 public V put(K key, V value) ##

put方法比较长，分几种情况解析

*  第一次put元素，数组还未初始化：调用resize()初始化数组，直接放入table相应位置。(resize扩容方法很重要)
 *  table中该位置没产生Hash冲突：构造节点放入table中
 *  产生Hash冲突，先判断table中节点元素key是否相等，相等则替换value
 *  产生Hash冲突，节点是TreeNode：按红黑树的方式插入节点
 *  产生Hash冲突，节点是Node：构造节点按链表的方式插入，并且检查插入后是否到达转红黑树的阈值8

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { 
            Node<K,V>[] tab; 
            Node<K,V> p; 
            int n;
            int i;
            //第一次put元素，数组还未初始化
            if ((tab = table) == null || (n = tab.length) == 0)
                //调用resize()初始化数组
                n = (tab = resize()).length;
             //table中该位置没产生Hash冲突
            if ((p = tab[i = (n - 1) & hash]) == null)
                //构造节点放入table中
                tab[i] = newNode(hash, key, value, null);
            else { 
                //产生Hash冲突
                Node<K,V> e; K k;
                //table中节点元素key是否相等
                if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                    //记录下节点的引用，后续替换E节点的值
                    e = p;
                else if (p instanceof TreeNode)
                    //节点是TreeNode：按红黑树的方式插入节点
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else { 
                    //节点是Node，链表情况
                    for (int binCount = 0; ; ++binCount) { 
                        //遍历到链表尾部还未发现相同的key,则构造节点插入到链表
                        if ((e = p.next) == null) { 
                            p.next = newNode(hash, key, value, null);
                            if (binCount >= TREEIFY_THRESHOLD - 1)
                                //检查插入后是否到达转红黑树的阈值8
                                treeifyBin(tab, hash);
                            break;
                        }
                        //检查是否有相同的key,有就退出，e = p.next已经记录了E的引用
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
                //上述各种情况下，如果不是插入节点的情况下
                //存在key相同的情况下，完成一个值的替换
                if (e != null) { 
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    return oldValue;
                }
            }
            //检查是否需要扩容 存在的数量>hashmap容量*负载因子就需要扩容
            if (++size > threshold)
                resize();
            return null;
        }

## 核心方法V remove(Object key) ##

移除节点，先找到要移除的节点记录下来。无非分为以下三种情况

*  移除的节点在数组中
 *  移除的节点在链表中
 *  移除的节点在红黑树中

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;
            //做一些简单的赋值和判断，hash取余数组容量如果数组该位置没元素，那更不可能存在链表和红黑树直接return null
            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 = 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节点为链表中需要移除节点的前驱
                            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)
                        //红黑树移除节点
                        ((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;
                }
            }
            return null;
        }

## 核心方法Node K,V \[\] resize() ##

最重要的部分来了，也是面试官最喜欢问的HashMap的扩容

1.  第一次初始化时候调用
2.  存放的键值对的数量>hashmap容量\*负载因子就需要扩容

## 初始化时候调用resize ##

扩容后得到的是一个Node数组。由于第一次初始化，肯定是不存在链表，红黑树等结构的，以及Node节点的。只是对一些属性做了赋值操作，和返回一个空的Node数组。  
**threshold**：HashMap能够承受的最多的键值对数量；如果指定了容量和负载因子，则threshold = 指定的容量\*负载因子；  
**Node<K,V>\[\] table**：存放Node的数组，创建了一个容量为16（未指定具体容量时，默认为16）的Node数组。![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 1]  
省略部分与第一次初始化无关代码不重要的代码

final HashMap.Node<K,V>[] resize() { 
            //16*0.75=12
            threshold = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            //16
            HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[DEFAULT_INITIAL_CAPACITY];
            table = newTab;
            return newTab;
        }

## 扩容调用resize 重点来了 ##

先删除一些与扩容无关的代码

final Node<K,V>[] resize() { 
            Node<K,V>[] oldTab = table;
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            int oldThr = threshold;
            int newCap, newThr = 0;
            if (oldCap > 0) { 
                //容量和阈值都扩大成两倍
                newCap = oldCap << 1;
                newThr = oldThr << 1;
            }
            //设置阈值属性
            threshold = newThr;
            //新建一个是之前两倍容量的大小的Node数组
            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) { 
                        //数据需要迁移，table相应位置置空
                        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 { 
                            //不需要移动的链表的头尾指针
                            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);
                            //将链表重新放入table数组中
                            if (loTail != null) { 
                                loTail.next = null;
                                newTab[j] = loHead;
                            }
                            if (hiTail != null) { 
                                hiTail.next = null;
                                newTab[j + oldCap] = hiHead;
                            }
                        }
                    }
                }
            }
            return newTab;
        }

这里主要分析一下拆分的依据。  
当要将链表中的数据进行拆分，并且分配到不同的table下标中。可以明确的是，不能因为扩容影响到get方法，所以根据get方法key的hash取余容量可以得到如下两张图片。  
**未拆之前**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 2]  
**拆之后**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 3]

## 扩容中读懂一行代码 ##

(e.hash & oldCap) == 0

当元素的hash &oldCap（前文提到过容量为2^n，其二进制为1000…）。  
看几个例子  
5&16 ==0  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 4]  
21&16 ！=0  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 5]  
69&16 ==0  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 6]

**Hash值的结构以红色框为中心：可以看成 左边Y+table容量+右边X，Y是容量的偶数倍数，X小于容量值**，从上述例子中可以看出来结果是否为0取决于红色框处是0还是1，即Hash值中权重等于数组容量的位为0还是1。

*  为0结果恒为0  
    Y是容量的偶数倍数扩容后取余为依旧0，余数为X，余数与扩容之前一致，不需要移动。
 *  为1时结果不为0  
    Y是容量的偶数倍数扩容后取余为依旧0，余数为容量值+X，扩容后余数与之前不一致，需要移动，移动后的位置为容量+X（之前所在位置的值）。

[20201024225357324.png_pic_center]: /images/20221122/71282623099f4f4587396a4c0af60bac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221122/6dac193245e64dc2bfec4478cd88b50f.png
[20201226152258506.png]: /images/20221122/36e6405fda084cb2abed6d00c66d96c8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70]: /images/20221122/954904b4632a4a7a9800ca30433c2962.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221122/2ad47c9f23ef43af8b07e13dcecd4806.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221122/7742f1e74a9140b29b3d11402b64f454.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221122/d6781eef6d434082afeff2876c93da3c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221122/c2488c86a147447cb7f95507dafa6bc5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221122/72889f97b3684c83af1cbda819e1f335.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221122/318a0905b60c44fea28cfa0a759381ef.png