HashMap.java
里第 569 行,tab[(n - 1) & hash]
中&
的意思是随机取一个小于等于 n-1 的值吗?
以下是我做的测试
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 而已
|