概述

双重哈希是一种计算机编程技术，它与哈希表中的开放寻址结合使用，以解决哈希冲突，方法是在发生冲突时使用密钥的辅助哈希作为偏移量。

要点

• 双哈希算法的复杂性
  • 时间复杂度 - O（n）

双重散列简介

您是否曾经与银行客户服务主管交谈过？对于任何投诉或疑问，他们首先会问您您的银行帐号。你觉得怎么样？他们为什么需要您的帐号？

是的，没错！您的帐号显示有关您的所有信息。对于每个客户，银行都维护一个键值对。密钥是您的帐号，值是您的完整信息。我们可以说银行已经以帐号的形式对您的全部信息进行了哈希处理。

哈希是一种强大的技术，用于在平均恒定时间内存储和检索数据。在这种技术中，我们将数据或一些键存储在称为哈希表的固定大小的数组结构中。

每个键都映射到哈希表上的特定位置。此映射称为哈希函数。理想的哈希函数必须将每个唯一键映射到哈希表上的唯一位置。

在大多数实际场景中，键的数量远远大于哈希表中的位置数量，因此，无论哈希函数有多好，都必然会发生冲突。

当两个或多个不同的键被哈希处理到哈希表的同一位置时，就会发生冲突。为了解决这些冲突，我们需要某种冲突解决技术。其中一种有效的冲突解决技术是双重散列。

什么是双重哈希？

在双重哈希中，我们使用两个哈希函数。第一个哈希函数是，这个函数接受我们的键，并在哈希表上给出一个位置。如果新位置是空的，我们可以轻松地将密钥放入其中，而无需使用辅助哈希函数。

但是，在发生冲突的情况下，我们需要使用辅助哈希函数 与第一个哈希函数结合使用 在哈希表上找到一个新位置。 使用的组合哈希函数的格式为。在这里，i 是一个非负整数，表示冲突数，k = 正在散列的元素/键，m = 散列表大小。

辅助哈希函数的使用 碰撞后，帮助我们到达哈希表上的新位置，每个新位置的距离为......，这导致了对哈希表进行寻址的非线性方式，从而减少了冲突的次数。

需要考虑的非常重要的一点是，两个哈希函数都应按 O（1） 时间的顺序计算。

1. 在图中，我们有一个大小为 5 的哈希表和两个键 10、15，需要插入到哈希表中。我们在这里使用两个哈希函数，第一个哈希函数 = = key % 5和辅助哈希函数 == key % 7

2. 我们从第一个键 10 开始，并应用我们的第一个哈希函数来获取 10 在哈希表上的位置。
   位置。现在第 0 个位置是空的，因此我们可以将 10 个位置放在那里。这里不需要使用辅助哈希函数。

3. 现在，我们取第二个键 15 并再次应用我们的第一个哈希函数。
   位置。哎呀！这一次位置不是空的，因此是碰撞。我们需要为键 15 找到一个新位置，为此我们使用辅助哈希函数。
   新位置。哈希表的第一个位置是空的，我们可以在这里放置键 15。

数据结构中的双重哈希示例

双重哈希背后的想法相当简单，

1. 获取要存储在哈希表上的密钥。
2. 应用第一个哈希函数ℎ1h1​（key） 以获取存储密钥的位置。
3. 如果该位置为空，请将密钥放在该位置上。
4. 如果位置已填充，请应用第二个哈希函数ℎ2h2​（键）结合第一个哈希函数ℎ1h1​（键）以获取密钥的新位置。

让我们通过一个动手问题更详细地探讨这个想法，

问题陈述：

将键 79、69、98、72、14、50 插入大小为 13 的哈希表中。使用双哈希解决所有冲突，其中第一个哈希函数是 = k mod 13第二个哈希函数是

溶液：

最初，所有哈希表位置都是空的。我们选择第一个键 = 79 并应用在它上面，

ℎ1h1​（79） = 79 % 13 = 1，因此键 79 哈希值为哈希表的位置。但是在放置密钥之前，我们需要确保哈希表的位置为空。在我们的例子中，它是空的，我们可以轻松地将钥匙 79 放在那里。

第二个键 = 69，我们再次申请 在它上面，，因为位置是空的，我们可以把69放在那里。

第三个键 = 98，我们应用 在它上面，​​​​​​​ = 98 % 13 = 7，位置是空的，所以98放在那里。

第四个键 = 72， = 72 % 13 = 7，现在这是一个碰撞，因为位置已被占用，我们需要使用双重哈希来解决此冲突。

= [ 7 + 1 * （ 1 + 72 % 11） ] % 13

= 1

位置已经在哈希表中被占用，因此我们再次发生冲突。现在我们再次重新计算 i = 2

= [ 7 + 2 * （ 1 + 72 % 11） ] % 13

