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

This article mainly explains "how to use hashCode () method in Java". Interested friends may wish to have a look at it. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "how to hashCode () method in Java"!

The hashCode () method is included in the Object class:

@ HotSpotIntrinsicCandidate public native int hashCode ()

This means that all classes will have a hashCode () method that returns a value of type int. Since the hashCode () method is a native method (a method modified by the native keyword, implemented in the Cmax Candle + language and called by Java), it means that there is no specific implementation in the Object class.

The specific implementation can be found in jdk/src/hotspot/share/runtime/synchronizer.cpp (the source code can be downloaded from the OpenJDK repository on GitHub). The get_next_hash () method determines which hash generation strategy is used based on the value of hashCode.

And the hashCode () method is modified by the @ HotSpotIntrinsicCandidate annotation, indicating that it has an efficient implementation in the HotSpot virtual machine, based on CPU instructions.

Have you ever thought about the question: why does the Object class need a hashCode () method?

In Java, the main purpose of the hashCode () method is to work with a hash table.

Hash table (Hash Table), also known as hash table, is a data structure that can be accessed directly through key code values (key-value). Its biggest feature is that it can quickly find, insert and delete. The algorithm used is called hashing, which converts an input of any length into a fixed-length output, which is the hash value. For example, MD5 and SHA1 all use hashing algorithm.

Things like HashSet, Hashtable (lowercase t) and HashMap in Java are all based on the concrete implementation of the hash table. Among them, HashMap is the most typical representative, not only the interviewer often asks, but also the frequency of use in the job is very high.

Think about it, if there is no hash table, but you need such a data structure, the data stored in it is not allowed to be repeated, what should we do?

Why don't you use the equals () method to compare one by one? Such a scheme is of course feasible. But if the amount of data is particularly large, the efficiency of using the equals () method to compare one by one must be very low, and the best solution is a hash table.

Take HashMap, for example. When we want to add an object to it, we first call the object's hashCode () method to get the corresponding hash value, and then put the hash value in the HashMap together with the object. When we want to add a new object:

Get the hash value of the object

Compare with the previously existing hash value, and if it is not equal, store it directly.

If there is an equality, then call the equals () method to compare the objects. If it is equal, it is not saved.

If not, it means that the hash conflicts. Add a linked list to store new objects.

If the length of the linked list is greater than 8, convert it to a red-black tree.

In this way, the frequency of calling the equals () method is greatly reduced. In other words, as long as the hash algorithm is efficient enough to minimize the frequency of hash conflicts, the efficiency of the hash table is particularly high.

Let's take a look at HashMap's hashing algorithm:

Static final int hash (Object key) {int h; return (key = = null)? 0: (h = key.hashCode ()) ^ (h > 16);}

The object's hashCode () method is called first, then the value is shifted to the right, and then XOR is performed.

Generally speaking, String is used to hash as the key of HashMap, so let's take a look at String's hashCode () method again:

Public int hashCode () {int h = hash; if (h = = 0 & & value.length > 0) {hash = h = isLatin1 ()? StringLatin1.hashCode (value): StringUTF16.hashCode (value);} return h;} public static int hashCode (byte [] value) {int h = 0; int length = value.length > > 1; for (int I = 0; I

< length; i++) { h = 31 * h + getChar(value, i); } return h; } 可想而知，经过这么一系列复杂的运算，再加上 JDK 作者这种大师级别的设计，哈希冲突的概率我相信已经降到了最低。 当然了，从理论上来说，对于两个不同对象，它们通过 hashCode() 方法计算后的值可能相同。因此，不能使用 hashCode() 方法来判断两个对象是否相等，必须得通过 equals() 方法。 也就是说： 如果两个对象调用 equals() 方法得到的结果为 true，调用 hashCode() 方法得到的结果必定相等; 如果两个对象调用 hashCode() 方法得到的结果不相等，调用 equals() 方法得到的结果必定为 false; 反之： 如果两个对象调用 equals() 方法得到的结果为 false，调用 hashCode() 方法得到的结果不一定不相等; 如果两个对象调用 hashCode() 方法得到的结果相等，调用 equals() 方法得到的结果不一定为 true; 来看下面这段代码。 public class Test { public static void main(String[] args) { Student s1 = new Student(18, "张三"); Map scores = new HashMap(); scores.put(s1, 98); System.out.println(scores.get(new Student(18, "张三"))); } } class Student { private int age; private String name; public Student(int age, String name) { this.age = age; this.name = name; } @Override public boolean equals(Object o) { Student student = (Student) o; return age == student.age && Objects.equals(name, student.name); } } 我们重写了 Student 类的 equals() 方法，如果两个学生的年纪和姓名相同，我们就认为是同一个学生，虽然很离谱，但我们就是这么草率。 在 main() 方法中，18 岁的张三考试得了 98 分，很不错的成绩，我们把张三和成绩放到了 HashMap 中，然后准备输出张三的成绩： null 很不巧，结果为 null，而不是预期当中的 98。这是为什么呢? 原因就在于重写 equals() 方法的时候没有重写 hashCode() 方法。默认情况下，hashCode() 方法是一个本地方法，会返回对象的存储地址，显然 put() 中的 s1 和 get() 中的 new Student(18, "张三") 是两个对象，它们的存储地址肯定是不同的。 HashMap 的 get() 方法会调用 hash(key.hashCode()) 计算对象的哈希值，虽然两个不同的 hashCode() 结果经过 hash() 方法计算后有可能得到相同的结果，但这种概率微乎其微，所以就导致 scores.get(new Student(18, "张三")) 无法得到预期的值 18。 怎么解决这个问题呢?很简单，重写 hashCode() 方法。 @Override public int hashCode() { return Objects.hash(age, name); } Objects 类的 hash() 方法可以针对不同数量的参数生成新的 hashCode() 值。 public static int hashCode(Object a[]) { if (a == null) return 0; int result = 1; for (Object element : a) result = 31 * result + (element == null ? 0 : element.hashCode()); return result; } 代码似乎很简单，归纳出的数学公式如下所示(n 为字符串长度)。

