Java中String的hash函數分析

jdk6的源碼：

以字元串"123"為例：

字元'1'的ascii碼是49

hashcode = （49*31 + 50）*31 + 51

或者這樣看：

hashcode=（'1' * 31 + '2' ） * 31 + '3'

可見實際可以看作是一種權重的算法，在前面的字元的權重大。

這樣有個明顯的好處，就是字首相同的字元串的hash值都落在鄰近的區間。

好處有兩點：

1.可以節省記憶體，因為hash值在相鄰，這樣hash的數組可以比較小。比如當用hashmap，以string為key時。

2.hash值相鄰，如果存放在容器，比好hashset，hashmap中時，實際存放的記憶體的位置也相鄰，則存取的效率也高。（程式局部性原理）

以31為倍數，原因了31的二進制全是1，則可以有效地離散資料。

最後看下，兩個字元串，由eclipse生成的代碼是如何計算hash值的：

可見，還是以31為倍數， hashcode = firstname.hashcode() * 31 + lastname.hashcode() 。

btw：java的字元串的hash做了緩存，第一次才會真正算，以後都是取緩存值。

eclipse生成的equals函數品質也很高，各種情況都考慮到了。

總結：字元串hash函數，不僅要減少沖突，而且要注意相同字首的字元串生成的hash值要相鄰。