飞道的博客

为什么 String 的 hashCode() 方法使用 31 来计算?

392人阅读  评论(0)

  
  1. /**
  2. * Returns a hash code for this string. The hash code for a
  3. * {@code String} 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} arithmetic, where {@code s[i]} is the
  8. * <i>i</i>th character of the string, {@code n} is the length of
  9. * the string, and {@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 && value.length > 0) {
  17. char val[] = value;
  18. for ( int i = 0; i < value.length; i++) {
  19. h = 31 * h + val[i];
  20. }
  21. hash = h;
  22. }
  23. return h;
  24. }

According to Joshua Bloch's Effective Java (a book that can't be recommended enough, and which I bought thanks to continual mentions on stackoverflow):

The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: 31 * i == (i << 5) - i. Modern VMs do this sort of optimization automatically.

(from Chapter 3, Item 9: Always override hashcode when you override equals, page 48)

参考资料

https://stackoverflow.com/questions/299304/why-does-javas-hashcode-in-string-use-31-as-a-multiplier%EF%BC%89


Kotlin 开发者社区

国内第一Kotlin 开发者社区公众号,主要分享、交流 Kotlin 编程语言、Spring Boot、Android、React.js/Node.js、函数式编程、编程思想等相关主题。

越是喧嚣的世界,越需要宁静的思考。


转载:https://blog.csdn.net/universsky2015/article/details/105090337
查看评论
* 以上用户言论只代表其个人观点,不代表本网站的观点或立场