Java中String的hash函数分析

转载自：http://blog.****.net/hengyunabc/article/details/7198533

JDK6的源码：

[java] view
plaincopy

1. /**
2. * Returns a hash code for this string. The hash code for a
3. * <code>String</code> object is computed as
4. * <blockquote><pre>
5. * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
6. * </pre></blockquote>
7. * using <code>int</code> arithmetic, where <code>s[i]</code> is the
8. * <i>i</i>th character of the string, <code>n</code> is the length of
9. * the string, and <code>^</code> indicates exponentiation.
10. * (The hash value of the empty string is zero.)
11. *
12. * @return  a hash code value for this object.
13. */
14. public int hashCode() {
15. int h = hash;
16. if (h == 0) {
17. int off = offset;
18. char val[] = value;
19. int len = count;
20. for (int i = 0; i < len; i++) {
21. h = 31*h + val[off++];
22. }
23. hash = h;
24. }
25. return h;
26. }

以字符串"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值的：

[java] view
plaincopy

1. public class Name{
2. String firstName;
3. String lastName;
4. @Override
5. public int hashCode() {
6. final int prime = 31;
7. int result = 1;
8. result = prime * result
9. + ((firstName == null) ? 0 : firstName.hashCode());
10. result = prime * result
11. + ((lastName == null) ? 0 : lastName.hashCode());
12. return result;
13. }
14. @Override
15. public boolean equals(Object obj) {
16. if (this == obj)
17. return true;
18. if (obj == null)
19. return false;
20. if (getClass() != obj.getClass())
21. return false;
22. Name other = (Name) obj;
23. if (firstName == null) {
24. if (other.firstName != null)
25. return false;
26. } else if (!firstName.equals(other.firstName))
27. return false;
28. if (lastName == null) {
29. if (other.lastName != null)
30. return false;
31. } else if (!lastName.equals(other.lastName))
32. return false;
33. return true;
34. }
35. }

可见，还是以31为倍数， hashCode = firstName.hashCode() * 31 + lastName.hashCode() 。

BTW：Java的字符串的hash做了缓存，第一次才会真正算，以后都是取缓存值。

eclipse生成的equals函数质量也很高，各种情况都考虑到了。

总结：字符串hash函数，不仅要减少冲突，而且要注意相同前缀的字符串生成的hash值要相邻。