除留余数法介绍除留余数法此方法为最常用的构造散列函数方法。对于散列表长为m的散列函数公式为:
mod是取模(求余数)的意思。事实上,这方法不仅可以对关键字直接取模,也可在折叠、平方取中后再取模。 一个例子
有一个关键字,它有12个记录,现在我们要针对它设计一个散列表。如果采用除留余数法,那么可以先尝试将散列函数设计为f(key) = key mod 12的方法。比如29 mod 12 = 5,所以它存储在下标为5的位置。 不过这也是存在冲突的可能的,因为12 = 2×6 = 3×4。如果关键字中有像18(3×6)、30(5×6)、42(7×6)等数字,它们的余数都为6,这就和78所对应的下标位置冲突了。
但是我们如果不选用p=12来做除留余数法,而选用p=ll,则结果如下: 这个时候就只有12和144有冲突,相对来说,就要好很多了。 如何合理选取p值
|
|