HashMap的初始化，到底都做了什么？

刘志航

1、HashMap初始化参数都是什么?默认是多少?

2、为什么建议初始化设置容量?

3、tableSizeFor方法是做什么的?

4、如何获取到一个key的hash值?及计算下标?

1

HashMap初始化参数？

HashMap初始化参数分别是初始容量和负载因子。

初始容量(threshold)：默认16，必须是2的幂，最大容量为 1 << 30。

负载因子(loadFactor):是指哈希表的负载因子，当哈希表的长度大于capacity * loadFactor时会进行扩容，默认 0.75f。

2

为什么建议初始化设置容量？

这块涉及到HashMap的扩容，在《阿里巴巴Java开发手册》中已经说明了原因。主要是为了减少频繁的扩容造成的资源损耗。

3

tableSizeFor方法是做什么的?

初始化HashMap时，如果传入初始容量，在初始化时会调用 tableSizeFor(initialCapacity) 方法寻找大于等于当前值的下一个2的幂值。

代码如下:

static final int tableSizeFor(int cap) {
    int n = cap - 1; //  -1操作, 防止当cap正好是2的幂时的处理
    n |= n >>> 1; // n无符号右移1位, 然后和n做 | 运算, (1|0=1 1|1=1 0|0=0 0|1=1)
    n |= n >>> 2; // n无符号右移2位, 然后和n做 | 运算,
    n |= n >>> 4; // n无符号右移4位, 然后和n做 | 运算,
    n |= n >>> 8; // n无符号右移8位, 然后和n做 | 运算,
    n |= n >>> 16; // n无符号右移16位, 然后和n做 | 运算,

    // 最后获得的结果为 cap-1的下一个2的幂值-1, 只需要对n+1即可
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

1. 假设cap值为100，即0110 0100
2. cap的下一个2的幂为 0111 1111 即 1000 0000
3. 0000 = 0111 1111 + 1
4. 只需要考虑将 首个为1的最高位之后的值置为1，然后+1即可
5. 为防止cap本来就是2的幂，则需要先进行减1操作

如图所示:

最后执行的结果进行加1即可。

4

如何获取到一个key的hash值?

static final int hash(Object key) {
    int h;
    // key的hashCode ^ 上自己的高16位, 如果是null的话则hash为0
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

数组长度都是 2的幂，假设 n = 1 >> x，则 n - 1 则表示 一个低x位全为1的数(n - 1) & hash 则相当于 一个低x位全为1的数和hash做&操作。

如图所示：

通过图可以看出：

参与运算的只有低x位，相当于之前的所有值都不会有效。

所以前面的hash(key) 将key.hashCode()高低16位做^操作，可以保证，高低16位都能参与运算。

一定程度上避免hash碰撞.在源码注释中已经说明，是肯定会有碰撞，但是这是权衡之后的结果。

- <End /> -