数据结构中的哈希

哈希是计算机科学中一种流行的技术，它涉及将大型数据集映射到固定长度的值。它是一个将可变大小的数据集转换为固定大小数据集的过程。高效执行查找操作的能力使得哈希成为数据结构中的一个基本概念。

什么是哈希？

哈希算法用于将输入（如字符串或整数）转换为固定大小的输出（称为哈希码或哈希值）。然后使用此哈希值作为数组或哈希表中的索引来存储和检索数据。哈希函数必须是确定性的，这意味着对于给定的输入，它总是产生相同的结果。

哈希通常用于为数据创建一个唯一标识符，该标识符可用于在大型数据集中快速查找该数据。例如，Web 浏览器可以使用哈希来安全地存储网站密码。当用户输入其密码时，浏览器会将其转换为哈希值，并将其与存储的哈希值进行比较以验证用户。

什么是哈希键？

在哈希的上下文中，哈希键（也称为哈希值或哈希码）是由哈希算法生成的固定大小的数值或字母数字表示。它通过一个称为哈希的过程从输入数据（如文本字符串或文件）派生而来。

哈希涉及对输入数据应用特定的数学函数，该函数会生成一个唯一的哈希键，该键通常是固定长度的，无论输入大小如何。生成的哈希键本质上是原始数据的数字指纹。

哈希键具有多种用途。它通常用于数据完整性检查，因为即使输入数据发生微小变化，也会产生截然不同的哈希键。哈希键还用于在哈希表或数据结构中进行高效的数据检索和存储，因为它们允许快速查找和比较操作。

哈希如何工作？

哈希过程可分为三个步骤：

• 输入：要哈希的数据被输入到哈希算法中。
• 哈希函数：哈希算法接收输入数据并应用数学函数来生成固定大小的哈希值。哈希函数的设计应确保不同的输入值产生不同的哈希值，并且输入的微小变化会导致输出发生大的变化。
• 输出：返回哈希值，该哈希值用作数据结构中存储或检索数据的索引。

哈希算法

有许多哈希算法，每种算法都有其独特的优点和缺点。最流行的算法包括以下几种：

• MD5：一种广泛使用的哈希算法，可生成 128 位哈希值。
• SHA-1：一种流行的哈希算法，可生成 160 位哈希值。
• SHA-256：一种更安全的哈希算法，可生成 256 位哈希值。

哈希函数

哈希函数：哈希函数是一种数学运算，它接受输入（或键）并输出一个称为哈希码或哈希值的固定大小的结果。为了保证确定性，哈希函数必须始终为相同的输入产生相同的哈希码。此外，哈希函数应为每个输入生成一个唯一的哈希码，这被称为哈希属性。

有不同类型的哈希函数，包括：

• 除法法

此方法涉及将键除以表的大小，并取余数作为哈希值。例如，如果表的大小为 10，键为 23，则哈希值为 3 (23 % 10 = 3)。

• 乘法法

此方法涉及将键乘以一个常数，并取乘积的小数部分作为哈希值。例如，如果键为 23，常数为 0.618，则哈希值为 2 (floor(10*(0.61823 - floor(0.61823))) = floor(2.236) = 2)。

• 通用哈希

此方法涉及使用一组哈希函数中的一个随机哈希函数。这确保了哈希函数不会偏向任何特定的输入，并且可以抵抗攻击。

冲突解决

哈希中的主要挑战之一是处理冲突，当两个或多个输入值产生相同的哈希值时会发生冲突。有各种技术用于解决冲突，包括：

• 链表法：在此技术中，每个哈希表槽包含一个链接列表，其中包含所有具有相同哈希值的项。此技术简单易于实现，但当链表过长时可能导致性能下降。
• 开放寻址法：在此技术中，当发生冲突时，算法通过连续探测槽来查找哈希表中的一个空槽，直到找到一个空槽。当负载因子较低时，此技术可能比链表法更有效，但在负载因子较高时可能导致聚集和性能下降。
• 双重哈希：这是开放寻址法的一个变体，当发生冲突时，它使用第二个哈希函数来确定要探测的下一个槽。此技术有助于减少聚集并提高性能。

冲突解决示例

让我们继续以大小为 5 的哈希表为例。我们想在哈希表中存储键值对“John: 123456”和“Mary: 987654”。这两个键都产生相同的哈希码 4，因此会发生冲突。

我们可以使用链表法来解决冲突。我们在索引 4 处创建一个链表，并将键值对添加到列表中。此时的哈希表如下所示：

0:

