为什么 HashMap 长度必须是 2 的 n 次幂
Java 面试 大约 725 字2 的 n 次幂
1
后面n
个0
如:
2^3
= 1000
2^6
= 1000000
取索引的算法
取索引的算法是对hash
值取模:hash%length
,而直接取模%
性能比位运算差,所以借助2
的n
次幂减去1
并做与运算,就等价于取模:hash&(length-1)
JDK1.8 后扩容
JDK1.8
后的扩容也是有一定技巧,直接和原先长度进行与运算,如果为0
,还是在当前所以位置,如果不等于0
(等于1
),索引就等于当前索引加上原先数组长度的位置。
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
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);
减少哈希碰撞
哈希碰撞就是不同的对象算出来的哈希值一样了,让数组均匀分配。
阅读 1103 · 发布于 2021-10-22
————        END        ————
Give me a Star, Thanks:)
https://github.com/fendoudebb扫描下方二维码关注公众号和小程序↓↓↓

昵称:
随便看看
换一批
-
Linux中/bin、/sbin、/usr/bin、/usr/sbin、/usr/local/bin、/usr/local/sbin 目录的含义及区别阅读 1273
-
Git rollback 无法回滚已修改文件阅读 622
-
IDEA macOS 合并的窗口间切换阅读 54
-
Go 时间加减、计算方法耗、毫秒转 Time阅读 18031
-
Redis Cluster 搭建阅读 3166
-
Nginx 日志按天生成阅读 8401
-
Tomcat acceptCount 和 maxConnections 参数解析阅读 1540
-
Android 获取状态栏高度阅读 3225
-
Linux 统计文本行数阅读 1428
-
Git 撤销 commit 和回退到指定 commit阅读 5514