首页 > 代码库 > HashCode计算

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计算