数据结构---哈希表

基本概念

哈希函数（Hash Function）是一种将输入的数据（通常是任意大小的）映射到固定大小的输出（通常是一个固定长度的值）的函数。这个输出值通常称为“哈希值”（Hash Value）或“哈希码”（Hash Code）。

• 基本特点：
  • 确定性：同样的输入必须产生相同的输出。
  • 快速计算：哈希函数应该能够快速计算出来，特别是在处理大量数据时。
  • 输出固定大小：无论输入数据的大小如何，哈希函数的输出应该是固定长度的。
  • 均匀分布：哈希值应该尽量均匀地分布在输出空间中，以减少哈希冲突。
  • 哈希冲突（Hash Collision）是指不同的输入数据经过哈希函数处理后，映射到相同的哈希值或相同的哈希槽（桶）中。由于哈希表的槽位是有限的，而输入的可能性是无限的，因此哈希冲突是不可避免的。为了有效地管理哈希冲突，我们需要使用冲突解决策略。

选择冲突解决策略的考虑因素：

• 负载因子：负载因子是指哈希表中元素个数与表的大小之比。如果负载因子过高，冲突会增多，性能也会下降。链式法在负载因子较高时性能依然较好，而开放地址法则可能出现性能瓶颈。
• 存储需求：链式法需要额外的空间来存储链表或其他数据结构，而开放地址法则不需要额外的空间，但可能会在高负载因子时导致查找效率下降。
• 查找和插入频率：如果哈希表中的查找操作多于插入操作，使用链式法可能更合适，因为在链式法中查找冲突的元素比较简单。对于插入和查找都频繁的场景，开放地址法或渐进式哈希可能表现得更好。

哈希冲突解决方法：

链式法（Chaining）：

• 在这种方法中，每个哈希桶不仅仅存储一个元素，而是存储一个元素链表（或其他数据结构，如链表、二叉树等）。当多个元素哈希到同一个桶时，它们就以链表的形式存储在该桶中。
• 优点：
  • 实现简单。
  • 不需要额外的空间重新哈希（如果槽位已满，只需动态扩展链表即可）。
  • 哈希表大小可以灵活扩展，不需要预先确定哈希表的大小。
• 缺点：
  • 在极端情况下（所有元素都哈希到同一个桶），查找的时间复杂度可能退化为 O(n)。
  • 链表的管理和扩展可能需要额外的空间开销。

开放地址法（Open Addressing）：

在开放地址法中，所有元素都存储在哈希表的主数组中，而不使用额外的数据结构（如链表）。当发生冲突时，形成某个探测序列；按此序列逐个探测散列表中的其他地址，直到给定的关键字或一个空地址（开放的地址）为止，将发生冲突的记录放到该地址中。

散列地址的计算公式：Hi(key)=(H(key)+di) MOD m,i=1,2,…,k(k<=m-1)

• H(key):哈希函数
• m:散列表长度
• di:第i次探测时的增量序列；
• Hi(key)：经过i次探测后得到的散列地址。
• 常见的开放地址法有：

1.线性探测（Linear Probing）：

将散列表T[0,…m-1]看成循环向量。当发生冲突时，从初次发生冲突的位置依次向后探测其他的地址。
增量序列：di=0,1,2,3,…m-1
设初次发生冲突的地址是h，则依次探测T[h+1]，T[h+2]…，直到T[m-1]时又循环到表头，再次探测T[0]，T[1]…，直到T[h-1]
探测终止的情况：
1.表中对应位置，已经存在该元素
2.直到循环完成，仍为探测到空地址，散列表满。
- 优点：只要散列表未满，总能快速简单的找到一个不冲突的散列地址。
- 缺点：容易形成聚集（clustering），每个产生冲突的记录被散列到离冲突最近的空地址上，从而又增加了更多的冲突机会。

2.二次探测（Quadratic Probing）：

增量序列：d= ±1^2、±2^2、±3^2…±n^2 等。(具体增量序列根据题目要求来）
- 优点：探测序列跳跃式的散列到整个表中，比线性探测减少了聚集问题。
- 缺点：不能保证探测到散列表的所有地址。

3.伪随机探测法

增量序列使用一个伪随机函数来产生一个落在闭区间[1,m-1]的随机序列。

双重哈希（Double Hashing）：

使用第二个哈希函数来计算冲突元素的探测间隔。具体来说，若一个元素哈希到的位置已被占用，则使用另一个哈希函数来决定下一个探测位置。
优点：冲突的概率较小，避免了聚集问题。
缺点：需要额外的哈希函数，且实现较为复杂。
再哈希法（Rehashing）：

• 再哈希法是解决哈希冲突的一种方法，它涉及使用多个哈希函数。当使用第一个哈希函数产生冲突时，再哈希法会尝试第二个哈希函数，如果仍然冲突，就继续使用第三个，以此类推，直到找到一个没有冲突的哈希值。
• 优点：
  • 能够降低冲突率，提高查找效率。
  • 适用于处理大量数据的场景。
• 缺点：
  • 再哈希会导致重新计算所有元素的哈希值，增加计算时间和空间开销。
  • 当哈希表扩展时，可能会出现性能问题（尤其是在元素非常多时）。

渐进式哈希（Cuckoo Hashing）：

• 渐进式哈希是一种更复杂的解决冲突的方法。在这种方法中，每个元素有两个哈希位置。如果一个位置已经被占用，新的元素会“逐出”原来的元素，原来的元素会被移动到它的备用位置（通过另一个哈希函数）。这样逐步交换直到没有冲突。
• 优点：
  • 查找操作时间复杂度始终保持在 O(1)。
  • 极低的冲突率，适合大规模数据。
• 缺点：
  • 插入操作较为复杂。
  • 需要较多的空间，且逐出和迁移元素的过程可能导致性能下降。

---

以人言善我，必以人言罪我。 —韩非