Hashcode details

Preface

I wrote this article because I encountered some hashcode values when reading the HashMap source code, and then I checked them. There is an image in my head. There are equal and hashcode methods in the object. I encountered them when learning the basics of Java, but it doesn't matter at that time. If I don't understand it, I don't understand it. I just took it with me, and now, I went back to make up the problem that should have been made clear before, so I know a truth. Learning is not a matter of pursuing speed. If you don't understand it, you have to find out and understand it step by step. Although it may be very slow at the beginning, it will be faster and faster if you learn more and understand more slowly. It's getting easier and easier. It's not like we're still making up the original knowledge. There's nothing to regret. At least now I know this truth. It's never too late to learn. As long as I suddenly wake up one day, everything will slowly get better. 　　

After understanding this knowledge, I checked many blogs and found many similarities. I don't know which is the original work, so I think it's better to copy one, but I'm confused after reading it. I'll write it down.

　　　　　　　　　　　　 http://blog.csdn.net/zhangyuan19880606/article/details/51240372

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　---WZY

1、 What is hashcode@ H_ 403_ 14@

1. What are hash and hash tables@ H_ 403_ 14@　　　

If you want to know this hashcode, you must first know the hash and take a look at it through Baidu Encyclopedia

Hash is a function. The implementation of this function is an algorithm, which obtains a hash value through a series of algorithms. At this time, we need to know another thing, the hash table. The hash value obtained through the hash algorithm is in this hash table, that is, the hash table is composed of all hash values. There are many kinds of hash functions, This means that there are many algorithms to obtain hash values, such as the three in the screenshot above. We will take the first one later.

　　　2、 hashcode@H_403_14 @　

With the previous foundation, the explanation here is simple. Hashcode is obtained through the hash function. Generally speaking, it is obtained through an algorithm. Hashcode has a corresponding position in the hash table.

Every object has a hashcode. How do you get the hashcode of the object?

First of all, an object must have a physical address. In other blog posts, hashcode will be said to represent the address of the object. Here, readers will certainly form a misunderstanding. The physical address of the object is different from this hashcode address. Hashcode represents the address of the object, which refers to the location of the object in the hash table, and the physical address refers to the address of the object stored in memory, So how do objects get hashcode? The internal address (that is, the physical address) of the object is converted into an integer, and then the integer is hashcode through the algorithm of hash function. Therefore, what is hashcode? Is the corresponding position in the hash table. If it is not clear here, for example, in the hash table, hashcode is 1, hashcode is 2, (...) 3. 4, 5, 6, 7 and 8, there is an object a, and the physical address of a is converted to an integer 17 (this is if). Through the direct remainder algorithm, 17% 8 = 1, then the hashcode of a is 1, and a is at the position of 1 in the hash table. There must be other questions. Then look at the following. Here is just an example to let you know what hashcode means.

2、 What does hashcode do@ H_ 403_ 14@

We have talked so much about the hash function and how the hashcode is obtained, and the hashcode corresponds to the position in the hash table. You may have questions. Why doesn't the hashcode write the physical address directly and use another hash table to represent the address of the object? Next, I'll tell you the role of hashcode,

1. Hashcode exists mainly for the convenience of searching. Hashcode is used to determine the storage address of the object in the hash storage structure (hashcode is used to represent the position of the object in the hash table in the latter sentence) @ h_ 403_ 14@@H_ 403_ 14@

Why does hashcode search faster? For example, we have a memory that can store 1000 numbers, in which we need to store 1000 different numbers. The stupidest way is to save a number and traverse it to see if there are the same numbers. When we save 900 numbers and start saving 901 numbers, You need to compare with 900 numbers, which is very troublesome and time-consuming. Use hashcode to record the location of the object. Take a look. There are 1, 2, 3, 4, 5, 6, 7 and 8 positions in the hash table. The first number is saved. The hashcode is 1. The number is placed in the position of 1 in the hash table. When 100 numbers are saved, there will be many numbers in the 8 positions in the hash table. There may be 20 numbers in 1. When saving 101 numbers, he first checks the position corresponding to the hashcode value. If it is 1, 20 numbers are the same as his hashcode, It only needs to compare with these 20 numbers (equals). If each number is the same, it will be placed in the position of 1. In this way, the number of comparisons will be much less. In fact, there are many positions in the hash table. Here is only an example, there are only 8, so the number of comparisons will make you feel a lot. In fact, if the hash table is large, the number of comparisons will be very few. By comparing the original method with the hashcode method, we know the function of hashcode and why hashcode is used @ H_ 403_ 14@@H_ 403_ 14@

3、 The relationship between the equals method and hashcode@ H_ 403_ 14@@H_ 403_ 14@

From the previous example, we can probably know that we first compare through hashcodes. If hashcodes are equal, we use the equals method to compare whether the two objects are equal. For example, the eight positions in the hash table mentioned above are like eight buckets. Each bucket can hold a lot of objects. Object a is obtained through the hash function algorithm and put it into bucket 1, Of course, there must be other objects in bucket 1. If object B is also assigned to bucket 1 through the algorithm, how can it identify whether other objects in the bucket are the same as it? At this time, the equals method is needed to filter@ H_ 403_ 14@@H_ 403_ 14@@H_ 403_ 14@@H_ 403_ 14@

1. If the equals of two objects are equal, the hashcodes of the two objects must be the same @ H_ 403_ 14@@H_ 403_ 14@@H_ 403_ 14@@H_ 403_ 14@@H_ 403_ 14@@H_ 403_ 14@

2. If the hashcodes of two objects are the same, it does not mean that the two objects are the same. It only means that the two objects are stored in the same location @ h in the hash storage structure_ 403_ 14@@H_ 403_ 14@

You can understand these two@ H_ 403_ 14@@H_ 403_ 14@

4、 Why is it recommended to rewrite the hashcode method if the equals method is rewritten@ H_ 403_ 14@@H_ 403_ 14@@H_ 403_ 14@

(if the equals method of the object is overridden, the hashcode method of the object should also be overridden as much as possible) @ h_403_14 @ @ h_403_14 @ @ h_403_14@

For example, I understand this truth, @ H_ 403_ 14@@H_ 403_ 14@

For example, a class a rewrites the equals method but does not rewrite the hashcode method. According to the output results, the equals methods used by object A1 and object A2 are equal. According to the usage of hashcode above, their hashcodes must be equal. However, since the hashcode method is not rewritten here, their two hashcodes are different, so, After rewriting the equals method, we also rewritten the hashcode method as much as possible. Through certain algorithms, they will have the same hashcode value when equals is equal@ H_ 403_ 14@@H_ 403_ 14@

Example: now let's take a look at the equals method and hashcode method in the source code of string. This class overrides these two methods. Why do you need to override these two methods now@ H_ 403_ 14@@H_ 403_ 14@

Equals method: in fact, the principle is the same as the example I wrote above, so we know the equals method of string through the source code to verify whether the values of two strings are the same. The double class also overrides these methods. Many classes compare these two methods, because they are in the parent class object of all classes. The function of equals is the function of "= =". You can also compare the difference between equals and = = of a string object. It will not be explained here@ H_ 403_ 14@@H_ 403_ 14@

Hashcode method @ h_ 403_ 14@@H_ 403_ 14@