我有一个关于哈希表大小和模块化哈希的问题。我指的哈希算法如下:
hash_key % table_size = array_index.
我正在阅读一本算法教科书,其中给出了以下建议:
如果表大小不是素数,则可能会出现键的所有位在确定 array_index 时不起作用的情况。
谁能用一个例子来解释这到底意味着什么?
你要避免的是常见因素。有一个定理指出每个数字都可以表示为素数的乘积。
因此,如果你有一个素数作为 mod。您不会分享该部门的任何因素。
比如说 A % 30,所以 2、3 和 5 的任何倍数都将共享除法中的因数,并且该因数在除法中将毫无用处。
250/30 = 50 / 6 = 25 / 3
你想尽量减少无用的因素。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)