HashMap初始化

HashMap初始化参数都是什么？默认是多少？ 为什么建议初始化设置容量？ tableSizeFor方法是做什么的？ 如何获取到一个key的hash值？及计算下标？

HashMap初始化参数都是什么？默认是多少？

HashMap初始化参数分别是初始容量和负载因子。
初始容量(threshold)：默认 16， 必须是2的幂， 最大容量为 1 << 30
负载因子(loadFactor)：是指哈希表的负载因子，当哈希表的长度大于capacity * loadFactor时会进行扩容，默认 0.75f

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

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

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即可

如何获取到一个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);
}

获取到了hash值， 那如何计算在数组的那个位置呢？

// n为数组长度  数组下标
i = (n - 1) & hash

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

通过图可以看出, 参与运算的只有低x位, 相当于之前的所有值都不会有效. 所以前面的hash(key) 将key.hashCode()高低16位做^操作, 可以保证, 高低16位都能参与运算.一定程度上避免hash碰撞.在源码注释中已经说明, 是肯定会有碰撞, 但是这是权衡之后的结果.