HashCode计算
多项式
我们知道字典Dictionary对象是一个key到value的映射，如果key为数值型，则计算其hashcode（假设为32位）时，我们可以通过对其的位表示（bit representation）进行某种计算，
比如不超过32位的数值，其hashcode为其本身（左边填充0即可），超过32位的数值，则每32位分成一个部分，表示一个整型Xi，则可以通过计算所有Xi的和或者依次异或计算，从而得到hashcode
然而对于字符串类型或者某序列而言，以上hashcode的计算方法则不可取，因为对这个序列进行置换操作，并不改变hashcode，如"stop", "tops", "pots", "spot"的hashcode将一样，那如何计算hashcode？
（以上对于数值型的hashcode计算方法，理论上也存在这个问题，只不过32位能表示的范围在实际应用中还是蛮大的，故而实际中碰撞概率很低，而上面举得字符串的例子，则碰撞概率相对高很多）
由于这里每一项的位置很重要，故而需要用位置影响最终的hashcode值，一种方式是使用多项式计算：
加入序列中有n项，x0... xn-1, 选择常数a（不等于1），
x0a^n-1 + x1a^n-2 + ... + xn-2a + xn-1
这里，可以忽略32位相加溢出的情况，并且a的取值不宜过大。根据测试，a取33，37，39或者41比较好，对于字符串为英文单词时，对超过50000的单词测试，每种情况碰撞不超过7。
循环移位
前面讲到对于序列计算hashcode时，需要引入位置信息，使得位置能影响到最终的hashcode值。那除了计算多项式，还有一种方法循环移位也可以做到。
考虑，依次相加序列中每一项，则项的顺序并不会影响到最终相加的和，but，如果每次加一个项后就做一次循环移位，显然，最终的和是受到影响的，代码如下，
python：
def hash_code(s): mask = (1 << 32) -1 sum = 0 for c in s: sum = (sum << 5 & mask) | (sum >> 27) sum += ord(c) return sum
这里，将sum的最左边5位移到最右边。
压缩函数
上面计算得到的hashcode是32位的，其范围远大于字典的容量N，那要将key-value pair 放入字典，势必需要压缩hashcode，再次映射使得范围为[0, N-1]
取模
一个很容易想到的方法是取模，
i mod N
其中N一般都是使用素数，但是如果计算的hashcode很容易重复出现 pN+q的形式（p不同，q相同），那么，N使用素数依然无法避免很容易发生碰撞。
MAD
上面的取模方法可能会出现重复pN+q形式，所以需要更加复杂的方法来避免。
那么如何避免这种重复pN+q的形式呢？
由于这里p不同，而q相同，导致 i mod N 结果相同，那么容易想到，如果对 i 做变换，也许就可以实现了。
已知：i = Np + q （Eq 1）
可以看成 i 是 p的函数，其中N和q在某情况下为定值（这里假设有很多hashcode是这种形式，并且只考虑这些hashcode，不考虑其他hashcode，我们要做的就是对这些hashcode做某种变换，打破这种形式）
显然对 （Eq 1）做线性变化是没用的，这只会使得 i' = Np' + q'，如果做平方运算，则 i' = i^2 = (Np)^2 + 2Npq + q^2，可以知道，做平方、三次方都是没用的。
既然（Eq 1）里面 q是定值，而p不是定值，那么只要让做一个变换，让p（或者Np）能影响q即可，这里给出Multipy-Add-and-Divide(MAD)方法如下，
[(ai + b) mod c] mod N
其中，c是比N大的素数，a和b范围在[0, c - 1]，且 a > 0。