Hashcode details

Today, when reviewing the hash table of data structure, I saw HashCode The concept , Then I don't understand it so much , Just record it ！

Then I refer to the explanation of the boss , With some understanding , The original link is as follows ：

hashcode Detailed explanation - Lao Wang with dreams - Blog Garden (cnblogs.com)

1. What is? HashCode as well as hashcode How did you get it ？

1.1 What is? hash?

1.2  What is? hashcode?

hashcode It is obtained in a certain way hash The corresponding position in the table .

1.3 hashcode How did you get it ？

First of all, an object must have a physical address , In other blog posts hashcode Said to represent the address of the object , This will certainly make readers form misunderstandings , The physical address of the object is the same as this hashcode Different addresses ,hashcode The address representing the object means that the object is in hash The position in the table , The physical address is the address where the object is stored in memory , So how do objects get hashcode Well ？ Through the internal address of the object ( That's the physical address ) Convert to an integer , Then the integer passes through hash The algorithm of the function gets hashcode, therefore ,hashcode What is it? ？ Is in the hash The corresponding position in the table . If it's not clear here , for instance ,hash Table has hashcode by 1、hashcode by 2、(...)3、4、5、6、7、8 These eight positions , There is an object A,A Convert the physical address of to an integer 17( This is if ), Through the direct remainder algorithm ,17%8=1, that A Of hashcode for 1, And A It's just hash In the table 1 The location of . There must be other questions , Then look at the following , Here is just an example to let you know what is hashcode The meaning of .

2. hashcode What's the role ？

HashCode The main purpose of the existence of is to find the shortcut ,HashCode It is used to determine the storage address of the object in the hash storage structure

  Why? hashcode Just find it faster , such as ： We have one that can store 1000 In such a large number of memory , In which to store 1000 A different number , In the dumbest way , Just save a number , Just go through it , See if there is the same number , When saved 900 A digital , Start saving 901 A number , Just follow 900 Compare two numbers , It's a lot of trouble , It's time consuming , use hashcode To record the location of the object , Take a look at .hash Table has 1、2、3、4、5、6、7、8 A place , Save the first number ,hashcode by 1, The number is placed in hash In the table 1 The location of , Deposit in 100 A digital ,hash In the table 8 There will be many numbers in one position ,1 There may be 20 A digital , save 101 When a digital , He checked first hashcode The position corresponding to the value , Assuming that 1, Then there is 20 A number and his hashcode identical , He just needs to talk to this 20 Compare two numbers (equals), If each one is the same , Then put it in 1 This position , In this way, the number of comparisons is much less , actually hash There are many places in the table , Here is just an example 8 individual , So the number of comparisons will make you feel a lot , actually , If hash The watch is big , Then the number of comparisons is very few .  Through the original method and use hashcode Method comparison , We'll see hashcode The role of , And why use hashcode 了

3. equals and hashcode The relationship between

Through the previous example , You can probably know , Through the first hashcode To compare , If hashcode equal , Then use equals Method to compare the equality of two objects , Use an example to illustrate ： Above said hash In the table 8 A place , like 8 A barrel , Each bucket can hold a lot of objects , object A adopt hash The function algorithm gets it and puts it in 1 In No.1 barrel , Of course, there must be other objects that will be put in 1 In No.1 barrel , If the object B It is also divided into 1 Bucket number , So how does it identify whether other objects in the bucket are the same as it , It's time to equals Method to screen .

① If two objects equals equal , So the two objects HashCode It must be the same

② If I have two objects HashCode identical , Doesn't mean two objects are the same , It can only indicate that these two objects are in the hash storage structure , Store in the same location

4. Why rewrite equals It needs to be rewritten hashcode?

such as ： There is one A Class overridden equals Method , But no rewriting hashCode Method , Look at the output , object a1 And the object a2 Use equals The method is equal , According to the above hashcode Usage of , So the two of them hashcode Definitely equal , But because there's no rewriting here hashcode Method , Two of them hashcode Not the same. , therefore , We're rewriting equals After the method , Try to rewrite it as well hashcode Method , Through a certain algorithm , Make them in equals When equal , There will be the same hashcode value .

Last , Let's take a look String At the bottom hashcode Source code