Java之HashMap经典算法

1. 得到最接近(>=)cap的2的次幂

int tableSizeFor(int cap)

// 限定最大容量2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
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;
}
1
2
3
4
5
6
7
8
9
10
11

注解：

1. MAXIMUM_CAPACITY容量之所以设为2³⁰而不是2³¹原因在于int的范围是 -2³¹~2³¹-1，所以会越界(容量是要为 2ⁿ)
2. >>是 带符号 右移，即按照二进制把数字右移指定数位，高位如符号位为正补 0，符号位负补 1，低位直接移除
   >>>是 无符号 右移，即按照二进制把数字右移指定数位，高位直接补零，低位移除。
   负数 都会变成1111 1111 1111 1111 1111 1111 1111 1111 (在计算机中，负数采用补码的形式储存)，即 -1，最后返回最接近的2的次幂为 1
   正数 最后都会变为 1111 .... 的形式
3. n + 1 目的是得到2的次幂的值，当二进制全为1时，例如：1111 此时加上 1 就会变成 10000 这种形式，必为 2的次幂
4. n = cap - 1 目的是若刚好cap为2的次幂，则最后处理完得到的是原值，假设不做处理：cap为4，二进制是100，处理完是111，+1后就变为1000，最后得到的是8而不是4

总结：

关键还是利用了二进制的特性，二进制最高位为1，后面全为0，则必定是2的次幂(2⁰-1、2¹-10、2²-100、2³-1000、…)，所以该数若不为2的次幂，则在该数最高位前加1，后全补0，则为最接近该数的二的次幂(9-1001 ---- 16-10000)。

2. 对键值表和扩容阈值一起进行扩容

Node[] resize()

不超范围的情况下都扩容2倍

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) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 如果旧表长度超过默认最大长度
            // 扩容阈值直接是int范围最大值,意味着不能再扩容
            threshold = Integer.MAX_VALUE;
            return oldTab;
        } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 如果旧表长度的2倍<默认最大长度 && 旧表长度>=默认初始化容量
            // 此时，newCap 被赋值为 旧表长度的2倍
            // 新表的扩容阈值调整为 旧的2倍
            newThr = oldThr << 1;
    } else if (oldThr > 0)
        // 如果旧表为null 但有扩容阈值
        // 新表大小直接为 旧表的扩容阈值
        newCap = oldThr;
    else {
        // 旧表为null && 扩容阈值为0 新表设默认值
        // 新表的大小 16
        newCap = DEFAULT_INITIAL_CAPACITY;
        // 扩容阈值 16*0.75 = 12
        newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 针对 旧表为null 但有扩容阈值 情况
    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"})
    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)
                	// 注解 1
                    newTab[e.hash & (newCap - 1)] = e;
                    // 桶里为树结构
                else if (e instanceof HashMap.TreeNode)
                    ((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    // 桶里是链表
               	else {
                    // 将旧桶里的链表拆分到新表当中
                    // 注解 2
                    HashMapCase.Node<K, V> loHead = null, loTail = null;
                    HashMapCase.Node<K, V> hiHead = null, hiTail = null;
                    HashMapCase.Node<K, V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            // 满足该条件时，旧表哈希对应的位置等于新表哈希对应的位置
                            // 注解 3
                            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;
                        // 旧表哈希移动到新表偏移位置
                        // 注解 4
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

注解：

1. newTab[e.hash & (newCap - 1)] = e;
   使哈希分布在表的位置更平均

   newCap为2的次幂 - 1 = (二进制)1111...
   所以与hash做 &运算 时，就会有2^n种可能，使分布更加平均
   并且newCap-1也能防止数组越界，因为 &运算 后可能得到原值
   但有个问题：下一次哈希进来不会覆盖原来的值吗？
   不会，因为hash进行&运算后要么在 j 要么在 j+oldCap 位置
   1
   2
   3
   4
   5

2. 将旧桶里的链表拆分到新表当中
   
3. (e.hash & oldCap) == 0
   满足该条件时，旧表哈希对应的位置等于新表哈希对应的位置
   推导：

    前提：e.hash & oldCap = 0
    结论：e.hash & (oldCap - 1) = e.hash & (2*oldCap - 1)
    例如   oldCap-1 = 00111
    那么 2*oldCap-1 = 01111
    所以若想 & 运算使两式相等 -> hash要为 00..xxx (为1的位数顶多为后三位)
    所以若 e.hash & oldCap = 0
    那么oldCap为1的位置必为0 -> ...x0xxx
    对比看一下 ->
                 oldCap - 1 = 00111
               2*oldCap - 1 = 01111
                  e.hash = ...x0xxx
    所以最后影响结果的都是后三位                      
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12

4. newTab[j + oldCap] = hiHead;
   旧表哈希移动到新表偏移位置
   推导：

    假设：             oldCap-1 = 0111
    所以：           2*oldCap-1 = 1111
    前提：两值不想等,所以哈希必为 ...x1xxx
    因为：hash &运算 后三个值必定相等
    所以：哈希对应新表位置为 在旧表对应位置 j 的二进制前面加个1
    	  即 hash & 2*oldCap-1 = 1111 & ...x1xxx = 1000 + j
    化为二进制刚好就是加上 oldCap
   1
   2
   3
   4
   5
   6
   7

总结：

这也解释了为什么每次扩容要为2ⁿ次方了，因为可以利用他的二进制做很多事情：

1. 2ⁿ-1 二进制全为1，与任何数做 &运算 得到的范围都在 0~2ⁿ-1，等价于取模，而且位运算更快。
2. 扩容后的大小二进制实际就 高位增加了1，所以在与hash做 &运算 后只要判断任何hash的该位 是否为1 就能知道扩容前后对应位置是否一致，若不一致也能找到新的位置，因为无非就是二进制中最高位多了个1。