Java HashMap【笔记】_从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点

Java HashMap【笔记】

原文链接：Java HashMap【笔记】

HashMap

HashMap 基本结构

HashMap 底层的数据结构主要是数组 + 链表 + 红黑树
其中当链表的长度大于等于 8 时，链表会转化成红黑树，当红黑树的大小小于等于 6 时，红黑树会转化成链表

类注释

1.允许 null 值，不同于 HashTable ，是线程不安全的

2.load factor 默认值是 0.75，是均衡了时间和空间损耗算出来的值，较高的值会减少空间开销，但增加了查找成本，不扩容的条件：数组容量大于需要的数组大小

3.如果有很多数据需要储存到 HashMap 中，那么建议 HashMap 的容量一开始就设置成足够的大小，这样可以防止在其过程中不断的扩容，影响性能

4.HashMap 是非线程安全的，可以通过在外部加锁，或者通过 Collections#synchronizedMap 来实现线程安全，Collections#synchronizedMap 的实现就是在每个方法上加上了 synchronized 锁

5.在迭代过程中，如果 HashMap 的结构被修改，会快速失败

基本属性

初始容量DEFAULT_INITIAL_CAPACITY

最大容量MAXIMUM_CAPACITY

负载因子DEFAULT_LOAD_FACTOR

链表长度TREEIFY_THRESHOLD

红黑树大小UNTREEIFY_THRESHOLD

数组容量MIN_TREEIFY_CAPACITY

HashMap新增

新增key，value（put（key，value））的步骤如下：

1.首先看一下空数组有没有初始化，如果没有的话就先初始化

2.如果可以通过 key 的 hash 直接找到值，那就直接跳转到第6步，要不就进行到第3步

3.看一下是什么情况，如果是 hash 冲突，进行解决，解决方案有两种，链表或者红黑树

4.如果是链表的话，就进行递归循环，把新元素追加到队尾

5.如果是红黑树的话，就调用红黑树新增的方法

6.通过第二步第四步以及第五步，就可以把新元素追加成功，然后再根据 onlyIfAbsent 判断是否需要覆盖

7.最后判断是否需要扩容，如果需要扩容的话，就进行扩容

具体流程

具体流程怎么个说呢，将参数，数组长度，数组索引下标啥的都设好以后，开始进行，如果数组为空，那么就是用resize方法进行初始化，如果当前的索引位置是空的，那就在当前的索引位置上直接生成新的节点，那么如果当前索引位置上有值的处理方法，我们就要看key的hash和值是不是都相等，如果都相等，那么就直接把当前下标位置的node值赋值给临时变量

如果是红黑树，就使用红黑树的方法进行新增，如果是个链表，就使用链表的新增方法，然后看一下是不是需要覆盖，只有在onlyIfAbsent 为 false 时，才会覆盖，然后记录一下HashMap的数据结构发生了变化，如果HashMap的实际大小大于扩容的门槛儿，就开始扩容，否则就结束

代码流程：

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)
        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);
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

链表的新增节点

链表的新增就是将当前节点追加到链表的尾部，和 LinkedList 的追加实现基本一样，从头开始遍历链表，当遍历到链表尾部时，把新节点放到链表尾部，链表遍历过程中，发现有元素和新增的元素相等，结束循环

需要注意的是，当链表长度大于等于 8 时，此时的链表就会转化成红黑树，链表转化红黑树的方法是：treeifyBin，此方法有一个判断，当链表长度大于等于 8，并且整个数组大小大于 64 时，才会转成红黑树，当数组大小小于 64 时，只会触发扩容，不会转化成红黑树

为什么链表的长度大于等于8就会有这种转化？

简单来说，就是在链表查询的时间复杂度，红黑树的时间复杂度以及泊松分布概率函数的综合考虑下，选取出一个边界值，需要在正常情况下不太可能出现的情况发生时进行性能的保证，如果真的出现了，那么可能就是hash算法出了问题，为了保持高性能，就需要转化红黑树

红黑树的新增节点

首先明确红黑树的原则：

1.节点是红色或黑色

2.根是黑色

3.所有叶子都是黑色

4.从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点

5.从每个叶子到根的所有路径上不能有两个连续的红色节点

过程如下：

