哈希导论

假设我们要创建一个系统来存储包含电话号码（作为键）的员工记录。我们还希望以下查询能够快速运行：

• 插入电话号码和任何必要信息。
• 查找电话号码并获取信息。
• 删除电话号码和任何相关信息。

我们可以考虑使用以下数据结构来存储各种电话号码的信息：

• 电话号码和记录的集合。
• 电话号码和记录在此列表中链接。
• 电话号码作为平衡二叉搜索树的键。
• 直接访问表。

对于数组和链表，我们必须进行线性搜索，这在实践中可能成本很高。如果我们使用数组并将数据保持排序状态，我们可以使用二分查找以 O(Logn) 的时间找到电话号码，但插入和删除操作会变得昂贵，因为我们必须保持数据排序。

通过平衡二叉搜索树，我们获得了中等的搜索、插入和删除时间。所有这些操作都将在 O(Logn) 时间内完成。

“访问列表”（access-list）是指用于控制网络流量和减少网络攻击的规则集。ACL 用于根据传入或传出流量定义的规则集来过滤网络流量。

另一种选择是使用直接访问表，在这种表中，我们创建一个大型数组，并将电话号码用作索引。如果电话号码不存在，则数组条目为 NIL；否则，数组条目存储指向对应于电话号码的记录的指针。在时间复杂度方面，这个解决方案是最好的；我们可以以 O(1) 的时间执行所有操作。例如，要插入电话号码，我们创建一个包含电话号码详细信息的记录，使用电话号码作为索引，并将指向新创建记录的指针存储在表中。

这个解决方案有许多实际的缺点。这个解决方案的第一个问题是所需的额外空间量。例如，如果一个电话号码有 n 位数字，我们需要 O(m * 10n) 的表空间，其中 m 是指向记录的指针的大小。另一个问题是，编程语言中的整数无法容纳 n 位数字。

由于上述限制，不能总是使用直接访问表。在实践中，哈希是几乎所有此类情况都可以使用的解决方案，并且优于数组、链表和平衡 BST 等上述数据结构。哈希的平均搜索时间为 O(1)（在合理假设下），最坏情况为 O(n)。让我们分解一下什么是哈希。

哈希到底是什么意思？

哈希是一种流行的快速存储和检索数据的方法。使用哈希的主要原因在于，它通过执行最优搜索来产生最优结果。

为什么你应该使用哈希？

如果我们尝试在平衡二叉搜索树中搜索、插入或删除任何元素，相同操作的时间复杂度为 O(logn)。现在，有时我们的应用程序需要以更快、更优化的方式执行相同的操作，这就是哈希发挥作用的地方。哈希中的所有上述操作都可以在 O(1) 或常数时间内完成。了解哈希的最坏情况时间复杂度仍然是 O(n)，但平均时间复杂度为 O(1) 至关重要。

现在让我们看一些基本的哈希操作。

基本操作

• HashTable：使用此操作创建新的哈希表。
• Delete：此操作用于从哈希表中删除特定的键值对。
• Get：此操作用于在哈希表中查找键并返回与该键关联的值。
• Put：此操作用于将新的键值对添加到哈希表中。
• DeleteHashTable：此操作用于删除哈希表。

描述哈希函数。

• 哈希函数是一种固定的过程，它将键转换为哈希键。
• 此函数将键转换为一个长度受限的值，称为哈希值或哈希。
• 虽然哈希值通常小于原始值，但它仍然代表原始字符字符串。
• 数字签名被传输，然后将哈希值和签名一起提供给接收者。接收者使用相同的哈希算法生成的哈希值与随消息收到的哈希值进行比较。
• 如果哈希值匹配，则消息已成功发送。

哈希表：它是什么？

• 哈希表或哈希映射是一种用于存储键值对的数据结构。
• 它是一系列已组织好的材料，以便以后轻松访问。
• 它使用哈希函数计算数组（桶或槽）中的索引，然后可以从该索引中定位所需的值。
• 数组中的每个列表都称为一个桶。
• 它根据键包含值。
• Map 接口使用哈希表实现，哈希表还扩展了 Dictionary 类。
• 哈希表是同步的，并且只包含唯一组件。

哈希的组成部分

• 哈希表：一个存储指向对应于特定电话号码的记录的指针的数组。如果没有任何现有电话号码的哈希函数值等于该条目的索引，则哈希表中的条目为 NIL。简单来说，哈希表是数组的推广。哈希表提供了存储数据集合的功能，使得以后可以轻松查找这些数据。这使得元素搜索非常高效。
• 哈希函数：一个将大电话号码减少为小的实际整数值的函数。在哈希表中，映射的整数值用作索引。因此，简单来说，哈希函数用于将给定的键转换为特定的槽索引。其主要功能是将每个可能的键映射到一个唯一的槽索引。如果每个键都映射到一个不同的槽索引，则该哈希函数称为完美哈希函数。尽管构造理想哈希函数非常困难，但作为程序员，我们的职责是以最小化冲突概率的方式来完成它。本节将介绍冲突。

一个好的哈希函数应该具备以下特性：

• 易于计算。
• 键应该平均分布在所有表位置。
• 应尽量减少冲突。
• 负载因子应较低（表中项目数除以表的大小）。

例如，对于电话号码，使用前三位数字是一个糟糕的哈希函数。考虑后三位数字是一个更好的函数。请注意，这个哈希函数可能不是最好的。可能有更好的选择。

• 处理冲突：由于哈希函数只为大键返回一个小数字，因此可能存在两个键产生相同结果的情况。当新添加的键对应于一个已占用的哈希表槽时，就会发生冲突，需要使用冲突处理机制来处理。处理冲突的方法如下：
  • 使每个哈希表单元指向一个具有相同哈希函数值的记录的链表，称为“链表法”（chaining）。虽然链表法很简单，但需要比表本身更多的内存。
  • 开放寻址（Open Addressing）：在开放寻址中，哈希表本身用作所有项的存储位置。每个表条目中都存在记录或 NIL。在查找元素时，我们逐个检查每个表槽，直到找到所需的元素，或者可以明显地确定该元素不在表中。

线性探测

在数据结构中，哈希会产生已经被用来存储值的数组索引。在这种情况下，哈希执行搜索操作并线性探测下一个空单元格。

在哈希算法中，处理哈希表冲突的最简单方法称为线性探测（linear probing）。任何发生的冲突都可以通过顺序搜索找到。

二次哈希（Double Hashing）

二次哈希方法使用两个哈希函数。当第一个哈希函数导致冲突时，使用第二个哈希函数。为了存储值，它提供了一个偏移索引。

二次哈希方法的公式如下：

(firstHash(key) + i * secondHash(key)) % sizeOfTable

偏移值由 i 表示。偏移值不断增加，直到遇到一个空槽。