这是一个创建于 2000 天前的主题，其中的信息可能已经有所发展或是发生改变。
HashMap.java里第 569 行，tab[(n - 1) & hash]中&的意思是随机取一个小于等于 n-1 的值吗？
第 1 条附言 · 2019-06-04 14:02:42 +08:00
以下是我做的测试
Map<Integer, Integer> map = new HashMap<>();
map.put(3, 11);
map.put(8, 12);
map.put(1, 13);
System.out.println(map.containsKey(8));
我传入的值是8，debug看到getNdoe里hash是8，key是8。
我这里tab.length应该是3吧
为什么first = tab[(n - 1) & hash]的first得到的结果是tab[2]//"8" -> "123"呢？
2&8的值是0才对啊
 |
1
tchqiq 2019-06-04 13:39:40 +08:00
可以这么认为.hash 是用高 16 位和低 16 位异或得到.所以更为"随机"
|
 |
2
cookii 2019-06-04 13:42:50 +08:00
n 是之前获取的 table 的长度，n 的值总是 2 的次方(16/32/64/128...)，(n-1)转换成二进制低位全部是 1，和 hash 值&操作相当于对 n 取余。
|
 |
3
ukipoi OP @imzhoukunqiang 请教一下为什么 n 的值总是 2 的次方呢？关于我的 第 1 条附言 希望能解答一下
|
 |
4
neuthself 2019-06-04 14:07:55 +08:00
jdk1.7 中 HashMap 通过 h & (length-1) 来得到数组位置，而底层数组的长度总是为 2 的 n 次方。当 length 为 2 的 n 次方时，h & (length-1) 运算等价与对 length 取模，也就是 h % length，但是 & 比 % 具有更高的效率。
jdk1.8 中 HashMap 优化了高位运算的算法，通过 hashcode() 的高 16 位异或低 16 位实现的: (h = key.hashCode()) ^ (h >>> 16) ,这样做可以在数组 table 的 length 比较小的时候，也能保证考虑到高低 Bit 都参与到 hash 运算中，同时不会有太大的开销。 |
|
5
neuthself 2019-06-04 14:08:42 +08:00
并且由于每次扩容是上一次的两倍。Jdk1.8 中，扩容之后元素要么是在原来的位置，要么实在原来的位置再移动 2 次幂的位置。
|
|
6
cookii 2019-06-04 14:22:19 +08:00  1
@ukipoi table 的 length ≠ map 的 size，此时 table 的 size 应该是 16 吧(默认容量 没记错的话)，，hashmap 中 table 长度是由 tableSizeFor(int cap)计算得来的。这个方法总会返回最接近且大于等于 cap 的 2 的幂。 使用这个方法取余的原因可以参照 4L 说的，效率问题。
|
 |
7
Caturra 2019-06-04 14:22:48 +08:00 via Android
@ukipoi 不严谨的说下自己的想法，n 保持 2 的幂可以保证 n-1 永远是二进制全 1，符合原来算法的实现（&hash 那一段，替代性能低下的 mod 操作），其次，假设（ n-1 ）&hash 在扩容前算法足够均匀（ hash 的处理是和自己的高 16 位取 xor ），那下一个 index 比原来的 index 在二进制上只是多了最高位的 0 和 1 的区别，也就是只要重新分布一半数目的 index 即可
|
 |
8
limuyan44 2019-06-04 16:37:39 +08:00 via Android
就是为了扩容不二次 hash 而已
|
Select Language