极客观点
项目管理
HarmonyOS
在我上一个帖子中沙渺的回答让我觉得有点道理,又觉得毫无道理,直到我看到了这样的帖子:
Hash Table（哈希表）就是根据对象的特征进行定位的一种数据结构。一个简单的实现方法是将对象通过某种运算得到一个整数，再让这个整数除以哈希表的大小，取其余数，以此作为对象的存储位置。
很多的书上认为，哈希表的大小最好是选择一个大的质数，并且最好不要和2的整数幂接近。《算法导论》上还认为，最不好的选择是哈希表的大小恰好是2的整数幂，对此的解释是（只记得大意）：因为计算机是用二进制存储的，当一个二进制数除以一个2的整数幂的时候，结果就是这个二进制数的后几位，前面的位都丢失了，也就意味着丢失了一部分信息，进而导致哈希表中的元素分布不均匀。
这个解释看似合理，但我不认同。不光是我，Java开发小组的人也不认同。Java里的HashSet类偏偏就把哈希表的大小设置成2的整数幂。可以设想一下，对于自然数集合中的任意一个数x，对于一个正整数M，难道x mod M为某些值的概率会大些吗？显然不是，因为x是在自然数集合里任选的，当选取的次数非常多时，x mod M的结果应该是平均分布在[0,M-1]中。我认为《算法导论》的错误在于先引入了二进制，其实二进制和哈希表的“碰撞”根本没有什么关系；然后说对除以2^n的余数会丢失位，丢失信息，这显然也不对，因为只要x>=M，x mod M的结果总是要“丢失一些信息的”。照《算法导论》的说法，如果计算机采用十进制，那哈希表的容量是10^n的话岂不是很糟？这种解释显然站不住脚。
我认为对于x mod M这样的哈希函数来说，好坏应该取决于x的生成方式和M的值。比如一个字符串“ABC”，如果我让x("ABC")=65128^2+66128+67，即把字符串当成一个128进制的整数，那么若M=128，那就很糟糕了。因为这样无论是什么字符串，最终结果只取决于最后一个字符，这才会造成分布不均匀。
我上一个问题中弄错的一个地方是讨论了哈希结果暴露原值，而不是避免冲撞这个角度。
恰好等于或接近2^i的风险我认为都只是暴露原值。能轻易操纵哈希目标值的特征，在安全性上是一个巨大的风险——这样就留下了用户使用特意构造的输入，去试图占用其他哈希值桶的攻击方法。
而质数才是用来避免冲撞。如果种子用合数，那么很可能对合数的某个因数取余，所得到的余数仍然是一样的。这样就增加了同一个桶中元素的共同特征，危害了平摊的效果。
举个例子：对4取余如果余1，那么对2取余仍然余1，那么1号桶就必然全部是奇数。同理0号桶必然是偶数。
从这一点来看，质数与接近2^i与否其实完全是两个无关的问题。
我必须说明的是：引文第3段的说法是一个极其想当然的糟糕解释。
理由很简单：Java开发小组会蠢到用简单取余算法去做HashSet么？原文作者分明就是把别人的完整实现蓄意偷来一部分，用来给自己偏执的观点贴金。
最后仍然必须再次声明的是：单纯取余的哈希运算很糟糕。“远离2^i的质数”、“接近2^i的质数”、“恰好等于2^i”都只不过是“没有那么差”、“确实很差”和“差到不能再差”的区别。
要么为冲撞做好准备，给每一个桶都构造一个链表，要么就任何时候都使用SHA-1等成熟且冲撞概率稳定而足够低的Hash算法。