Java HashMap 里，在 getNode 方法中关于&的一个问题。

[ukipoi]

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才对啊

[tchqiq]

可以这么认为.hash 是用高 16 位和低 16 位异或得到.所以更为"随机"

[imzhoukunqiang]

n 是之前获取的 table 的长度，n 的值总是 2 的次方(16/32/64/128...)，(n-1)转换成二进制低位全部是 1，和 hash 值&操作相当于对 n 取余。

[ukipoi]

@imzhoukunqiang 请教一下为什么 n 的值总是 2 的次方呢？关于我的 第 1 条附言 希望能解答一下

[neuthself]

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 运算中，同时不会有太大的开销。

[neuthself]

并且由于每次扩容是上一次的两倍。Jdk1.8 中，扩容之后元素要么是在原来的位置，要么实在原来的位置再移动 2 次幂的位置。

[imzhoukunqiang]

@ukipoi table 的 length ≠ map 的 size，此时 table 的 size 应该是 16 吧(默认容量 没记错的话)，，hashmap 中 table 长度是由 tableSizeFor(int cap)计算得来的。这个方法总会返回最接近且大于等于 cap 的 2 的幂。 使用这个方法取余的原因可以参照 4L 说的，效率问题。

[Caturra]

@ukipoi 不严谨的说下自己的想法，n 保持 2 的幂可以保证 n-1 永远是二进制全 1，符合原来算法的实现（&hash 那一段，替代性能低下的 mod 操作），其次，假设（ n-1 ）&hash 在扩容前算法足够均匀（ hash 的处理是和自己的高 16 位取 xor ），那下一个 index 比原来的 index 在二进制上只是多了最高位的 0 和 1 的区别，也就是只要重新分布一半数目的 index 即可

[limuyan44]

就是为了扩容不二次 hash 而已