首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》变种

关灯直达底部

基于散列查找的一个主要变种是修改了处理冲突的策略。与其在槽中放入一个元素的链表,我们能够使用一种叫做开放定址的技术,这种技术直接将冲突元素存储在散列表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)的值,我们将重复这个过程,直到目标元素被找到,或者槽是空,或者散列函数产生了一个我们之前已经访问过得槽(此时就产生了一个错误)。

图 5-7 开放定址

假设我们能够确保我们不会重新访问一个槽,那么这种方法的最坏性能是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]。

[1]ln为以e为底的自然对数。 [2]GPERF for C/C++可以在http://www.gnu.org/software/gperf/下载到,JPERF for Java可以在http://www.anarres.org/projects/jperf/下载到。