•Backend

处理Hash冲突的办法

Hash冲突是什么

JavaHash

Hash冲突是什么

Hash冲突也叫Hash碰撞，指的就是两个不同的元素，经过hash函数的计算后，得到的hash值一样

如何处理hash冲突

处理hash冲突的方法通常有以下几种：

  1. 拉链法（链地址法）：

将哈希表中每个槽的位置变成一个链表，当多个键的哈希值相同时，将它们存储在同一个链表中。

  1. 开放寻址法：

如果出现碰撞，寻找哈希表中的下一个可用位置。

  1. 再哈希法：

在出现碰撞时，使用第二个哈希函数计算新的索引位置，如果还冲突则再用另一个哈希函数重新算一次位置，直到无冲突。

一定会发生hash冲突吗

理论上是的，核心原理就是鸠占鹊巢，也叫抽屉原理。

空间有限，而元素无限或超过空间容量时，那么必定有一个空间会至少有两个元素。就像10只鸡要关在9个鸡笼里一样，那么必然有一个鸡笼至少有两只鸡。

拉链法

拉链法是最常见、也是最容易理解的方法。Java 的 HashMap 就是采用这种方式（数组 + 链表/红黑树）。

核心思想是：外挂存储。哈希表的每一个槽位（Bucket）不再只存一个数据，而是作为一个“入口”。所有哈希值相同的 Key，都像挂葡萄一样，挂在这个入口下面的链表上。

工作流程：

  1. 计算 Hash(Key) 取余得到索引 i。
  2. 查看数组下标 i 的位置
  3. 如果是空的，直接把数据放进去（或者创建一个新链表头）。
  4. 如果已经有数据了（发生碰撞），就顺着链表往下找。
  5. 如果链表中找到了相同的 Key，覆盖 Value。
  6. 如果走到链表尾部还没找到，就把新数据追加到链表末尾。

这种方式的优点是：

  1. 内存利用率高：不需要预先分配大量连续空间，链表节点是动态申请的。
  2. 处理冲突简单：无论冲突多少次，无非就是链表变长而已。
  3. 对负载因子不敏感：即使哈希表里的元素数量超过了数组大小（负载因子 > 1），它依然能工作（只是链表会很长，查询变慢）。

缺点也很明显：

  1. 额外的内存消耗：每个节点都需要额外的指针（Next指针）来指向下一个节点。
  2. 缓存不友好：链表节点在内存中是分散的，CPU 缓存命中率不如连续数组高。
  3. 查询退化：如果黑客故意构造大量 Hash 值相同的 Key（Hash 洪水攻击），链表会变得极长，查询时间从 O(1) 退化为 O(n)。

所以jdk 1.8的时候，引入了红黑树来优化发生hash冲突时，链表On的查询复杂度

开放寻址法

这种方法不用额外的链表，所有的数据都必须存在主数组里。

其核心思想是：占坑位。如果你的位置被占了，你就去数组里找下一个空位。这就像在电影院找座位，票上的座位有人了，你就往后挨个找空座。

常见的探测方式：

  • 线性探测：步长为 1。位置被占了，就看 index+1，再看 index+2... 直到找到空位。（实现简单）
  • 二次探测：步长为平方数。位置被占了，就看 index+1²，再看 index+2²... 避免数据聚集在一起。（缓解线性探测的堆积问题）
  • 双重哈希：使用两个哈希函数：h1(key) + i * h2(key)（hash冲突分布更均匀）

这种方式的优点是：

  1. 节省内容：不需要指针，节省了指针占用的内存空间。
  2. 缓存友好：数据都在连续的数组里，CPU 缓存命中率高。

缺点：

  1. 删除困难：你不能直接把元素删掉，因为这会截断后续元素的查找路径。通常需要标记为“墓碑（Tombstone）”或“已删除”，逻辑复杂。

    即Entry中增加一个isDeleted变量来充当Tombstone标记，如果isDeleted判断为true就可以直接在此插入新元素，否则就继续探测

    比较有意思的是TreadLocalMap也还是采用的开放寻址里的线性探测法，但他的Entry里只有key-value没有额外的Tombstone标记。但别忘了TreadLocalMap里key是WeakReference，如果threadLocal的强引用没了，那么key就会被gc回收，那么在后续的set中，如果判断到当前key为null就会覆盖，get时，如果判断到当前key为null就会清理

  2. 聚集现象：这是线性探测最大的问题。一旦某一块区域冲突多了，数据会连成一片，后续插入的数据为了找空位要走很久，导致性能急剧下降。

  3. 容量限制：因为没有链表，数组存满了就必须扩容，负载因子通常不能太高（一般 0.7 左右性能就开始下降）。

再哈希法

当一个哈希函数计算出的地址发生冲突时，它会使用另一个哈希函数来重新计算地址，直到找到一个空位为止。

核心思想是：多重哈希。不进行探测（不去找相邻或跳跃的空位），而是直接换一个新哈希函数重新计算一个全新的地址，直到不冲突！

工作流程：

  1. 计算 Hash(Key) 取余得到索引 i。
  2. 如果 i 位置是空的，直接存入。
  3. 如果 i 位置有人了（且 Key 不同），使用备用的第二个函数。
  4. 计算新位置 Hash2(Key) 取余得到索引 j。
  5. 如果 j 位置有人了（且 Key 不同）继续用 Hash3(Key)……
  6. 直到找到空位

优点是：

  • 不易产生聚集：因为不同的哈希函数计算出的分布通常是独立的，数据会散落得非常均匀，不会像线性探测那样连成一片。

缺点：

  • 计算开销大：每次冲突都要做一次完整的、复杂的哈希运算（比如 MD5 换成 SHA-1，或者不同的多项式计算），比简单的“加法探测”要消耗更多的 CPU 时间。
  • 函数设计难：需要准备好几个“足够好且相互独立”的哈希函数，这在实现上比较麻烦。

post.comments