《算法技术手册》变种

基于散列查找的一个主要变种是修改了处理冲突的策略。与其在槽中放入一个元素的链表，我们能够使用一种叫做开放定址的技术，这种技术直接将冲突元素存储在散列表A中。如图5-7所示。使用了开放定址技术，散列表减少了存储开销，例如在冲突的链表中使用指针指向元素。使用开放定址技术，我们将散列函数调整成为带两个参数的函数，h(u,j)=i,u∈U，i和j都是在范围[0,b)中的整数，b是A的规模。一般来说，我们使h(u,0)=i=h'(u)，h'是之前描述过的一个散列函数。如果A[i]的槽被占用了，并且这个元素和目标元素不匹配，我们计算h(u,1)的值。如果这个值指向的槽还是被占用了，并且这个元素和目标元素不匹配，那么我们计算h(u,2)的值，我们将重复这个过程，直到目标元素被找到，或者槽是空，或者散列函数产生了一个我们之前已经访问过得槽（此时就产生了一个错误）。

假设我们能够确保我们不会重新访问一个槽，那么这种方法的最坏性能是O(b)。开放定址技术在查找时表现非常好。即使在一个不成功的查找中，期望的探测数目也只是1/(1-α)，并且最坏情况下，成功查找的性能时(1/α)ln(1/1-α)[1]；详细信息请参见算法导论（Cormen等，2001）。开放定址技术中有两种广泛使用的探测方法。第一种是线性探测，这种方法下，我们的散列函数是h(u,j)=(h'(u)+j)mod n。当我们发现有冲突时，我们简单地查看散列表中的下一个槽，使用这个散列函数构成一个环形的查找。这个方法受元素的分布范围影响较大，当元素分布比较密集时，将会导致需要探测很多槽，尤其是α接近于1.0时。为了避免这种情况，我们可以使用二次方探测，散列函数变为h(u,j)=(h'(u)+f(j))mod m，f是j的一个二次方函数。

在表5-5，我们看到在强制使用散列表不进行重散列之后，节省了大量的时间。如果在一个元素插入之前，原散列表的负载因子已经非常高了，那么一个重散列操作是有必要的。当散列表包含的元素比其预想的要多时，那么可以调整自身的大小。最典型的方式就是将其桶的数目加倍然后加一（因为散列表通常包含奇数个桶）。当只有很少的桶可用时，所有表中存在的元素必须重散列以放到新的位置。这是一个昂贵的操作，但是能够减少未来查找的总开销，不过这个操作不能非常频繁，要不然散列表的性能将会退化。当你对散列表的性能不满时，你必须允许散列表能够重散列使得元素平均分布到散列表中。java.util.Hashtable默认的负载因子是0.75；如果你将这个值设为n/b，那么它将永远不会重散列。

之前的“使用环境”一节中的例子使用了一个静态的字符串集合。当面对这种特殊情况时，我们能够通过使用完美的散列函数，得到最优化的性能。完美的散列使用两个散列函数。我们用一个标准的散列函数来索引主表A。每一个槽，A[i]。指向一个小得多的二级散列表，Si，这个散列表和散列函数hi绑定。如果有k个键值映射到槽A[i]。那么Si将包含k2个槽。这看起来浪费了很多内存，但是明智地选择初始散列函数能够减少这种浪费。选择合适的散列函数能够保证在二级表中不会存在冲突。也就是说，我们能够得到一个性能为O(1)的算法。完美散列分析的细节在算法导论（Cormen等，2001）中能够找到。Doug Schmidt（1990）发表过一篇非常优秀的论文，论述了完美散列操作。网络上有一些免费的多种语言的完美散列函数生成器可以下载。

一般来说，虽然有着很多潜在的元素ei会得到特定的键值k，但是散列表也许被设计成只能存储其中的一个元素。也就是说，如果ei∈C且ej∈C，那么i=j当且仅当key(ei)=key(ej)。有这个限制的原因是使得给定键值key(e)下，能够快速寻找到元素e。如果原始集合C包含两个相同的元素，那么仅仅只有一个会正确存储到散列表A中[2]。