avatar

【JDK源码笔记】- HashMap的初始化

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

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

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

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

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

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

3aQLYq

这块涉及到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的幂, 则需要先进行减一操作

如图所示:
51Xhtj

最后执行的结果进行加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做&操作.

OAZssV

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

文章作者: liuzhihang
文章链接: https://liuzhihang.com/2020/05/11/source-code-hashmap-init.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Notes

评论