天天看點

Hash表與素數

最近看到mysql的hash表,發現一個特點。

當hash表滿的時候,hash表size總是擴充成一個素數。

上網查了一下資料,素數可以有效的減少hash沖突。

想了一下,這個确實是有道理的。

假設hash表大小為size,這是一個合數,即有size=a*n。當有hash值為hashcode,且hashcode = b*n.

則hashcode取模之後為

hashcode = hashcode%size = hashcode - (hashcode / size) * size = hashcode - (b/a) * size

因為a是固定的,那麼上面的hashcode的取值隻有b種可能,這樣顯然會增加沖突的機率。