1:

2:

3:

4: John: 123456 -> Mary: 987654

5:

哈希表

哈希表是一种在数组中存储数据的数据结构。通常，会选择一个比可以放入哈希表中的元素数量更大的数组大小。使用哈希函数将键映射到数组中的一个索引。

当要在哈希表中添加新元素时，哈希函数用于定位需要插入元素的索引。如果没有发生冲突，该元素将被添加到该索引。如果发生冲突，则使用冲突解决方法在数组中查找下一个可用槽。

为了从哈希表中检索元素，哈希函数用于定位存储该元素的索引。如果未在该索引处找到元素，则使用冲突解决方法在链表中（如果使用链表法）或在下一个可用槽中（如果使用开放寻址法）搜索该元素。

哈希表操作

可以对哈希表执行几种操作，包括：

• 插入：将新的键值对插入到哈希表中。
• 删除：从哈希表中删除键值对。
• 搜索：在哈希表中搜索键值对。

创建哈希表

哈希经常用于构建哈希表，哈希表是一种数据结构，可以快速地进行数据插入、删除和检索。构成哈希表的桶数组中的每个数组可以存储一个或多个键值对。

要创建哈希表，我们首先需要定义一个哈希函数，该函数将每个键映射到数组中的一个唯一索引。一个简单的哈希函数可能是将键中字符的 ASCII 值相加，然后除以数组大小取余数。但是，此哈希函数效率低下，可能导致冲突（两个键映射到同一索引）。

为了避免冲突，我们可以使用更高级的哈希函数，它们可以在数组中更均匀地分布哈希值。一种流行的算法是 djb2 哈希函数，它使用按位运算来生成哈希值。

此哈希函数以字符串作为输入，并返回一个无符号长整数哈希值。该函数初始化哈希值为 5381，然后遍历字符串中的每个字符，使用按位运算生成新的哈希值。最后返回哈希值。

C++ 中的哈希表

在 C++ 中，标准库提供了一个名为 unordered_map 的哈希表容器类。unordered_map 容器使用哈希表实现，并提供对键值对的快速访问。unordered_map 容器使用哈希函数来计算键的哈希码，然后使用开放寻址法来解决冲突。

要在 C++ 中使用 unordered_map 容器，您需要包含 头文件。以下是如何在 C++ 中创建 unordered_map 容器的示例：

说明

• 此程序演示了 C++ 中 unordered_map 容器的用法，该容器使用哈希表实现并提供对键值对的快速访问。
• 首先，程序包含必要的头文件： 和 。
• 然后，程序创建一个名为 my_map 的空 unordered_map 容器，该容器具有字符串键和整数值。这是使用语法 std::unordered_map my_map; 完成的。
• 接下来，程序使用 [] 运算符将三个键值对插入到 my_map 容器中：“apple”值为 10，“banana”值为 20，“orange”值为 30。
• 这是分别使用语法 my_map["apple"] = 10;、my_map["banana"] = 20; 和 my_map["orange"] = 30; 完成的。
• 最后，程序使用 [] 运算符和 std::cout 对象打印与“banana”键关联的值。

程序输出

将数据插入哈希表

要将键值对插入哈希表，我们首先需要为数组编制索引以存储键值对。如果另一个键映射到同一索引，则会发生冲突，我们需要适当地处理它。一种常见的方法是使用链表法，其中数组中的每个存储桶都包含一个键值对的链表，这些键值对具有相同的哈希值。

以下是如何使用链表法将键值对插入哈希表的示例：

说明

• 首先，定义了一个名为 node 的结构体，它代表哈希表中的一个节点。
• 每个节点有三个成员：一个 char* key 用于存储键，一个 int value 用于存储关联值，以及一个指向另一个节点（名为 next）的指针，用于使用链表处理哈希表中的冲突。
• 声明了一个大小为 100 的 node 指针数组，名为 hash_table。此数组将用于存储哈希表的元素。
• insert 函数接受 char* key 和 int value 作为参数。
• 它首先使用哈希函数计算给定键的哈希值，假设哈希函数已在程序其他地方定义。
• 然后使用模运算符 % 100 将哈希值缩小到适合 hash_table 数组的大小。
• 使用动态内存分配 (malloc(sizeof(node))) 创建一个新节点，并将其成员（key、value 和 next）分别赋为提供的键、值和 NULL。
• 如果 hash_table 数组中相应的槽为空 (NULL)，表示未发生冲突，则新节点直接赋给该槽 (hash_table[hash_value] = new_node)。

