当前位置：网站首页>Rewrite equals why rewrite hashcode

Rewrite equals why rewrite hashcode

2022-07-19 03:12:00 【51CTO】

rewrite equals Why rewrite hashcode？

Premise

Let's get to know object class

       
       public 
       
       class 
       
       Object {
       
       //  Compare memory addresses for equality 
       
       public 
       
       boolean 
       
       equals(
       
       Object 
       
       obj) {
       
       return (
       
       this 
       
       == 
       
       obj);
       
    }
       
       // Convert the internal address of the object into an integer , That is to say hash value 
       
       public 
       
       native 
       
       int 
       
       hashCode();
       
       //........ Omitted code .............
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.

example

Suppose in business , We think that the same name is the same person

       
       public 
       
       class 
       
       Student {
       
       private 
       
       String 
       
       name;
       
       private 
       
       Integer 
       
       age;
       
       // .... Omit getter and  setter Method ....
       
       @Override
       
       public 
       
       boolean 
       
       equals(
       
       Object 
       
       o) { 
       
       // We think that the same name is the same person 
       
       if (
       
       this 
       
       == 
       
       o) 
       
       return 
       
       true;
       
       if (
       
       o 
       
       == 
       
       null 
       
       || 
       
       getClass() 
       
       != 
       
       o.
       
       getClass()) 
       
       return 
       
       false;
       
       Student 
       
       student 
       
       = (
       
       Student) 
       
       o;
       
       return 
       
       Objects.
       
       equals(
       
       name, 
       
       student.
       
       name);
       
    }
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.

guess

If you do not override hashcode What's going to happen

       
       public 
       
       static 
       
       void 
       
       main(
       
       String[] 
       
       args) {
       
       Map
       
       <
       
       Object, 
       
       Object
       
       > 
       
       map 
       
       = 
       
       new 
       
       HashMap
       
       <>(
       
       4);
       
       Student 
       
       student1 
       
       = 
       
       new 
       
       Student(
       
       "zhangsan", 
       
       11);
       
       Student 
       
       student2 
       
       = 
       
       new 
       
       Student(
       
       "zhangsan", 
       
       22);
       
       map.
       
       put(
       
       student1,
       
       student1);
       
       map.
       
       put(
       
       student2,
       
       student2);
       
       System.
       
       out.
       
       println(
       
       map.
       
       size());
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.

Let's see below. map Of put What happened to the operation ？

       
       //hashmap Of hash Algorithm 
       
       static 
       
       final 
       
       int 
       
       hash(
       
       Object 
       
       key) {
       
       int 
       
       h;
       
       return (
       
       key 
       
       == 
       
       null) 
       
       ? 
       
       0 : (
       
       h 
       
       = 
       
       key.
       
       hashCode()) 
       
       ^ (
       
       h 
       
       >>> 
       
       16);
       
}
       
       public 
       
       V 
       
       put(
       
       K 
       
       key, 
       
       V 
       
       value) {
       
       return 
       
       putVal(
       
       hash(
       
       key), 
       
       key, 
       
       value, 
       
       false, 
       
       true);
       
}
       
       final 
       
       V 
       
       putVal(
       
       int 
       
       hash, 
       
       K 
       
       key, 
       
       V 
       
       value, 
       
       boolean 
       
       onlyIfAbsent,
       
       boolean 
       
       evict) {
       
       Node
       
       <
       
       K,
       
       V
       
       >[] 
       
       tab; 
       
       Node
       
       <
       
       K,
       
       V
       
       > 
       
       p; 
       
       int 
       
       n, 
       
       i;
       
       if ((
       
       tab 
       
       = 
       
       table) 
       
       == 
       
       null 
       
       || (
       
       n 
       
       = 
       
       tab.
       
       length) 
       
       == 
       
       0)
       
       n 
       
       = (
       
       tab 
       
       = 
       
       resize()).
       
       length;
       
       if ((
       
       p 
       
       = 
       
       tab[
       
       i 
       
       = (
       
       n 
       
       - 
       
       1) 
       
       & 
       
       hash]) 
       
       == 
       
       null)
       
       tab[
       
       i] 
       
       = 
       
       newNode(
       
       hash, 
       
       key, 
       
       value, 
       
       null);
       
       else {
       
       Node
       
       <
       
       K,
       
       V
       
       > 
       
       e; 
       
       K 
       
       k;
       
       //1、 Compare first key Of hash Whether the values are equal , Compare again key Whether the memory addresses of are equal   perhaps  key Of  equals  Whether it is equal or not 
       
       if (
       
       p.
       
       hash 
       
       == 
       
       hash 
       
       &&
       
            ((
       
       k 
       
       = 
       
       p.
       
       key) 
       
       == 
       
       key 
       
       || (
       
       key 
       
       != 
       
       null 
       
       && 
       
       key.
       
       equals(
       
       k))))
       
       e 
       
       = 
       
       p;
       
       //2、hash It's not equal , Compare it again TreeNode type 
       
       else 
       
       if (
       
       p 
       
       instanceof 
       
       TreeNode)
       
       e 
       
       = ((
       
       TreeNode
       
       <
       
       K,
       
       V
       
       >)
       
       p).
       
       putTreeVal(
       
       this, 
       
       tab, 
       
       hash, 
       
       key, 
       
       value);
       
       //3、 Whether there are equal nodes in the linked list 
       
       else {
       
       for (
       
       int 
       
       binCount 
       
       = 
       
       0; ; 
       
       ++
       
       binCount) {
       
       if ((
       
       e 
       
       = 
       
       p.
       
       next) 
       
       == 
       
       null) { 
       
       // The next node of the current linked list is empty 
       
       p.
       
       next 
       
       = 
       
       newNode(
       
       hash, 
       
       key, 
       
       value, 
       
       null);
       
       // Add a new node 
       
       if (
       
       binCount 
       
       >= 
       
       TREEIFY_THRESHOLD 
       
       - 
       
       1) 
       
       //  The length of the list is greater than or equal to  7 , The tree, , Exit loop 
       
       treeifyBin(
       
       tab, 
       
       hash);
       
       break;  
       
                }
       
       // Whether the next node is equal to the nodes to be added , It's the exit loop 
       
       if (
       
       e.
       
       hash 
       
       == 
       
       hash 
       
       &&
       
                    ((
       
       k 
       
       = 
       
       e.
       
       key) 
       
       == 
       
       key 
       
       || (
       
       key 
       
       != 
       
       null 
       
       && 
       
       key.
       
       equals(
       
       k))))
       
       break;
       
       // Continue to walk behind the linked list 
       
       p 
       
       = 
       
       e;
       
            }
       
        }
       
       // If the same node exists in the linked list , Return old value 
       
       if (
       
       e 
       
       != 
       
       null) { 
       
       // existing mapping for key
       
       V 
       
       oldValue 
       
       = 
       
       e.
       
       value;
       
       if (
       
       !
       
       onlyIfAbsent 
       
       || 
       
       oldValue 
       
       == 
       
       null)
       
       e.
       
       value 
       
       = 
       
       value;
       
       afterNodeAccess(
       
       e);
       
       return 
       
       oldValue;
       
        }
       
    }
       
       ++
       
       modCount;
       
       if (
       
       ++
       
       size 
       
       > 
       
       threshold)
       
       resize();
       
       afterNodeInsertion(
       
       evict);
       
       return 
       
       null;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.

We find that when there is conflict , The order of judgment is as follows

Compare first key Of hash Whether the values are equal , Compare again key Whether the memory addresses of are equal perhaps key Of equals Whether it is equal or not
hash It's not equal , Compare it again TreeNode type
Whether there are equal nodes in the linked list

Because we think that the same name is the same person
When put When , Compare first student1 and student2 Of hash value , because student1 and student2 It's a different object , their hashcode Method is called object.hashcode Method , It compares the address of the object , Obviously , It is calculated by the following method hash It's not equal

       
       //hashmap Of hash Algorithm 
       
       static 
       
       final 
       
       int 
       
       hash(
       
       Object 
       
       key) {
       
       int 
       
       h;
       
       return (
       
       key 
       
       == 
       
       null) 
       
       ? 
       
       0 : (
       
       h 
       
       = 
       
       key.
       
       hashCode()) 
       
       ^ (
       
       h 
       
       >>> 
       
       16);
       
}
      
1.
2.
3.
4.
5.

hash Value inequality , Neither TreeNode type , Add to linked list

There's a contradiction

But now the name is the same , But in map But there are two people , It's obviously against our original intention
Obviously , The reason for the contradiction is to call object.hashcode Method , Calculate the unequal hash value , If hash The values are equal , Can meet the following if sentence

       
       //1、 Compare first key Of hash Whether the values are equal , Compare again key Whether the memory addresses of are equal   perhaps  key Of  equals  Whether it is equal or not 
       
       if (
       
       p.
       
       hash 
       
       == 
       
       hash 
       
       && ((
       
       k 
       
       = 
       
       p.
       
       key) 
       
       == 
       
       key 
       
       || (
       
       key 
       
       != 
       
       null 
       
       && 
       
       key.
       
       equals(
       
       k))))
       
       e 
       
       = 
       
       p;
      
1.
2.
3.

So , I want to design something with the same name student Produce the same hash value

rewrite hashcode

We know that different values may produce the same hash value , But in map This problem does not exist , Because when hash When the values are equal , And compare it equals Method , But we should also try to avoid hash Collision , After all hash Collision still has a little impact on performance

       
       @Override
       
       public 
       
       int 
       
       hashCode() {
       
       return 
       
       Objects.
       
       hash(
       
       name);
       
}
      
1.
2.
3.
4.

Sum up , rewrite equals To rewrite hashcode Just to avoid being like map In such a data structure , Prohibit the same key There are multiple value value .
end ！！！

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/200/202207170032465426.html