《算法导论》散列函数问题？

xtlx2000

《算法导论》P138 散列函数一节中，
1、除法散列法：h(k) = k mod m，m不应是2的幂，原因没看懂？
2、乘法散列法：h(k) = [m(kA mod 1)],一班选择m为2的某个次幂，原因也没看懂？
请教。。。。

liexusong

除法散列法：h(k) = k mod m，m不应是2的幂
因为要一个素数吧！

yylogo

回复 1# xtlx2000


    算法导论理论部分从来不看..

comesun_cpp

除法散列法：h(k) = k mod m，m不应是2的幂
因为要一个素数吧！
liexusong 发表于 2010-09-23 15:36

    9呢?

wkq5325

除法散列法：h(k) = k mod m，m不应是2的幂
2的幂的情况下，就是你的k的p位之前必是被整除的，那么结果就只和后面的p位相关，
而非幂的情况，不会整除，所以会反映k的前面的各位情况。
乘法的情况类似吧

au9ustine

个人猜想：
k mod m时，m之所以为素数时为了使得k在m所在的素数域上保持唯一性（根据欧拉定理和费马小定理）
m(kA mod 1)时，kA在1所在的域已经存在了唯一的乘法逆元，所以当被扩大m倍时，mkA性质不变

mirnshi

搞理论研究吗？如果仅仅是用，有很多的选择，很多教科书上的hash算法，只能称其为hash概念演示，没有任何实用价值。

goubao198562

不在乎读的书多

zhangsuozhu

除法散列法：h(k) = k mod m，m不应是2的幂
2的幂的情况下，就是你的k的p位之前必是被整除的，那么结果就只 ...
wkq5325 发表于 2010-09-25 08:14

    这个好象靠点普。