哈希方法

实现哈希主要有两种方法

1. 链式哈希
2. 开放寻址哈希

1. 链式哈希

在链式哈希中，S 中的元素存储在大小为 m 的哈希表 T [0...m-1] 中，其中 m 比 S 的大小 n 略大。哈希表被称为有 m 个槽。与哈希方案相关联的是哈希函数 h，它是从 U 到 {0...m-1} 的映射。每个键 k ∈ S 存储在位置 T [h (k)] 中，我们说 k 被哈希到槽 h (k) 中。如果 S 中有多个键被哈希到同一个槽中，那么我们就有一个冲突。

在这种情况下，所有哈希到同一个槽的键都放在与该槽关联的链表中，该链表称为槽中的链。哈希表的负载因子定义为 ∝=n/m，它表示每个槽的平均键数。我们通常在 m=θ(n) 的范围内操作，所以 ∝ 通常是一个常数，通常 ∝<1。

通过链接解决冲突

在链接中，我们将所有哈希到同一槽的元素放入同一个链表中。如图所示，槽 j 包含一个指向存储的所有哈希到 j 的元素的列表头的指针；如果没有这样的元素，则槽 j 包含 NIL。

图：通过链接解决冲突。

每个哈希表槽 T [j] 包含一个链表，其中包含所有哈希值为 j 的键。

例如, h (k1) = h (k4) 且 h (k5) = h (k7) = h (K2)。链表可以是单链或双链；我们将其显示为双链，因为这样删除速度更快。

链式哈希分析

给定一个包含 m 个槽并存储 n 个元素的哈希表 T，我们将 T 的负载因子 α 定义为 n/m，即存储在链中的平均元素数。因此，搜索的最坏情况运行时间为 θ(n) 加上计算哈希函数的时间——不比我们对所有元素使用一个链表好多少。显然，哈希表不是因为它们的最坏情况性能而被使用的。

哈希的平均性能取决于哈希函数 h 在平均情况下如何将要存储的键集分布在 m 个槽中。

示例：让我们考虑将元素 5、28、19、15、20、33、12、17、10 插入到链式哈希表中。假设哈希表有 9 个槽，哈希函数为 h (k) = k mod 9。

解决方案：链式哈希表的初始状态

插入 5

为 T [5] 创建一个链表并在其中存储值 5。

类似地，插入 28。h (28) = 28 mod 9 = 1。为 T [1] 创建一个链表并在其中存储值 28。现在插入 19 h (19) = 19 mod 9 = 1。在链表的开头将值 19 插入槽 T [1] 中。

因此，插入键 10 后的链式哈希表是

2. 开放寻址哈希

在开放寻址中，所有元素都存储在哈希表本身中。也就是说，每个表条目都包含动态集或 NIL 的一个组件。当搜索一个项目时，我们会一致地检查表槽，直到找到所需的对象，或者确定该元素不在表中。因此，在开放寻址中，负载因子 α 永远不能超过 1。

开放寻址的优点是它避免了指针。在这种情况下，我们计算要检查的槽序列。通过不共享指针释放的额外内存为哈希表提供了相同内存量的更多槽，从而可能减少冲突并加快检索速度。

检查哈希表中位置的过程称为探测。

因此，哈希函数变为

使用开放寻址，我们要求对于每个键 k，探测序列

HASH-INSERT 过程将哈希表 T 和键 k 作为输入

HASH-INSERT (T, k)
 1. i ← 0
 2. repeat j ← h (k, i)
 3. if T [j] = NIL
 4. then T [j] ← k
 5. return j
 6. else ← i= i +1
 7. until i=m
 8. error "hash table overflow"

如果 HASH-SEARCH 过程发现槽 j 包含键 k，或者键 k 不在表 T 中，则 HASH-SEARCH 过程将哈希表 T 和键 k 作为输入，并返回 j。

HASH-SEARCH.T (k)
 1. i ← 0
 2. repeat j ← h (k, i)
 3. if T [j] =j
 4. then return j
 5. i ← i+1
 6. until T [j] = NIL or i=m
 7. return NIL