Cuckoo Hashing - 最坏情况 O(1) 查找

引言

哈希表是一种基本数据结构，允许您创建关联数组或键值对映射。它们以平均时间复杂度 O(1) 执行高效的插入、删除和检索操作。然而，在某些情况下，哈希表可能会由于冲突而导致性能下降，即多个键哈希到同一个索引。布谷鸟哈希通过提供最坏情况下的常数时间查找来克服这个问题，使其成为现有哈希方法的有效替代方案。

什么是布谷鸟哈希？

布谷鸟哈希是一种用于解决哈希表中冲突的哈希技术。经典哈希表中的冲突发生在多个键映射到相同哈希值时，导致存储位置的冲突。布谷鸟哈希通过使用多种哈希算法和哈希表来解决这个问题。

以下是布谷鸟哈希的工作原理

1. 多个哈希函数： 布谷鸟哈希使用多个哈希函数。每个哈希函数将一个键分配到哈希表中的特定位置。
2. 多个哈希表： 布谷鸟哈希不是只使用一个哈希表，而是使用两个或更多。每个哈希表包含一部分键。
3. 键放置： 布谷鸟哈希首先对键值对进行哈希，然后将其输入哈希表。它接下来尝试将键插入第一个哈希表中适当的位置。如果该位置已被占用，它会移除现有键并使用另一个哈希函数选择的替代位置重新插入。此方法是递归的，直到所有键都找到自己的位置而没有冲突或达到预定义的阈值。
4. 查找： 当查找键时，布谷鸟哈希使用所有哈希函数对其进行哈希，并检查哈希表中的每个位置。如果键存在于任何表中，则可以在常数时间内获取。
5. 重新哈希： 如果插入过程遇到循环或超过一定数量的位移，则必须扩展或重新哈希哈希表以容纳更多键。它需要重新计算哈希函数并将键分布到新的哈希表中。

基本操作

查找

• 当您想查找特定项目（键）是否在哈希表中时，您可以使用查找操作。
• 您向哈希表提供您要查找的项目（键），它会告诉您它是否存在。
• 如果存在，它返回“true”；如果不存在，它返回“false”。

插入

• 如果您想向哈希表添加新项目（键），您可以使用插入操作。
• 您向哈希表提供要添加的项目。
• 如果该项目尚未在表中，它会添加它。
• 如果该项目已存在，它不会再次添加。

删除

• 当您想从哈希表中移除项目（键）时，您可以使用删除操作。
• 您指定要移除的项目。
• 然后哈希表从其结构中移除该项目。
• 如果该项目最初不在表中，则什么也不会发生。

示例

假设我们有一个具有两个哈希函数的哈希表，

h₁(x) 和 h₂(x)，以及一个大小为 n 的数组。最初，数组中的所有槽位都是空的。

假设我们想将一个键 K 插入哈希表。我们使用两个哈希函数计算它的两个哈希值

h₁(K) 和 h₂(K)。

假设我们有一个大小为 5 的数组和两个哈希函数的哈希表

h1(x)=xmod5

h2(x)=(xmod5+1)mod5

现在，让我们插入键

7、12、6 和 17 到哈希表中

1. 插入 7

• h1(7) =7mod5=2，所以我们把 7 放在槽位 2。

2. 插入 12

• h1(12) =12mod5=2，但槽位 2 已经被 7 占用。
• h2(12) =(12mod5+1) mod5=3，所以我们把 12 放在槽位 3。

3. 插入 6

• h1(6) =6mod5=1，所以我们把 6 放在槽位 1。

4. 插入 17

• h1(17)=17mod5=2，但槽位 2 已经被占用。
• h2(17)=(17mod5+1)mod5=3，但槽位 3 已经被 12 占用。
• 我们继续移动键，直到递归找到一个空槽位。在这种情况下，12 移动到槽位 4。
• h1(17)=17mod5=2，现在槽位 2 为空，所以我们把 17 放在槽位 2。

实施

输出

说明

1. 初始化

• 创建两个数组来表示哈希表，称为 table1 和 table2。
• 两个数组最初都是空的。
• 决定哈希表的大小和允许的最大插入尝试次数。

2. 插入

• 要插入一个键，使用两个不同的哈希函数计算其哈希值。
• 首先，尝试将键放入 table1 中由第一个哈希函数确定的索引处。
• 如果该槽位被占用，则将现有键移动到 table2，并尝试将新键插入 table1。
• 如果 table2 中的槽位也被占用，则在表之间递归移动键，直到找到一个空槽位或达到最大尝试次数。

3. 重新哈希

• 如果在未找到空槽位的情况下达到最大尝试次数，则触发重新哈希。
• 重新哈希涉及将哈希表的大小加倍并重新分配键。
• 重新哈希后，重试插入键。

4. 查找

• 要检查键是否存在，使用相同的哈希函数计算其哈希值。
• 在 table1 和 table2 中搜索键。
• 如果在任一表中找到键，则返回 true；否则，返回 false。

5. 主方法

• 在主方法中，创建 CuckooHashing 类的一个实例，并指定表大小和最大尝试次数。
• 将一些键插入哈希表。
• 通过执行查找来检查特定键是否存在。

复杂度分析

时间复杂度

插入： 平均 O(1)，最坏情况 O(n)，因为可能需要重新哈希。

查找： O(1)，因为它涉及计算哈希值并检查两个可能的位置。

重新哈希： 触发时为 O(n)，但很少发生，并在所有插入中均摊。

空间复杂度

空间复杂度为 O(n)，其中 n 是哈希表的大小。

每个哈希表最多包含 n 个元素，从而导致线性空间复杂度。

优点

1. 常数时间查找： 布谷鸟哈希确保最坏情况下的查找时间为 O(1)，无论键的数量或哈希表的大小如何。它在需要常数性能的实时系统和应用程序中特别有用。
2. 空间效率： 与某些冲突解决方法不同，布谷鸟哈希不需要额外的空间用于链表或探测结构。它提高了内存效率，尤其是在处理大型数据集时。
3. 确定性性能： 布谷鸟哈希确保确定性性能，这简化了分析并确保了跨各种输入和工作负载的一致行为。

应用

1. 网络路由和交换： 布谷鸟哈希可用于网络设备中，以有效执行路由表查找、数据包转发和流量分类。
2. 分布式系统： 在分布式数据库和键值存储中，布谷鸟哈希可以帮助在多个节点上实现高效的数据分发和检索。
3. 缓存管理： 布谷鸟哈希可以通过快速识别和替换旧项目来优化缓存淘汰规则，从而提高缓存性能。