数据结构中的哈希表

哈希表是数据结构中最重要的一种，它使用一种特殊的函数，称为哈希函数，该函数将给定的值与键映射起来，以便更快地访问元素。

哈希表是一种存储信息的数据结构，信息基本上有两个主要组成部分，即键和值。哈希表可以通过关联数组来实现。映射的效率取决于用于映射的哈希函数的效率。

例如，假设键是 John，值是电话号码，那么当我们通过下面的哈希函数传递键值时：

Hash(key)= index;

当我们通过哈希函数传递键时，它会返回索引。

Hash(john) = 3;

上面的例子将 John 添加到索引 3。

哈希函数的缺点

哈希函数为每个值分配一个唯一的键。有时哈希表使用不完美的哈希函数，这会导致冲突，因为哈希函数会为两个不同的值生成相同的键。

哈希

哈希是使用常数时间的一种搜索技术。哈希的时间复杂度为 O(1)。到目前为止，我们已经学习了两种搜索技术，即 线性搜索 和 二分搜索。线性搜索的最坏时间复杂度为 O(n)，二分搜索为 O(logn)。在这两种搜索技术中，搜索都取决于元素的数量，但我们想要一种花费常数时间的技术。因此，哈希技术应运而生，它提供了常数时间。

在哈希技术中，使用哈希表和哈希函数。使用哈希函数，我们可以计算存储值的地址。

哈希的核心思想是创建（键/值）对。如果给定了键，则算法会计算将存储值的位置。它可以写成：

Index = hash(key)

计算哈希函数有三种方法：

• 除法法
• 折叠法
• 平方中间法

在除法法中，哈希函数可以定义为：

h(k_i) = k_i % m;

其中 m 是哈希表的大小。

例如，如果键值为 6，哈希表的大小为 10。当我们将哈希函数应用于键 6 时，索引将是：

h(6) = 6%10 = 6

索引是 6，值将存储在此处。

冲突

当两个不同的值具有相同的值时，就会在它们之间产生问题，称为冲突。在上面的示例中，值存储在索引 6。如果键值为 26，则索引将是：

h(26) = 26%10 = 6

因此，两个值存储在同一个索引处，即 6，这会导致冲突问题。为了解决这些冲突，我们有一些称为冲突解决技术的方法。

以下是冲突解决技术：

• 开放寻址法：也称为闭定址法。
• 闭定址法：也称为开放寻址法。

开放寻址法

在开放寻址法中，解决冲突的一种方法称为链地址法。

让我们首先理解链地址法以解决冲突。

假设我们有一组键值：

A = 3, 2, 9, 6, 11, 13, 7, 12 其中 m = 10，h(k) = 2k+3

在这种情况下，我们不能直接使用 h(k) = k_i/m，而是使用 h(k) = 2k+3。

• 键值 3 的索引是：

index = h(3) = (2(3)+3)%10 = 9

值 3 将存储在索引 9 处。

• 键值 2 的索引是：

index = h(2) = (2(2)+3)%10 = 7

值 2 将存储在索引 7 处。

• 键值 9 的索引是：

index = h(9) = (2(9)+3)%10 = 1

值 9 将存储在索引 1 处。

• 键值 6 的索引是：

index = h(6) = (2(6)+3)%10 = 5

值 6 将存储在索引 5 处。

• 键值 11 的索引是：

index = h(11) = (2(11)+3)%10 = 5

值 11 将存储在索引 5 处。现在，我们有两个值（6, 11）存储在同一个索引处，即 5。这会导致冲突问题，所以我们将使用链地址法来避免冲突。我们将创建另一个列表并将值 11 添加到该列表中。创建新列表后，新列表将链接到包含值 6 的列表。

• 键值 13 的索引是：

index = h(13) = (2(13)+3)%10 = 9

值 13 将存储在索引 9 处。现在，我们有两个值（3, 13）存储在同一个索引处，即 9。这会导致冲突问题，所以我们将使用链地址法来避免冲突。我们将创建另一个列表并将值 13 添加到该列表中。创建新列表后，新列表将链接到包含值 3 的列表。

• 键值 7 的索引是：

index = h(7) = (2(7)+3)%10 = 7