= 8

位置在哈希表中是空的，现在我们可以将键 72 放在那里。

第五个键 = 14，​（14） = 14%13 = 1，现在这又是一次冲突，因为第一个位置已经被占用，我们现在需要使用双重哈希来解决这个冲突。

= [ 1 + 1 * （ 1 + 14 % 11） ] % 13

= 5

位置是空的，我们可以轻松地将 14 号钥匙放在那里。

第六个键 = 50，​（50） = 50%13 = 11，位置已经空了，我们可以把钥匙50放在那里。

由于所有键都放在我们的哈希表中，因此完成了双重哈希过程。最后，我们的哈希表如下所示：

为什么要使用双重哈希？

双重哈希是流行的冲突解决技术之一。其他具有相同目的的流行变体是线性探测和二次探测。 但是，如果有其他技术可用，那么为什么我们首先需要双重散列呢？

双重哈希提供了更好的抗聚类能力。造成这种情况的一个主要原因是使用双重功能。双函数支持双重哈希，以执行更均匀的密钥分布，从而减少冲突。

数据结构中双重哈希的优点

1. 每次碰撞后，我们都会重新计算哈希表中元素的新位置。对于连续的碰撞，这将生成一系列位置。如果序列是唯一的，则碰撞次数较少。
2. 双重哈希创建最独特的序列，在哈希表中提供更均匀的键分布。
3. 如果哈希函数不够好，元素往往会在哈希表中形成分组。此问题称为聚类分析。双重哈希最不容易出现聚类。

基于双重哈希的练习题

问题陈述 1：

给定两个哈希函数，​（k） = k mod 23和（k） = 1 + k mod 19.假设表大小为 23。查找键 = 90 的第二次碰撞后通过双重哈希返回的地址。

溶液：

我们将使用双重哈希的公式-

h（k，i） = （​（k） + i *​（k） ）%m

正如它所给出的，k = 90，m = 23

由于第二次碰撞已经发生，i = 2。 代入上述公式中的值，我们得到，

h（90,2） = [ （ 90 % 23 ） + 2 * （ 1 + 90 % 19 ） ] % 23

= [ 21 + 2 * 15 ] % 23

= 5

因此，在第二次碰撞后，Key = 90 的双重哈希返回的地址为 5。

问题陈述 2：

给定一个正整数的 Array[] 和一个数字 n，找出数组中是否存在一对总和等于 n 的数字。如果存在这样的对，则返回 true 否则为 false。

例：

1. 输入：- A = [ 6， 4， 3， 1 ] 和 n = 7 输出：- 没错，对是 {4,3} 或 {6,1}
   解释：- 4 + 3 = 7 或 6 + 1 = 7

2. 输入：- A = [ 6， 4， 3， 1 ] 和 n = 8 输出：- 假，不存在
   这样的对 解释：- 数组中没有一对数字，其相加总和为 8

在转向解决方案之前，只需停下来思考一下

溶液：

以下 JAVA 代码提供了解决方案。

boolean isPairSumPresent(int[] arr, int n) {
   HashSet<Integer> hSet = new HashSet<>();
   for (int num : arr) {
       int diff = n - num;
       if (hSet.contains(diff)) {
           return true;
       } else {
           hSet.add(num);
       }
   }
   return false;
}

1. 我们维护一个整数的哈希集，用于存储数组数的补码。
2. 哈希集确保每次查找都可以在平均 O（1） 时间内完成。它在内部维护所谓的存储桶，然后尝试根据哈希函数在这些存储桶之间分配我们的元素。
3. 核心逻辑是迭代检查我们的哈希集是否包含所需的补码数。例如：如果总和是 8，数组的第一个元素是 3，那么在哈希集中，我们检查 5 （8 - 3） 是否存在。
4. 如果哈希集中不存在这样的补码，那么我们只需将数组号放入哈希集中并继续前进。
5. 如果存在这样的补码，那么我们返回 true 并停止。

双重散列的时间复杂度：

1. 哈希集中的每次查找都会花费 O（1） 个恒定时间。
2. 在最坏的情况下，我们可能无法找到这样的赞美并遍历整个数组，这将花费我们 O（n） 线性时间。
3. 像减法这样的静止运算只是恒定时间运算。
4. 因此，总时间复杂度 = O（n） 时间。

双重散列的空间复杂度：

1. 我们需要维护一个额外的哈希集，其大小不超过 n 个元素，这会消耗我们额外的 O（n） 空间。
2. 因此，总空间复杂度 = O（n） 时间。

结论

• 在本文中，我们揭开了双重哈希的神秘面纱。我们亲身体验了它的工作和应用。
• 最后，我们利用了它的优势，在恒定的平均时间内进行了搜索。