但是，如果 hash_table 数组中该索引处已经存在一个节点，则函数需要处理冲突。它遍历从当前节点 (hash_table[hash_value]) 开始的链表，并移动到下一个节点，直到到达末尾 (curr_node->next != NULL)。一旦到达列表末尾，新节点就会作为下一个节点附加 (curr_node->next = new_node)。

C++ 中哈希的实现

让我们看看在 C++ 中使用开放寻址法和线性探测法进行冲突解决的哈希实现。我们将实现一个存储整数的哈希表。

说明

• 此程序实现了哈希表数据结构，使用线性探测法来处理冲突。
• 哈希表是一种数据结构，它以键值对的形式存储数据，其中键使用哈希函数进行哈希以生成数组中的索引。这允许在平均情况下进行常数时间复杂度的插入、搜索和删除哈希表中的元素。
• HashTable 类有一个私有的整数数组 arr，大小为 SIZE，在构造函数中初始化为 -1。hash 函数方法接受一个整数键并返回该键的哈希值，该值仅仅是键除以 SIZE 的余数。
• insert 方法接受一个整数键，并使用哈希函数获取应插入该键的索引。
• 如果索引已被另一个键占用，则使用线性探测法在数组中查找下一个可用索引。线性探测法会检查数组中的下一个索引，直到找到空槽或键本身。
• 如果键已存在于哈希表中，则该方法会显示一条消息，说明该元素已存在。否则，它会将键插入到计算出的索引处。
• remove 方法接受一个整数键，并使用哈希函数获取该键所在的位置索引。
• 如果键不在计算出的索引处，则使用线性探测法在数组的下一个索引中搜索该键。一旦找到该键，就通过将其值设置为 -2 来将其删除。
• 如果未在哈希表中找到该键，则该方法会显示一条消息，说明未找到该元素。
• display 方法只是遍历数组并打印出所有非空键值对。
• 在 main 函数中，创建了 HashTable 类的一个实例，并通过 insert 方法将几个整数插入到哈希表中。
• 然后调用 display 方法显示哈希表的内容。调用了两次 remove 方法，一次是删除哈希表中存在的元素，另一次是删除不存在的元素。
• 在每次调用 remove 方法后调用 display 方法以显示哈希表的更新内容。
• 最后，将另一个整数插入哈希表中，然后再次调用 display 方法以显示哈希表的最终内容。

程序输出

哈希的应用

哈希在计算机科学中有许多应用，包括：

• 数据库：哈希用于高效地索引和搜索大型数据库。
• 密码学：哈希函数用于生成消息摘要，用于验证数据完整性并防止篡改。
• 缓存：哈希表用于缓存系统中，以存储频繁访问的数据并提高性能。
• 拼写检查：哈希用于拼写检查器中，以快速在词典中查找单词。
• 网络路由：哈希用于负载均衡和路由算法中，以在多个服务器之间分配网络流量。

哈希的优点

• 快速访问：哈希提供对数据的常数时间访问，使其比链表和数组等其他数据结构更快。
• 高效搜索：哈希允许快速的搜索操作，使其成为需要频繁搜索操作的应用程序的理想数据结构。
• 空间效率高：哈希可能比其他数据结构更节省空间，因为它只需要固定量的内存来存储哈希表。

哈希的局限性

• 哈希冲突：哈希可能为不同的键产生相同的哈希值，导致哈希冲突。为了处理冲突，我们需要使用链表法或开放寻址法等冲突解决技术。
• 哈希函数质量：哈希函数的质量决定了哈希算法的效率。质量差的哈希函数可能导致更多冲突，从而降低哈希算法的性能。

结论

总而言之，哈希是数据结构中一种广泛使用的技术，它提供了对数据的有效访问。它涉及使用哈希函数将大量数据映射到较小的哈希表，这减少了搜索特定数据元素所需的时间。哈希函数确保数据存储在哈希表中的唯一位置，并允许在需要时轻松检索数据。

与链表和数组等其他数据结构技术相比，哈希具有一些优点，例如更快的检索时间、高效的内存利用率以及由于使用了良好的哈希函数而减少的冲突。但是，它也有一些局限性，包括可能发生哈希冲突，以及需要一个能够将数据均匀分布到哈希表中的良好哈希函数。

总的来说，哈希是一项强大的技术，广泛应用于数据库索引、拼写检查和密码存储等许多应用程序中。通过使用良好的哈希函数并实现适当的冲突解决技术，开发人员可以优化其应用程序的性能，并为用户提供无缝的体验。