值 7 将存储在索引 7 处。现在，我们有两个值（2, 7）存储在同一个索引处，即 7。这会导致冲突问题，所以我们将使用链地址法来避免冲突。我们将创建另一个列表并将值 7 添加到该列表中。创建新列表后，新列表将链接到包含值 2 的列表。

• 键值 12 的索引是：

index = h(12) = (2(12)+3)%10 = 7

根据上面的计算，值 12 必须存储在索引 7 处，但值 2 存在于索引 7 处。所以，我们将创建一个新列表并将 12 添加到列表中。新创建的列表将链接到包含值 7 的列表。

下面表格显示了与每个键值相关的计算索引值：

闭定址法

在闭定址法中，有三种技术用于解决冲突：

1. 线性探测
2. 二次探测
3. 双重哈希技术

线性探测

线性探测是开放寻址法的一种形式。众所周知，哈希表中的每个单元格都包含一个键值对，因此当一个新键映射到一个已被另一个键占用的单元格而发生冲突时，线性探测技术会搜索最近的空位置并将新键添加到该空单元格中。在这种情况下，搜索是按顺序进行的，从发生冲突的位置开始，直到找到空单元格为止。

让我们通过一个例子来理解线性探测。

考虑上面线性探测的例子。

A = 3, 2, 9, 6, 11, 13, 7, 12 其中 m = 10，h(k) = 2k+3

键值 3、2、9、6 分别存储在索引 9、7、1、5 处。11 的计算索引值为 5，该索引已被另一个键值，即 6 所占用。当应用线性探测时，离索引 5 最近的空单元格是 6；因此，值 11 将添加到索引 6。

下一个键值是 13。当应用哈希函数时，此键值的索引值为 9。索引 9 处的单元格已被占用。当应用线性探测时，离索引 9 最近的空单元格是 0；因此，值 13 将添加到索引 0。

下一个键值是 7。当应用哈希函数时，此键值的索引值为 7。索引 7 处的单元格已被占用。当应用线性探测时，离索引 7 最近的空单元格是 8；因此，值 7 将添加到索引 8。

下一个键值是 12。当应用哈希函数时，此键值的索引值为 7。索引 7 处的单元格已被占用。当应用线性探测时，离索引 7 最近的空单元格是 2；因此，值 12 将添加到索引 2。

二次探测

在线性探测的情况下，搜索是线性进行的。相比之下，二次探测是一种开放寻址技术，它使用二次多项式进行搜索，直到找到一个空槽。

它也可以定义为允许在从 (u+i²)%m 其中 i=0 到 m-1 开始的第一个空位置插入 ki。

让我们通过一个例子来理解二次探测。

考虑我们在线性探测中讨论过的相同示例。

A = 3, 2, 9, 6, 11, 13, 7, 12 其中 m = 10，h(k) = 2k+3

键值 3、2、9、6 分别存储在索引 9、7、1、5 处。由于没有发生冲突，因此我们无需对这些键值应用二次探测技术。

11 的索引值为 5，但该位置已被 6 占用。因此，我们将应用二次探测技术。

当 i = 0 时

Index= (5+0²)%10 = 5

当 i=1 时

Index = (5+1²)%10 = 6

由于位置 6 是空的，因此值 11 将添加到索引 6。

下一个元素是 13。当对 13 应用哈希函数时，索引值变为 9，这我们在链地址法中已经讨论过。在索引 9 处，单元格已被另一个值，即 3 占用。因此，我们将应用二次探测技术来计算空位置。

当 i=0 时

Index = (9+0²)%10 = 9

当 i=1 时

Index = (9+1²)%10 = 0

由于位置 0 是空的，因此值 13 将添加到索引 0。

下一个元素是 7。当对 7 应用哈希函数时，索引值变为 7，这我们在链地址法中已经讨论过。在索引 7 处，单元格已被另一个值，即 7 占用。因此，我们将应用二次探测技术来计算空位置。

当 i=0 时

Index = (7+0²)%10 = 7

当 i=1 时

Index = (7+1²)%10 = 8

由于位置 8 是空的，因此值 7 将添加到索引 8。

