位运算实现哈希索引的核心是哈希扰动和与运算定位：先用h^(h>>>16)将高位信息融入低位提升散列均匀性，再用hash&(n−1)（要求n为2的幂）替代取模快速计算下标，兼顾效率与分布稳定性。

直接用位运算实现哈希索引，核心就两点：先做扰动让哈希值更散，再用与运算快速定位数组下标。不需要复杂数学，也不依赖取模，效率高且分布更稳。

为什么不用取模而用 & 运算

哈希表底层数组长度必须是 2 的幂（如 16、32、64），这样 n − 1 的二进制全是 1（比如 15 → 0b1111）。此时：

• hash % n 和 hash & (n − 1) 等价，都只保留 hash 的低 log₂n 位
• & 是 CPU 级原生指令，比 % 快好几个数量级
• 例如 hash = 27（0b11011），n = 16（0b10000），n−1 = 15（0b1111），27 & 15 = 11（0b1011）→ 正确落进索引 11

关键一步：哈希扰动提升均匀性

Java 默认的 hashCode() 返回 32 位整数，但数组通常只有 16 或 32 个槽位。如果只取低几位，高位不同、低位相同的键（如 0x12345678 和 0x9abc5678）会全挤进同一个桶。

解决办法是加入扰动：

• 写法：(h = key.hashCode()) ^ (h >>> 16)
• 原理：把高 16 位无符号右移后与原值异或，让高位“渗透”进低位
• 效果：原来低 4 位都是 1000 的两个键，扰动后大概率变成 0110 和 1101，&15 后分到不同桶

动手写一个可运行的简易哈希映射

假设你维护一个固定大小为 32 的数组，想把任意字符串映射过去：

• 先计算原始哈希：int h = key.hashCode();
• 再扰动：int hash = h ^ (h >>> 16);
• 最后定索引：int index = hash & (32 - 1); // 即 hash & 31

这个三行逻辑就是 JDK 8 HashMap 实际在用的核心哈希策略。它不增加随机性，而是有针对性地弥补低位信息贫乏的问题，对大多数未重写 hashCode() 的对象特别有效。

小提醒：别指望它解决所有冲突

扰动函数不能替代合理设计的键：

• 语义相近的键（如 "user_1"、"user_2"）天然易碰撞，需重写 hashCode()
• 数组长度不是 2 的幂时，& 运算失效，必须改用 % 或扩容对齐
• 冲突仍会发生，后续要用链表或红黑树承接溢出元素