4.1. 开放散列¶

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

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

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

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

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

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