Note: 31 is an odd prime number, not too small, the general prime number is very suitable for hashing, even number is equivalent to shift operation, easy to overflow, resulting in the loss of data information.

This means that if you have the same age and name, you will get the same hash. Scores.get (new Student (18, "Zhang San")) will return the expected value of 98.

There is a passage in the Bible "Java programming ideas" that describes the hashCode () method.

The most important factor in designing hashCode () is that whenever you call hashCode () on the same object, you should generate the same value. If you add an object to HashMap with the put () method and produce a hashCode () value when you take it out with the get () method, you will not be able to retrieve the object. So, if your hashCode () method depends on mutable data in the object, users should be careful, because when this data changes, hashCode () generates a different hash value, which is equivalent to a different key.

That is, if a field in the object is prone to change when overriding the hashCode () and equals () methods, it's best to discard those fields so as not to produce unexpected results.

good. With the above as the basis, let's look back at the C++ source code of the local method hashCode ().

Static inline intptr_t get_next_hash (Thread* current, oop obj) {intptr_t value = 0; if (hashCode = = 0) {/ / This form uses global Park-Miller RNG. / / On MP system we'll have lots of RW access to a global, so the / / mechanism induces lots of coherency traffic. Value = os::random ();} else if (hashCode = = 1) {/ / This variation has the property of being stable (idempotent) / / between STW operations. This can be useful in some of the 1-0 / / synchronization schemes. Intptr_t addr_bits = cast_from_oop (obj) > > 3; value = addr_bits ^ (addr_bits > > 5) ^ GVars.stw_random;} else if (hashCode = = 2) {value = 1; / / for sensitivity testing} else if (hashCode = = 3) {value = + GVars.hc_sequence;} else if (hashCode = = 4) {value = cast_from_oop (obj) } else {/ / Marsaglia's xor-shift scheme with thread-specific state / / This is probably the best overall implementation-we'll / / likely make this the default in future releases. Unsigned t = current- > _ hashStateX; t ^ = (t _ hashStateX = current- > _ hashStateY; current- > _ hashStateY = current- > _ hashStateZ; current- > _ hashStateZ = current- > _ hashStateW; unsigned v = current- > _ hashStateW; v = (v ^ (v > > 19)) ^ (t > > 8); current- > _ hashStateW = v; value = v;} value & = markWord::hash_mask; if (value = 0) value = 0xBAD Assert (value! = markWord::no_hash, "invariant"); return value;}

If there is no C++ foundation, we don't have to look at every line of code in detail, we just take a superficial look at the get_next_hash () method. The hashCode variable is a global parameter when JVM starts, which can be used to switch the generation strategy of hash values.

HashCode==0, which returns a random number by calling the random () method of the operating system OS.

HashCode = = 1, which is commonly used in synchronization scenarios in STW (stop-the-world) operations. Use the object address for calculation, and use random numbers (GVars.stw_random) that are not updated frequently to participate in it.

HashCode = = 2, using return 1, for testing in some cases.

HashCode = = 3, the hash value is calculated from 0, which is not thread safe, and multiple threads may get the same hash value.

HashCode = = 4, depending on the memory location where the object was created, output as is.

HashCode = = 5, default value, supports multithreading, and uses Marsaglia's xor-shift algorithm to generate pseudorandom numbers. The so-called xor-shift algorithm, simply put, appears to be a shift register, in which the bits moved in each time are different or generated by several bits in the register. The so-called pseudo-random number is not completely random, but it is difficult to generate true random number, so as long as it can pass a certain statistical test of random number, it can be used as true random number.

As for deeper mining, it involves mathematical knowledge and physical knowledge, so it will not be carried out. After all, food is the original sin.

At this point, I believe you have a deeper understanding of "how to use the hashCode () method in Java". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

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.