use*_*310 1 algorithm hash data-structures
这是我关于stackflow的第一个问题.如您所知,我是学习算法和数据结构的新手.
当使用除法方法来创建散列函数(即h(k)= k mod m)时,建议(例如通过CLRS)使用对于除数m而言不太接近2的幂的素数.有人可以向我解释为什么选择m作为复合数是坏的吗？
Igo*_*sky 13
考虑如果m是偶数并且所有k值都是偶数的情况.然后,哈希值也将是均匀的.
例如,考虑m = 6哈希偶数值的情况:
Input values: 0, 2, 4, 6, 8, 10, 12, 14, 16, ...
Hash values: 0, 2, 4, 0, 2, 4, 0, 2, 4, ...
如果将这些哈希值用作表的索引,则表的一半将不使用.另一方面,如果m是素数,即使输入值都具有公共因子,您也将获得均匀分布的哈希值.
考虑相同的输入值,但m = 7:
Input values: 0, 2, 4, 6, 8, 10, 12, 14, 16, ...
Hash values: 0, 2, 4, 6, 1, 3, 5, 0, 2, ...
尽管输入值都是偶数,但哈希值仍然均匀分布在[0..6]上.
总而言之,如果m是素数,那么即使所有输入值都可以被共同的素数因子(m除外),你仍然可以获得均匀的哈希值分布.