下一个元素是 12。当对 12 应用哈希函数时，索引值变为 7。当我们观察哈希表时，我们会发现索引 7 处的单元格已被值 2 占用。因此，我们对 12 应用二次探测技术来确定空位置。

当 i=0 时

Index= (7+0²)%10 = 7

当 i=1 时

Index = (7+1²)%10 = 8

当 i=2 时

Index = (7+2²)%10 = 1

当 i=3 时

Index = (7+3²)%10 = 6

当 i=4 时

Index = (7+4²)%10 = 3

由于位置 3 是空的，因此值 12 将存储在索引 3。

最终的哈希表将是：

因此，元素的顺序是 13, 9, _, 12, _, 6, 11, 2, 7, 3。

双重散列

双重哈希是一种开放寻址技术，用于避免冲突。当发生冲突时，该技术使用键的二次哈希。它使用一个哈希值作为索引向前移动，直到找到空位置。

在双重哈希中，使用两个哈希函数。假设 h₁(k) 是用于计算位置的哈希函数之一，而 h₂(k) 是另一个哈希函数。它可以定义为“将 ki 插入到第一个空位置 (u+v*i)%m，其中 i=(0 到 m-1)”。在这种情况下，u 是使用哈希函数计算的位置，v 等于 (h₂(k)%m)。

考虑我们在二次探测中使用的相同示例。

A = 3, 2, 9, 6, 11, 13, 7, 12 其中 m = 10，并且：

h₁(k) = 2k+3

h₂(k) = 3k+1

我们知道在插入键 (3, 2, 9, 6) 时不会发生冲突，因此我们不会对这些键值应用双重哈希。

在插入键 11 到哈希表时，会发生冲突，因为 11 的计算索引值为 5，该索引已被另一个值占用。因此，我们将对键 11 应用双重哈希技术。当键值为 11 时，v 的值为 4。

现在，将 u 和 v 的值代入 (u+v*i)%m

当 i=0 时

Index = (5+4*0)%10 =5

当 i=1 时

Index = (5+4*1)%10 = 9

当 i=2 时

Index = (5+4*2)%10 = 3

由于哈希表中的位置 3 是空的；因此，键 11 被添加到索引 3。

下一个元素是 13。13 的计算索引值为 9，该索引已被另一个键值占用。因此，我们将使用双重哈希技术来查找空位置。v 的值为 0。

现在，将 u 和 v 的值代入 (u+v*i)%m

当 i=0 时

Index = (9+0*0)%10 = 9

由于 v 的值为零，因此在所有迭代（从 0 到 m-1）中，我们将得到 9 值。因此，无法将 13 插入哈希表。

下一个元素是 7。7 的计算索引值为 7，该索引已被另一个键值占用。因此，我们将使用双重哈希技术来查找空位置。v 的值为 2。

现在，将 u 和 v 的值代入 (u+v*i)%m

当 i=0 时

Index = (7 + 2*0)%10 = 7

当 i=1 时

Index = (7+2*1)%10 = 9

当 i=2 时

Index = (7+2*2)%10 = 1

当 i=3 时

Index = (7+2*3)%10 = 3

当 i=4 时

Index = (7+2*4)%10 = 5

当 i=5 时

Index = (7+2*5)%10 = 7

当 i=6 时

Index = (7+2*6)%10 = 9

当 i=7 时

Index = (7+2*7)%10 = 1

当 i=8 时

Index = (7+2*8)%10 = 3

当 i=9 时

Index = (7+2*9)%10 = 5

由于我们检查了所有 i 的情况（从 0 到 9），但没有找到合适的插入 7 的位置。因此，键 7 无法插入哈希表。

下一个元素是 12。12 的计算索引值为 7，该索引已被另一个键值占用。因此，我们将使用双重哈希技术来查找空位置。v 的值为 7。

现在，将 u 和 v 的值代入 (u+v*i)%m

当 i=0 时

Index = (7+7*0)%10 = 7

当 i=1 时

Index = (7+7*1)%10 = 4

由于位置 4 是空的；因此，键 12 被插入到索引 4。

最终的哈希表将是：

元素的顺序是 _, 9, _, 11, 12, 6, _, 2, _, 3。