Shulou(Shulou.com)06/03 Report--

This article mainly explains the reason why the String hashCode method chooses the number 31 as the multiplier. Interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Now let the editor take you to learn "what is the reason why the String hashCode method chooses the number 31 as the multiplier"?

1. Background

One day, when I was writing code, I accidentally clicked on the String hashCode method. Then I took a quick look at the implementation of hashCode and found that it was not very complicated. But I found a strange number in the source code, which is 31, the protagonist of this article. This number is not declared as a constant, so it is impossible to infer the purpose of the number literally. Later, with doubt and curiosity, I went to the Internet to look for information. After reading the material, I sighed silently that this was the case. So what is it? In the next chapter, please solve the mystery of the use of the number 31 with curiosity.

two。 The reason for choosing the number 31

Before explaining in detail why the String hashCode method chooses the number 31 as the multiplier, let's take a look at how the String hashCode method is implemented, as follows:

Public int hashCode () {int h = hash; if (h = = 0 & & value.length > 0) {char val [] = value; for (int I = 0; I

< value.length; i++) { h = 31 * h + val[i]; } hhash = h; } return h; } 上面的代码就是 String hashCode 方法的实现，是不是很简单。实际上 hashCode 方法核心的计算逻辑只有三行，也就是代码中的 for 循环。我们可以由上面的 for 循环推导出一个计算公式，hashCode 方法注释中已经给出。如下： s[0]31^(n-1) + s[1]31^(n-2) + … + s[n-1] 这里说明一下，上面的 s 数组即源码中的 val 数组，是 String 内部维护的一个 char 类型数组。这里我来简单推导一下这个公式： 假设 n=3 i=0 ->

H = 31 * (31 * 0 + val [0]) + val [1] iF2-> h = 31 * (31 * (31-1 + val [0]) + val [1]) + val [2] h = 31-31-1 + 31*31*val [0] + 31*val [1] + val [2] h = 31 ^ (NLV 1) * val [0] + 31 ^ (n Mel 2) * val [1] + val [2]

The above formula including the derivation of the formula is not the focus of this article, we can understand it. Next, let's talk about the focus of this article, that is, the reasons for choosing 31. According to the information on the Internet, there are generally two reasons:

First, 31 is a medium prime number, which is one of the preferred prime numbers as hashCode multipliers. Other similar prime numbers, such as 37, 41, 43, etc., are also good choices. So why did you choose 31? Please look at the second reason.

Second, 31 can be optimized by JVM, 31 * I = (I)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.