哈希表如何避免冲突

 系列文章：

                 1.   先导片--Map&Set之二叉搜索树

                 2.   Map&Set之相关概念

                 3.   哈希表如何避免冲突

目录

1.概念

2. 冲突-概念

3. 冲突-避免

3.1 冲突-避免-哈希函数设计

3.2 冲突-避免-负载因子调节

4. 冲突-解决

4.1 冲突-解决-闭散列

4.1.1 线性探测

4.1.2.二次探测

4.2 冲突-解决-开散列/哈希桶

5. 冲突严重时的解决办法

---

1.概念

        在探讨数据结构的效率时，我们常常关注于查找操作的速度。 在顺序结构中，如数组或列表，查找一个元素通常需要遍历整个结构，这样的时间复杂度为O(N)，其中N是元素的总数。 类似地，在平衡树结构中，查找的时间复杂度与树的高度相关，也大致是O(N)。显然，这两种结构的查找效率都依赖于搜索过程中进行的比较次数。

        理想的搜索方法应该能够无需任何比较，直接从表中获取所需元素。这可以通过构造一种特殊的存储结构来实现，即通过一种称为哈希函数（hashFunc）的映射关系，将元素的关键码直接映射到其存储位置。这样，在查找时，只需通过哈希函数即可快速定位到元素的具体位置。

具体操作如下：

        - 插入元素：根据待插入元素的关键码，使用哈希函数计算出该元素的存储位置，并按此位置存放元素。
        - 搜索元素：对待查找元素的关键码应用相同的哈希函数，将得到的函数值作为元素的存储位置。在结构中按此位置取元素进行比较，如果关键码相等，则搜索成功。

        这种方法被称为哈希（散列）方法，使用的转换函数称为哈希（散列）函数，而构造出来的数据结构称为哈希表（Hash Table）或散列表。哈希表的优势在于，它能够在平均情况下提供近乎常数时间的查找效率，即O(1)，从而极大地优化了数据的访问速度。

哈希函数：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。

根据上面这个公式，我们将1,2,3,6,7,8放入下面这个表格中，得到： 

在使用哈希表进行搜索时，由于通过哈希函数可以直接计算出数据存储的位置，因此通常不需要进行多次关键码的比较，这使得搜索速度非常快。然而，尽管这种方法看起来非常有效，但它并非没有潜在的问题。例如，当我们尝试向表中插入一个关键码为33的元素时，可能会出现哈希冲突问题。这是因为33计算的哈希值和3计算得出的哈希值相同，导致它们在哈希表中的位置发生冲突。

2. 冲突-概念

对于两个数据元素，其关键字分别为i和j，如果它们通过哈希函数计算得出的哈希地址相同，即Hash(i) == Hash(j)，这种现象称为哈希冲突或哈希碰撞。在这种情况下，具有不同关键字但具有相同哈希地址的数据元素被称为“同义词”。

3. 冲突-避免

首先，我们需要明确一点，由于哈希表底层数组的容量通常小于实际要存储的关键字的数量，冲突的发生是不可避免的。然而，我们可以通过一些方法来尽量降低冲突率。

3.1 冲突-避免-哈希函数设计

引起哈希冲突的一个主要原因可能是哈希函数的设计不够合理。在设计哈希函数时，应遵循以下几个原则：

• 定义域覆盖：哈希函数的定义域必须包括需要存储的全部关键码。

• 值域适配：如果散列表允许有m个地址，哈希函数的值域必须在0到m-1之间。

• 均匀分布：计算出来的地址应能均匀分布在整个空间中，以避免某些区域过于拥挤，而其他区域则几乎没有数据。

• 简单高效：哈希函数应该比较简单，便于计算和实施。

常见的哈希函数包括：

1. 直接定制法（常用）：
   取关键字的某个线性函数为散列地址，例如：Hash(Key) = A*Key + B。这种方法简单且能使得散列地址较均匀，但需要事先知道关键字的分布情况。适合查找比较小且连续的情况。

2. 除留余数法（常用）：
   设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key % p（p <= m），将关键码转换成哈希地址。

3. 平方取中法（了解）：
   假设关键字为1234，对它平方得到1522756，抽取中间的3位227作为哈希地址。这个方法比较适合不知道关键字的分布，而位数又不是很大的情况。

4. 折叠法（了解）：
   折叠法是将关键字从左到右分割成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。适合事先不需要知道关键字的分布，适合关键字位数比较多的情况。

5. 随机数法（了解）：
   选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key)，其中random为随机数函数。通常应用于关键字长度不等时采用此法。

6. 数学分析法（了解）：
   设有n个d位数，每一位可能有r种不同的符号。这些符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等；在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。

通过这些方法，我们可以尝试减少哈希冲突的发生，但在实际应用中，冲突仍然是无法完全避免的。因此，选择合适的冲突解决方法，如链地址法或开放定址法，对于提高哈希表的性能同样重要。

3.2 冲突-避免-负载因子调节

散列表的载荷因子定义：α = 填入表中的元素个数 / 散列表的长度

一般情况下，我们的哈希表会有一个默认的负载因子--0.75f 。

负载因子和冲突率的关系粗略演示

负载因子和冲突率成反比， 所以当冲突率达到一个无法忍受的程度时，我们需要通过降低负载因子来变相的降低冲突率。

已知哈希表中已有的关键字个数是不可变的，那我们能调整的就只有哈希表中的数组的大小。