1.首先判断新增的节点在红黑树上是不是已经存在，如果节点没有实现 Comparable 接口，使用 equals 进行判断，如果节点自己实现了 Comparable 接口，使用 compareTo 进行判断

2.新增的节点如果已经在红黑树上，直接返回，不在的话，判断新增节点是在当前节点的左边还是右边，左边值小，右边值大

3.自旋递归第一步和第二步，直到当前节点的左边或者右边的节点为空时，停止自旋，当前节点即为我们新增节点的父节点

4.把新增节点放到当前节点的左边或右边为空的地方，并于当前节点建立父子节点关系

5.进行着色和旋转，结束

红黑树的着色（给红黑树的节点上色）或旋转（让红黑树更加平衡）的情况：

着色：新节点总是为红色；如果新节点的父亲是黑色，则不需要重新着色，如果父亲是红色，那么必须通过重新着色或者旋转的方法，再次达到红黑树的原则

旋转： 父亲是红色，叔叔是黑色时，进行旋转，如果当前节点是父亲的右节点，则进行左旋，如果当前节点是父亲的左节点，则进行右旋

HashMap查找

HashMap 的查找主要分为以下三步：

第一步，根据 hash 算法定位数组的索引位置，equals 判断当前节点是否是我们需要寻找的 key，是的话直接返回，不是的话继续进行

第二步，判断当前节点有无 next 节点，有的话就进行判断，看一下是链表类型还是红黑树类型

第三步，分别走链表和红黑树不同类型的查找方法

链表查找的话，采用自旋的方式从链表中查找key，如果当前的节点hash等于key的hash，并且equals相等，那么当前的节点就是我们需要的节点，当hash冲突的时候，同一个hash值上是一个链表的时候，我们可以通过equals的方法来比较key是不是相等的，如果这个节点不是我们需要的，那么就把当前节点的下一个节点拿出来继续寻找

代码：

do {
    if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k))))
        return e;
} while ((e = e.next) != null);
1
2
3
4
5

红黑树的查找思路，先从根节点进行递归查找，然后根据hashcode来比较查找节点，左边的节点，右边节点的大小，根据红黑树的左边值小，右边值大来进行判断，然后判断查找节点有没有定位节点位置，有的话就返回，没有的话就重复上面操作，一直到自旋到定位节点位置为止

一些问题：

Map 的 hash 算法是怎么进行的？

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
1
2
3
4

如上代码是 HashMap 的hash 算法

说白了就是一个数学问题，源码中就是这样计算 hash 的，首先计算出 key 的 hashcode，因为 key 是 Object，所以会根据 key 的不同类型进行 hashcode 的计算，接着计算 h ^ (h >>> 16)

好处：大多数场景下，算出来的 hash 值比较分散

一般来说，hash 值算出来之后，要计算当前 key 在数组中的索引下标位置时，可以采用取模的方式，就是索引下标位置 = hash 值 % 数组大小

好处：可以保证计算出来的索引下标值可以均匀的分布在数组的各个索引位置上

此问题可以延伸出三个小问题：

1：为什么不用 key % 数组大小，而是需要用 key 的 hash 值 % 数组大小？

key 还有可能是字符串，是复杂对象，这时候用字符串或复杂对象 % 数组大小是肯定不行的，所以需要先计算出 key 的 hash 值

2：计算 hash 值时，为什么需要右移 16 位？

减少了碰撞的可能性

3：为什么把取模操作换成了 & 操作？

处理器对 & 操作就比较擅长，换成了 & 操作，是有数学上的证明的支撑，为了提高了处理器处理的速度

4：为什么提倡数组大小是 2 的幂次方？

因为只有大小是 2 的幂次方时，才能使 hash 值 % n(数组大小) == (n-1) & hash 公式成立。

HashMap 中出现 hash 冲突时怎么办？

简单地说，先试试扩容

hash 冲突指的是 key 值的 hashcode 计算相同，但 key 值不同的情况

如果元素原本只有一个或已经是链表了，新增元素直接追加到链表尾部

如果元素已经是链表，并且链表个数大于等于 8 时，此时有两种情况：如果此时数组大小小于 64，数组再次扩容，链表不会转化成红黑树，如果数组大小大于 64 时，链表就会转化成红黑树

在数组容量小的情况下冲突严重的话，我们可以先尝试扩容，看看能否通过扩容来解决冲突的问题