7.4.1. 开放哈希¶

虽然哈希函数的目标是尽量减少冲突，但在实践中有些冲突无法避免。 因此，哈希实现必须包含某种形式的冲突解决策略。 冲突解决技术可以分为两类： 开放哈希 （也称 分离链接 ）和 闭哈希（closed hash system） （也称 开放寻址 ）。 （是的，当"开放哈希"的含义与"开放寻址"相反时确实令人困惑，但不幸的是，事实就是如此。） 两者的区别在于：冲突是存储在表外（开放哈希）， 还是冲突导致把其中一条记录存储在表中的另一个槽位（闭哈希）。

开放哈希最简单的形式是把哈希表中的每个槽位定义为一条链表的表头。所有哈希到某个特定槽位的记录都放在该槽位的链表上。下图展示了一个哈希表，其中每个槽位都指向一条链表，用于保存与该槽位关联的记录。所使用的哈希函数是简单的取模函数。

槽位链表中的记录可以按多种方式排序：按插入顺序、按键值顺序，或按访问频率顺序。按键值对链表排序，在查找失败时具有优势，因为一旦遇到比待查键更大的键，我们就知道可以停止查找该链表。如果链表中的记录无序或按频率排序，那么查找失败时需要访问链表上的每一条记录。

给定一个长度为 \(M\) 、存储 \(N\) 条记录的哈希表，哈希函数将（理想情况下）把记录均匀地散布到表中的 \(M\) 个位置上，平均每条链表有 \(N/M\) 条记录。假设表中的槽位多于要存储的记录数，我们可以期望只有少数槽位包含多条记录。当某条链表为空或只有一条记录时，查找只需访问该链表一次。因此，哈希的平均成本应当是 \(\Theta(1\))。然而，如果聚集导致许多记录哈希到少数几个槽位，那么访问一条记录的成本就会高得多，因为必须查找链表上的许多元素。

当哈希表保存在主存中、且各条链表用标准的内存链表实现时，开放哈希最为合适。要以高效的方式把开放哈希表存储在磁盘上是很困难的，因为给定链表的成员可能存储在不同的磁盘块上。这会导致在查找特定键值时需要多次访问磁盘，从而违背了使用哈希的目的。

开放哈希与箱排序（Binsort）之间有相似之处。看待开放哈希的一种方式是：每条记录只是被放进一个箱（bin）中。虽然多条记录可能哈希到同一个箱，但这种初始分箱仍应大大减少一次查找操作所访问的记录数。类似地，简单的箱排序把每个箱中的记录数减少到一个很小的数目，从而可以用其他方式对其进行排序。