哈希函数 直接定址法 除留余数法

时间:2022-05-05 19:30:31

直接定址法

  直接定址法是以数据元素关键字k本身或它的线性函数作为它的哈希地址,即:H(k)=k  或 H(k)=a×k+b ; (其中a,b为常数)

  例1,有一个人口统计表,记录了从1岁到100岁的人口数目,其中年龄作为关键字,哈希函数取关键字本身,如图(1):

地址

A1

A2

……

A99

A100

年龄

1

2

……

99

100

人数

980

800

……

495

107

可以看到,当需要查找某一年龄的人数时,直接查找相应的项即可。如查找99岁的老人数,则直接读出第99项即可。这种哈希函数简单,并且对于不同的关键字不会产生冲突,但可以看出这是一种较为特殊的哈希函数,实际生活中,关键字的元素很少是连续的。用该方法产生的哈希表会造成空间大量的浪费,因此这种方法适应性并不强。[2]↑

除留余数法

取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址,即设定哈希函数为  Hash(key)=key mod p (p≤m),其中,除数p称作模。

除留余数法不仅可以对关键字直接取模,也可以在折叠、平方取中等运算后取模。对于除留余数法求哈希地址,关键在于模p的选择。使得数据元素集合中每一个关键字通过该哈希函数映射到内存单元的任意地址上的概率相等,从而尽可能减少发生哈希冲突的可能性。

理论研究表明,除留余数法的模p取不大于表长且最接近表长m素数时效果最好,且p最好取1.1n~1.7n之间的一个素数(n为存在的数据元素个数)。例如:当n=7时,p最好取11、13等素数。 又例图(5):

表长m

8

16

32

64

128

256

512

1000

模p

7

13

31

61

127

251

503

997

由于除留余数法的地址计算方法简单,而且在许多情况下效果较好。[2]↑

例9,公司有236个员工,而员工编号介于1000到9999,除留余数法就是员工编号除以数据个数236后,去余数即为数据的位置。编号5428员工的数据(编号5428除以236取余数得0)放数据中的第一笔,编号3512员工数据(编号3512除以236取余数得8)放数据中的第九笔…依次类推。