s****A
发帖数: 80 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: studyA (Algorithm), 信区: JobHunting
标 题: hash table的size为什么最好是个质数？
发信站: BBS 未名空间站 (Mon Feb 18 17:32:47 2013, 美东)
而且书上还说，如果来search字符串的话,最好这样计算hash function
( char[0] x s^n + char[1] x s^(n-1)+...+char[n] )% M
这里如果s和M不互质的话，就会导致得到的index分布不uniform
我没想明白为什么，我怎么觉得不管是否互质，只要输入分布uniform得到的index还是
在0到M-1之间uniform分布的啊
谁能给举个例子说明一下s和M不互质的情况下会出什么问题？
最好是例子，一看就明白
谢谢！ | X****r
发帖数: 3557 | 2 输入未必是均匀分布的。s和M互质可以最大范围地使用输入每一个字符的信息。
极端一点，M=s，那hash就等于输入的最后一个字符，前面全部没有用上。
或者比如s=256，M=1024，那只有输入的倒数第二个字符的最低两位和
最后一个字符起了作用。
【在 s****A 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: studyA (Algorithm), 信区: JobHunting
: 标 题: hash table的size为什么最好是个质数？
: 发信站: BBS 未名空间站 (Mon Feb 18 17:32:47 2013, 美东)
: 而且书上还说，如果来search字符串的话,最好这样计算hash function
: ( char[0] x s^n + char[1] x s^(n-1)+...+char[n] )% M
: 这里如果s和M不互质的话，就会导致得到的index分布不uniform
: 我没想明白为什么，我怎么觉得不管是否互质，只要输入分布uniform得到的index还是
: 在0到M-1之间uniform分布的啊
: 谁能给举个例子说明一下s和M不互质的情况下会出什么问题？
| c*********e
发帖数: 16335 | 3 index分布不uniform很正常，每个key对应的是一個linkedlist.
【在 s****A 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: studyA (Algorithm), 信区: JobHunting
: 标 题: hash table的size为什么最好是个质数？
: 发信站: BBS 未名空间站 (Mon Feb 18 17:32:47 2013, 美东)
: 而且书上还说，如果来search字符串的话,最好这样计算hash function
: ( char[0] x s^n + char[1] x s^(n-1)+...+char[n] )% M
: 这里如果s和M不互质的话，就会导致得到的index分布不uniform
: 我没想明白为什么，我怎么觉得不管是否互质，只要输入分布uniform得到的index还是
: 在0到M-1之间uniform分布的啊
: 谁能给举个例子说明一下s和M不互质的情况下会出什么问题？
|
|