4. 冲突-解决

解决哈希冲突 两种常见的方法是： 闭散列 和 开散列

4.1 冲突-解决-闭散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以 把 key 存放到冲突位置中的 “ 下一个 ” 空位置中去。 那如何寻找下一个空位置呢？

4.1.1 线性探测

以下是处理哈希冲突的线性探测法的具体步骤：

以插入元素33为例，我们首先使用哈希函数计算出其理论上的存储位置，即下标为3。按照预期，33应该被插入到这个位置。然而，在该位置我们发现已经存在一个值为3的元素，这时就发生了哈希冲突。

为了解决这种冲突，我们采用线性探测的方法。这意味着我们从发生冲突的位置（下标3）开始，依次向后查找，直到找到一个空的位置。假设这个空位置的下标为j，我们就将新元素33插入到这个位置。

具体步骤如下：

1. 计算哈希地址：通过哈希函数确定待插入元素的目标位置。
2. 检查冲突：如果计算出的位置已经有元素存在，说明发生了哈希冲突。
3. 线性探测：从冲突发生的位置开始，顺序探测下一个位置，直至找到一个空位。
4. 插入元素：在找到的空位处插入新元素。

在闭散列技术中，处理哈希冲突时需要特别注意，不能简单地物理删除哈希表中已有的元素。这是因为直接删除一个元素可能会影响其他元素的搜索。例如，如果我们直接删除了元素3，那么在查找元素33时，可能会因为缺少原始键值3的信息而受到影响。

为了解决这个问题，线性探测采用了一种标记的伪删除法。这种方法不真正删除元素，而是将其标记为“已删除”。具体操作如下：

1. 标记删除：当需要“删除”一个元素时，实际上并不从哈希表中移除它，而是在该位置做一个特殊标记，比如将该位置的值设置为一个特殊状态（如“null”或其他标识）。

2. 更新搜索：在搜索时，如果遇到被标记为“已删除”的位，则跳过该位继续探测，就像处理哈希冲突时的线性探测一样。

3. 插入和查找：对于插入和查找操作，遇到被标记为“已删除”的位置，也按照线性探测的方式处理，即继续向后寻找合适的位置。

这种方法的优点在于，它避免了因删除元素而导致的连锁反应，即一系列的元素都需要移动来填补被删除空间的情况。这样可以保持哈希表的稳定性，并减少由于元素移动引起的潜在错误。

总结来说，闭散列中的线性探测通过标记的伪删除法来处理元素的删除，确保了哈希表的完整性和搜索的正确性，同时最小化了由于删除操作带来的复杂性和性能损耗。

4.1.2.二次探测

线性探测的缺陷在于，当发生哈希冲突时，会导致数据在表中堆积起来。这是因为线性探测在寻找下一个空位置时，会顺序地检查表中的每个位置，直到找到空位为止。为了解决这个问题，二次探测方法被提出来改善这一状况。

二次探测方法在寻找下一个空位置时，采用的计算公式为：Hi = (H0 + i^2) \% m，或者 Hi = (H0 - i^2) \% m。其中，i = 1, 2, 3…，H0 是通过散列函数 Hash(x) 对元素的关键码 key 进行计算得到的位置，m 是表的大小。

例如，如果要插入元素33，而初始哈希位置已经有冲突，使用二次探测方法可以找到合适的插入位置。

研究表明，当表的长度为质数且表的装载因子 a 不超过0.5时，新的表项总是能够被插入，并且不会重复探查任何一个位置。这意味着只要表中有至少一半的空位置，就不会出现表满的情况。在搜索时，我们不需要担心表是否已满，但在插入时，必须确保表的装载因子 a 不超过0.5。如果超过这个阈值，就必须考虑增大表的容量。

因此，相比于线性探测，二次探测的最大优点在于减少了冲突的发生，提高了空间利用率。然而，哈希表的这些方法都有其固有的缺陷，即空间利用率相对较低。

4.2 冲突-解决-开散列/哈希桶

开散列法，也称为链地址法或开链法，首先使用散列函数为关键码集合计算散列地址。具有相同地址的关键码被归入同一个子集合，每个这样的子集合被称为一个“桶”。每个桶中的元素通过一个单链表链接起来，而这些链表的头结点则存储在哈希表中。

这种方法有效地将具有相同散列地址的元素组织在一起，通过单链表解决冲突问题，确保了元素的有序存储和高效访问。

5. 冲突严重时的解决办法

刚才我们提到了，哈希桶实际上可以将一个大集合的搜索问题转化为多个小集合的搜索问题。然而，如果冲突严重，这意味着这些小集合的搜索性能也会受到影响。在这种情况下，我们可以进一步优化这个所谓的小集合搜索问题，例如：

1. 每个桶的背后是另一个哈希表：这种方法实际上是对冲突元素进行再次散列，形成一个多层次的哈希结构。这样可以进一步减少冲突，但增加了操作的复杂性。

2. 每个桶的背后是一棵搜索树：这种方法使用搜索树（如二叉搜索树、平衡树等）来替代链表，用于处理那些冲突的元素。这样可以利用搜索树的特性，提高搜索、插入和删除的效率，尤其是在冲突较多的情况下。

这两种方法都是对基本哈希桶方法的改进，旨在提高在高冲突环境下的性能。选择合适的方法取决于具体的应用场景和数据特性。