JDK1.8中HashMap实现

Myth丶恋晨 2024-02-19 16:57 55阅读 0赞

JDK1.8中的HashMap实现跟JDK1.7中的实现有很大差别。1.7和1.7之前HashMap都是“数组+链表”实现的，1.8之后就是“数组+（链表或红黑树）”来实现的了。

### 划重点： ###

JDK1.8中HashMap与JDK1.7中有很多地方不一样

1、1.8中引入了红黑树，而1.7中没有

2、1.8中元素是插在链表的尾部，而1.7中新元素是插在链表的头部

3、扩容的时候，1.8中不会出现死循环，而1.7中容易出现死循环，而且链表不会倒置

###  ###

### 一.红黑树介绍 ###

1.二叉查找树介绍

在介绍红黑树之前我们要先理解二叉查找树的数据结构。下面简单介绍一下。

![format_png][]

上面这张图就是一个二叉查找树。二叉查找树有如下几条特性

（1）.左子树上所有结点的值均小于或等于它的根结点的值。

（2）.右子树上所有结点的值均大于或等于它的根结点的值。

（3）.左、右子树也分别为二叉排序树

那既然他名字中是有“查找”的，那么他是怎么查找的呢？比如我们要查找10这个元素，查找过程为：首先找到根节点，然后根据二叉查找树的第一二条特性，我们知道要查找的10>9所以是在根节点的右边去查找，找到13，10<13,所以接着在13的左边找，找到11,10<11,继续在11的左边查找，这样就找到了10.这其实就是二分查找的思想。最后我们要查出结果所需的最大次数就是二叉树的高度！（二分查找的思想:找到数组的中间位置的元素v，将数组分成>v和<v两部分，然后将v和要查找的数据进行一个比较，如果大于v那么就在>v的部分再次进行二分查找，否则就在<v的部分进行二分查找，直到找到对应的元素。）

那既然要查出结果所需的最大次数就是二叉树的高度，那这个高度会不会有时候很长呢？

比如我们依次插入 根节点为9如下五个节点：7,6,5,4,3。依照二叉查找树的特性，结果会变成什么样呢？7,6,5,4,3一个比一个小，那么就会成一条直线，也就是成为了线性的查询，时间复杂度变成了O（N）级别。为了解决这种情况，该红黑树出场了。

2.红黑树介绍

红黑树其实就是一种**自平衡**的二叉查找树。他这个自平衡的特性就是对HashMap中链表可能会很长做出的优化。

红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:

性质1. 节点是红色或黑色。

性质2. 根节点是黑色。

性质3 每个叶节点（NIL节点，空节点）是黑色的。

性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

下面这棵树就是一个典型的红黑树

![format_png 1][]

红黑树那么多规则，那么在插入和删除元素会不会破坏红黑树的规则呢？什么情况下会破坏？什么情况下不会？

比如我们向原红黑树插入为14的新节点就不会破坏规则

![format_png 2][]

向原红黑树插入值为21的新节点就破坏了规则

![format_png 3][]

那么红黑树是怎么维护这个二叉查找树的自平衡性的呢？

红黑树通过**“变色”和“旋转”**来维护红黑树的规则，变色就是让黑的变成红的，红的变成黑的，旋转又分为“左旋转”和“右旋转”。这个比较复杂，容易晕，我们就只要知道红黑树就是通过这种方式来实现它的自平衡性就行了。

### 二.HashMap中是怎么使用红黑树的？ ###

JDK1.7的时候是使用一个Entry数组来存储数据，用key的hashcode取模来决定key会被放到数组里的位置，如果hashcode相同，或者hashcode取模后的结果相同（hash collision），那么这些key会被定位到Entry数组的同一个格子里，这些key会形成一个链表。在hashcode特别差的情况下，比方说所有key的hashcode都相同，这个链表可能会很长，那么put/get操作都可能需要遍历这个链表。也就是说时间复杂度在最差情况下会退化到O(n)

红黑树我们大致了解了，他的好处就是他的自平衡性，让他这棵树的最大高度为2log(n+1)，n是树的节点数。那么红黑树的复杂度就只有 O(log n)。

下面我们通过追踪JDK1.8 HashMap的put方法的源码来理解

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

put方法调用了putVal方法

static final int TREEIFY_THRESHOLD = 8;
    
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    //以看到这里的数组和1.7不同，是使用了一个Node数组来存储数据。
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                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);
    //如果超过了8个，那么会调用treeifyBin函数，根据数组长度，判断是否需要将链表转换为红黑树。 
                        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;
    }

