哈希表如何对键做哈希？扩容时索引变动问题如何解决？

哈希表扩容时出现索引变动是正常现象，本质是索引计算依赖桶数组长度的取模逻辑，可根据你的实际需求选择对应的处理方式： #

常规动态扩容哈希表（业界标准实现方案） #

如果你的需求是实现通用的可动态扩容的哈希表，不需要强制索引固定，用标准重哈希流程即可：

• 触发扩容：当负载因子（已存储键值对数量 / 桶数组长度）超过阈值（通常为0.75）时触发扩容，建议将扩容后的桶长度设为原长度的2倍，且始终保持桶长度为2的n次幂，此时取模运算可以替换为位运算 h(x) & (length - 1)，比普通取模性能高3~5倍。
• 执行重哈希：扩容时遍历旧桶数组的所有键值对，对每个键用新的桶长度重新计算索引，将键值对迁移到新桶的对应位置，迁移完成后用新桶数组替换旧桶数组即可。

注：如果哈希值可能为负数，计算索引前需要先转为非负整数，示例逻辑：(h(x) & 0x7FFFFFFF) % length，避免出现负索引。

要求索引永久固定的特殊场景 #

如果你的业务逻辑要求同一个键的存储索引不能随扩容变动，可以选择以下两种方案：

• 固定桶长度方案：提前评估业务最大存储容量，初始化桶数组时就设置为足够大的固定长度，全程不执行扩容操作，索引永远用 h(x) % 固定长度 计算，自然不会发生变动。缺点是会占用更多前置内存，若存储量超过预估值会导致哈希冲突率大幅上升。
• 一致性哈希方案：将整个哈希值空间划分为固定数量的虚拟节点，每个物理桶对应若干个虚拟节点，扩容时只调整虚拟节点和物理桶的映射关系，仅需要迁移少量数据，绝大多数键的索引不会发生变化。该方案适合分布式存储的哈希路由场景，无法保证100%的键索引完全不变。

内容的提问来源于stack exchange，提问作者user12577188