对hash函数的求余方式中Seed为大素数的迷惑(85分)

S

snowrain

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-21

• #1

对hash函数的求余方式中Seed为大素数的迷惑，很多文章都说hash算法用求余的方式来定位hash表时，index=num mod seed
Seed为大素数时，余数分布比较均匀，而当Seed的约数很多时，余数分布很不均匀，虽然余数的范围都为(0..Seed-1);
hoho,还是不明白为什么？
我觉得由于num是随机的，那么无所谓Seed是素数还是约数很多，
index落到(0..Seed-1)的几率几乎是相等的
请教各位大侠，这是为什么？能帮帮我吗？

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-22

• #2

除留余数法:
设散列表中允许的地址数为m,取一个不大于m，但最接近于或等于m的质数p,或选取一个不
小于20的质因数的合数作为除数，利用以下公式把关键码转换成散列地址。散列函数为:
hash(key) = key % p
其中,“%”是整数除法取余的运算，要求这时的质数p不是接近2的幂。

——上面这么写，没有说明任何道理。我看科学出版社的《数据结构》中写到：“从经验
得知，p宜选取不包含小于20的质数的合数。这样可以减少冲突的可能性。”
虽然理论上p应该没有什么限制，但是在实际使用中，由于key的分布特点以及可能涉及到
2次散列的原因，前人们才总结出上述经验。我认为，应该具体问题具体分析，如果你的key
满足均匀分布，p的选择应该没有这些限制的。

 

S

snowrain

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-24

• #3

谢谢creation-zy的回答。
呵呵，我只是想问问，为什么老是喜欢取质数，如果某合数约数很多，取这个合数作为除数，
有什么后果？(比取质数有什么不同)，能否举例说明一下？
谢谢！

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-24

• #4

呵呵,举个例子吧.
Seed=7时,理论上n mod seed会均匀分布在0..6上.
Seed=8时:
n均匀分布在0..7上, 当n为奇数时或n<8时.
n均匀分布在0..3上, 当n mod 2=0且n>=8时.
n均匀分布在0..1上, 当n mod 4=0且n>=8时.
n只会分布在0上, 当n mod 8=0且n>=8时.
呵呵，虽然7和8只差1,但由于8的因子多,所以导致于8有公因子的n的分布不均匀.
换个更一般的例子,对于任意的Seed,若它的因子越多,余数分布越不均匀.

 

S

snowrain

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-24

• #5

谢谢LeeChange的回答。
但是你所说的“当n mod 8=0且n>=8时.”
如果n随机，n mod 8 = 0,1,2,3,4,5,6,7的几率是相等的,那么n分布在0.1.2.3.4.5.6.7上的几率也是相等的。
分布也应该是均匀的呀。
还是不懂，继续请教！

 

C

creation-zy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-25

• #6

呵呵，我明白了，LeeChange兄的意思是这样的：
如果Seed为质数，那么散列值应该也是均匀分布。
如果Seed为合数，并且质因数较小，比如Seed为8，那么：
被散列的数值完全均匀分布时，散列值也会均匀分布在0..7之间——没有任何问题；
被散列的数值都是4的倍数时，散列值只会是0或4；
被散列的数值都是2的倍数时，散列值只会是0到6的偶数；
被散列的数值都是10的倍数时，散列值只会是0到6的偶数。
我估计是因为被散列的数据不能做到完全均匀分布（比如，绝大多数都是10的倍数），才
需要仔细的选择Seed值。——如果你的数据基本均匀，就不必有任何顾虑。