通过putVal方法可以看到这里的数组和1.7不同，是使用了一个Node数组来存储数据。那这个Node和1.7里面的Entry的区别是什么呢？

![format_png 4][]

HashMap中的红黑树节点 采用的是TreeNode 类

![format_png 5][]

![format_png 6][]

TreeNode和Entry都是Node的子类，也就说Node可能是链表结构，也可能是红黑树结构。

如果插入的key的hashcode相同，那么这些key也会被定位到Node数组的同一个格子里。如果同一个格子里的key不超过8个，使用链表结构存储。如果超过了8个，那么会调用treeifyBin函数，treeifyBin函数中，如果数组长度>64，链表才变变为红黑树，否则扩容处理。

### 疑问： ###

为什么在链表长度>=8并且数组长度>64，链表才变变为红黑树？

因为树节点所占空间是普通节点的两倍，所以只有当节点足够多的时候，才会使用树节点。根据统计，链表中节点数是8的概率已经接近千分之一，而且此时链表的性能已经很差了。所以在这种比较罕见和极端的情况下，才会把链表转变为红黑树。因为链表转换为红黑树也是需要消耗性能的，特殊情况特殊处理，为了挽回性能，权衡之下，才使用红黑树，提高性能。也就是大部分情况下，hashmap还是使用的链表，如果是理想的均匀分布，节点数不到8，hashmap就自动扩容了。为什么这么说呢，再看下图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzM3MTQ3MDcw_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzM3MTQ3MDcw_size_16_color_FFFFFF_t_70 1][]

在链表转变为红黑树方法中，有这样一个判断，数组长度小于MIN\_TREEIFY\_CAPACITY，就会扩容，而不是直接转变为红黑树，可不是什么链表长度为8就变为红黑树，要仔细看代码哟，还有别的条件呢。

### 下面源码分析JDK1.8中的实现，主要看put和get方法。 ###

> ![format_png 7][]
> 
> ![format_png 8][]

构造方法的时候并没有初始化，而是在第一次put的时候初始化

> ![format_png 9][]

putVal方法的主要逻辑是这样的：

1、如果数组还没有初始化（数组长度是0），则先初始化

2、通过hash方法计算key的hash值，进而计算得到应该放置到数组的位置

3、如果该位置为空，则直接放置此处

4、如果该位置不为空，而且元素是红黑树，则插入到其中

5、如果是链表，则遍历链表，如果找到相等的元素则替换，否则插入到链表尾部

6、如果链表的长度大于或等于8，那么会调用treeifyBin函数，根据数组长度，判断是否需要将链表转换为红黑树。

> ![format_png 10][]

1、计算hash求位置

2、看第一个元素是不是要找的，是则返回，否则遍历

> ![format_png 11][]

扩容就是将旧数组的元素移动到新数组

### 总结： ###

1、HashMap底层是用数组+双向链表+红黑树实现的

2、插入元素的时候，首先通过一个hash方法计算得到key的哈希值，进而计算出待插入的位置

3、如果该位置为空，则直接插入（包装成Node）

4、如果该位置有值，则依次遍历。比较的规则是，hash值相同，key值相等的元素视为相同，则用新值替换旧值并返回旧值。

5、如果该位置的元素是红黑树结构，则同理，查找，找到则替换，没找到则插入。

[format_png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/31c656e2761f4725aef9e686ede976f2.png
[format_png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/b66eef0d2f9143199273f11038e7f21f.png
[format_png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/46846e8745b04e0f83351a170183efca.png
[format_png 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/8386b532b2c04bc39b440fa38238f577.png
[format_png 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/aef9267171884f21a086ab6ef6d8c68d.png
[format_png 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/c6329398f6ca40b787607b21decaa66a.png
[format_png 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/07a75e5b372c417290efd5c8812784b6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzM3MTQ3MDcw_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/f6ab7ca8ef2d4c48a5d23bd640eccddb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzM3MTQ3MDcw_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/cd726545e3794d9fae12eca8969d6680.png
[format_png 7]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/5dfc511bcd214d3a98159088e835ad3f.png
[format_png 8]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/285089a8d5c94bfea60760dd73ab5573.png
[format_png 9]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/090aa49027644c7d8b494574ce5b891e.png
[format_png 10]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/195a0ff355df4658934a357cee599659.png
[format_png 11]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/6130f6a20d384e369e75ec5929c25427.png