在 SegmentFault，解决技术问题
每个月，我们帮助 1000 万的开发者解决各种各样的技术问题。并助力他们在技术能力、职业生涯、影响力上获得提升。
一线的工程师、著名开源项目的作者们，都在这里：
获取验证码
已有账号？
问题对人有帮助，内容完整，我也想知道答案
问题没有实际价值，缺少关键内容，没有改进余地
直接取余法：f(x):= x mod maxM ; maxM一般是不太接近 2^t 的一个质数。
听说是为了尽量避免冲突,我搞不懂怎么就能避免了?
这个问题已被关闭，原因：
答案对人有帮助，有参考价值
答案没帮助，是错误的答案，答非所问
我觉得这个是从二进制的角度考虑的。接近2^i的种子，二进制表达时中间必然产生大段的0或1。
那么以11这个种子为例，把它翻n倍：
可以看到，如果种子过于接近2^i，那么无论如何翻倍，种子中间仍然会有大段的0或1。
取余运算的本质无非是个减去种子n倍的减法。那么做减法的时候，种子中间大段的0或1就会让哈希原值的中间一段，有非常大的可能性仍然保持原样。
哈希函数的本质目的就是混淆，原值的变化产生哈希值无规律、等概率、不可预测、不能逆推的变化为最佳。
如果做完哈希运算之后，哈希值和原值中间居然有一大段二进制位保持不变，那么这个哈希函数就可以说是失败到不能再失败了。
当然必须说明的是：简单取余这个哈希函数本来就是非常失败的。简单分析即可，不必深究，也不要在任何真正的产品代码中实用。
答案对人有帮助，有参考价值
答案没帮助，是错误的答案，答非所问
哈希函数的重要特性沙渺的答案也指出了，就是要尽量让输出等概率，从而降低碰撞的频率。不过剩下的条件我觉的不一定适用。从mod可以猜到，这里的哈希是给哈希表算数据该放到哪个bucket里的，而不是用来进行签名/密码保护的(md5, sha-1...)。所以不可预测，不可逆推等不是必要条件。
对一个用于加密的哈希函数来说，原值部分保持不变是非常失败的。不过对一个用在哈希表上的哈希函数，就不能用容易逆推什么的证明它失败了。理论上，若x的分布是平均的，那么maxM取值多少效果都一样好。假设x平均分布在[0, k * maxM]，那么f(x)就会平均分布于[0, maxM]。从排除哈希碰撞的角度看，这已经是最优的分布了。
但是理论归理论，实际上maxM最好还得是个质数，因为x的分布在实际应用中很难做到平均分布，这时候maxM的取值就至关重要。首先不难看出maxM不能取2^t这种数，因为这样等同于把输入数据的高位截断了。如果恰好输入数据变化的只有高位。。。那就会悲剧。。。所有的数据都会被分配到一个桶。比如maxM=256，257%256=1，513%256=1，769%256=1……
再把之前的思路扩展一下，一个哈希函数若能保证在输入数据跟任何整数同余（不光只有2的幂）的情况下，都能避免大量碰撞，那就更好了。在Java的HashMap实现中()，第368行就解释了通过高低位不断异或的方式打乱同余的规律，从而达到了抑制碰撞的效果。
但要是只能用题目中f(x) = x mod m这种形式呢？假设输入形式是a+k, 2a+k, 3a+k等等：
让X={ja+k | k,j为正整数}, x∈X
让b=gcd(a, m), c=a/b, d=m/b
(ja+k) mod m
=(ja mod m + k mod m) mod m
=[b(jc mod d + k mod m)] mod m
=b[(jc mod d + k mod m) mod d]
因为c和d互质，所以jc mod d的可能取值是d个。
而k mod m又是常数，所以整个等式的可能取值正好是d个。d=m/gcd(a, m)
由此看出f(x)只可能取maxM/gcd(maxM, a)这么多个值。a若跟maxM互质，取值范围就会最大化，哈希函数会达到不错的散布效果。
所以maxM是质数的话，a取多少都能保证良好散布啦。
以上简要写了下我对maxM为啥不能是2^t，而且一般是质数的理解，至于为啥不能接近2^t，我还是没法回答。初次在segmentfault上发言，有错误和不妥之处还请各位大牛多多指正。
这个问题已经被关闭无法回答
分享到微博？
关闭理由：
删除理由：
忽略理由：
推广（招聘、广告、SEO 等）方面的内容
与已有问题重复（请编辑该提问指向已有相同问题）
答非所问，不符合答题要求
宜作评论而非答案
带有人身攻击、辱骂、仇恨等违反条款的内容
无法获得确切结果的问题
非开发直接相关的问题
非技术提问的讨论型问题
其他原因（请补充说明）
我要该，理由是：2的15次减1是否是质数
有没有算2的n次方加x是否为质数的方法。能否扩展到a的n次方加x是否为质数？算质数的简便方法是什么？
08-10-16 &匿名提问
如果一个数（&2），对这个数求平方根，如果这个数能被这个数的平方根到2之间的任何一个（只要有一个就行）整除说明就不是质数，如果不能就说明是质数！ 或者： '1.是两个大于 1 的整数之乘积;' '2.拥有某大于 1 而小于自身的因数（因子）;' '3.拥有至少三个因数（因子）;' '4.不是 1 也不是素数(质数);' '5.有至少一个素因子的非素数。 Private Sub Command1_Click() Dim n%, i%, j% n = Val(InputBox(&请输入一个正整数!&)) For i = 2 To Sqr(n) If n Mod i = 0 Then j = j + 1 If j &= 3 Then MsgBox &N是个合数!!& Exit Sub End If End If Next MsgBox &N是个质数!!& End Sub
请登录后再发表评论!
2^15-1 =(2^5)^3-1^3 =(2^5-1)*[(2^5)^2+(2^5)*1+1] =31*(32^2+33)
请登录后再发表评论!
2^15-1 =(2^5)^3-1^3 =(2^5-1)*[(2^5)^2+(2^5)*1+1] =31*(32^2+33)
支持这种方法.由此推广,因为1的无论多少次方仍为1,故只要n能被2或3整除,2的n次方就一定不是质数.
请登录后再发表评论!
2^15-1 =(2^5)^3-1^3 =(2^5-1)*[(2^5)^2+(2^5)*1+1] =31*(32^2+33)
支持这种方法.由此推广,因为1的无论多少次方仍为1,故只要n能被2或3整除,2的n次方就一定不是质数.
请登录后再发表评论!
2^15-1 =(2^5)^3-1^3 =(2^5-1)*[(2^5)^2+(2^5)*1+1] =31*(32^2+33)
支持这种方法.由此推广,因为1的无论多少次方仍为1,故只要n能被2或3整除,2的n次方就一定不是质数.
呵呵,不好意思,打错了,是2的n次方减1就一定不是质数.
请登录后再发表评论!
2^2-1=3 2^3-1=7
请登录后再发表评论!}