位运算与 HashMap 容量真实验证:为什么必须是 2 的幂

真实验证:任意初始容量都会被规整成 2 的幂

复刻 HashMap 源码里的 tableSizeFor 方法,并用反射拿到真实创建出来的 table 数组长度做对照。

BitwiseHashMapDemo.java static int tableSizeFor(int cap) { int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1); return (n < 0) ? 1 : (n >= (1<<30)) ? (1<<30) : n + 1; } HashMap<String, Integer> map = new HashMap<>(10); map.put("init", 1); // 触发真正分配 table Field tableField = HashMap.class.getDeclaredField("table");

tableSizeFor(1) = 1，是否是2的幂: true
tableSizeFor(5) = 8，是否是2的幂: true
tableSizeFor(7) = 8，是否是2的幂: true
tableSizeFor(10) = 16，是否是2的幂: true
tableSizeFor(16) = 16，是否是2的幂: true
tableSizeFor(17) = 32，是否是2的幂: true
tableSizeFor(100) = 128，是否是2的幂: true
new HashMap(10) 首次 put 后真实 table.length: 16

真实结果验证了两件事:第一,不管构造函数传入的初始容量是多少,tableSizeFor 算法(用 numberOfLeadingZeros 找到大于等于该数的最小 2 的幂)真实把它规整成了 2 的幂,10 变成 16、17 变成 32。第二,用反射拿到 new HashMap<>(10) 真实创建出来的内部 table 数组长度,结果是 16,和算法计算值完全对上,证明这不是纸面推导,是 HashMap 真实的运行时行为。

真实验证:(n-1)&hash 只在 n 是 2 的幂时等价于 hash%n

这才是"必须是2的幂"的真正原因:HashMap 定位桶用的是位运算而不是取模,而这个位运算只在特定条件下才和取模结果相同。

BitwiseHashMapDemo.java int n = 16; for (int h = 0; h < 1000; h++) { if (((n-1) & h) != (h % n)) { allMatch = false; break; } }

n=16(2的幂) 时，(n-1)&hash 与 hash%n 是否对所有测试值都相等: true

n=15(非2的幂) 时，(n-1)&hash 与 hash%n 是否对所有测试值都相等: false
首个不一致样例: h=1, (n-1)&h=0, h%n=1

真实验证:扰动函数确实改变了哈希值

HashMap 在真正做 (n-1)&hash 之前,会先对 hashCode() 做一次扰动(h ^ (h>>>16)),目的是让高位也参与低位的运算。

"abc".hashCode()=96354, 扰动后=96355, 是否相同: false
Integer.bitCount(255)=8（应为8，二进制全1）
Integer.highestOneBit(100)=64（100的二进制最高位对应的2的幂）
Integer.numberOfLeadingZeros(1)=31（32位中1前面有多少个0）

真实验证了扰动函数确实产生了效果(96354 变成 96355)。因为最终定位桶只用了 hashCode() 的低几位(容量越小,用到的位数越少),如果不做这一步异或高16位的处理,那些只在高位上有差异、低位完全相同的对象会真实全部落进同一个桶,扰动函数用很小的代价把高位的信息也混进了低位,真实改善了哈希分布。

分步演示:HashMap 为什么能用位运算代替取模

每一行都是真实运行这段代码得到的结果。