hashMap工作原理和hash碰撞

╰+攻爆jí腚メ 2022-06-10 11:38 170阅读 0赞

这一章节我们来讨论一下hash碰撞。

1.什么是hash碰撞？

就是两个对象的key的hashcode是一样的，这个时候怎么get他的value呢？

答案是通过equals遍历table那个位置上面的Entry链表。

2.例子

正常的例子：

**\[java\]**  [view plain][]   [copy][view plain]

1.  **package** com.ray.ch14;  
2.    
3.  **import** java.util.HashMap;  
4.    
5.  **public** **class** Test \{  
6.      **public** **static** **void** main(String\[\] args) \{  
7.          HashMap<Person, Dog> map = **new** HashMap<Person, Dog>();  
8.          Person person\_1 = **new** Person();  
9.          person\_1.setHeight(180);  
10.         person\_1.setId(1);  
11.         person\_1.setName("person\_1");  
12.         Person person\_2 = **new** Person();  
13.         person\_2.setHeight(180);  
14.         person\_2.setId(2);  
15.         person\_2.setName("person\_1");  
16.         Dog dog\_1 = **new** Dog();  
17.         dog\_1.setId(1);  
18.         dog\_1.setName("dog\_1");  
19.         Dog dog\_2 = **new** Dog();  
20.         dog\_2.setId(2);  
21.         dog\_2.setName("dog\_2");  
22.         map.put(person\_1, dog\_1);  
23.         map.put(person\_2, dog\_2);  
24.         System.out.println("--" + map.get(person\_1).getName());  
25.         System.out.println("--" + map.get(person\_2).getName());  
26.     \}  
27. \}  
28.   
29. **class** Dog \{  
30.     **private** **int** id = 0;  
31.     **private** String name = "";  
32.   
33.     **public** **int** getId() \{  
34.         **return** id;  
35.     \}  
36.   
37.     **public** **void** setId(**int** id) \{  
38.         **this**.id = id;  
39.     \}  
40.   
41.     **public** String getName() \{  
42.         **return** name;  
43.     \}  
44.   
45.     **public** **void** setName(String name) \{  
46.         **this**.name = name;  
47.     \}  
48.   
49.     @Override  
50.     **public** **int** hashCode() \{  
51.         System.out.println("dog's hashCode() invoked");  
52.         **return** id;  
53.     \}  
54.   
55.     @Override  
56.     **public** **boolean** equals(Object obj) \{  
57.         System.out.println("dog's equals invokes");  
58.         **return** **super**.equals(obj);  
59.     \}  
60. \}  
61.   
62. **class** Person \{  
63.     **private** **int** id = 0;  
64.     **private** String name = "";  
65.     **private** **int** height = 0;  
66.   
67.     @Override  
68.     **public** **int** hashCode() \{  
69.         System.out.println("person id:" + id + ",hashCode() invoked,"  
70.                 + "hashcode:" + **this**.name.hashCode() + **this**.height);  
71.         **return** **super**.hashCode();  
72.     \}  
73.   
74.     **public** **int** getId() \{  
75.         **return** id;  
76.     \}  
77.   
78.     **public** **void** setId(**int** id) \{  
79.         **this**.id = id;  
80.     \}  
81.   
82.     **public** String getName() \{  
83.         **return** name;  
84.     \}  
85.   
86.     **public** **void** setName(String name) \{  
87.         **this**.name = name;  
88.     \}  
89.   
90.     **public** **int** getHeight() \{  
91.         **return** height;  
92.     \}  
93.   
94.     **public** **void** setHeight(**int** height) \{  
95.         **this**.height = height;  
96.     \}  
97.   
98.     @Override  
99.     **public** String toString() \{  
100.         **return** "id:" + id + "; Name:" + **this**.name + "; height:" + **this**.height;  
101.     \}  
102.   
103.     @Override  
104.     **public** **boolean** equals(Object obj) \{  
105.         System.out.println("id:" + id + ", equals invokes");  
106.         **return** **super**.equals(obj);  
107.     \}  
108. \}

输出：

person id:1,hashCode() invoked,hashcode:443164103180  
person id:2,hashCode() invoked,hashcode:443164103180  
person id:1,hashCode() invoked,hashcode:443164103180  
\--dog\_1  
person id:2,hashCode() invoked,hashcode:443164103180  
\--dog\_2

解释：

（1）上面建立两个类，然后分别在hashCode和equal方法里面加上输出语句

（2）通过输出可以看到，其实我们重写的equals方法是没有被调用的，我们只需要通过hashcode就可以定位相应的对象

hash碰撞的代码：

**\[java\]**  [view plain][]   [copy][view plain]

1.  **package** com.ray.ch14;  
2.    
3.  **import** java.util.HashMap;  
4.    
5.  **public** **class** Test \{  
6.      **public** **static** **void** main(String\[\] args) \{  
7.          HashMap<Person, Dog> map = **new** HashMap<Person, Dog>();  
8.          Person person\_1 = **new** Person();  
9.          person\_1.setHeight(180);  
10.         person\_1.setId(1);  
11.         person\_1.setName("person\_1");  
12.         Person person\_2 = **new** Person();  
13.         person\_2.setHeight(180);  
14.         person\_2.setId(2);  
15.         person\_2.setName("person\_1");  
16.         Dog dog\_1 = **new** Dog();  
17.         dog\_1.setId(1);  
18.         dog\_1.setName("dog\_1");  
19.         Dog dog\_2 = **new** Dog();  
20.         dog\_2.setId(2);  
21.         dog\_2.setName("dog\_2");  
22.         map.put(person\_1, dog\_1);  
23.         map.put(person\_2, dog\_2);  
24.         System.out.println("--" + map.get(person\_1).getName());  
25.         System.out.println("--" + map.get(person\_2).getName());  
26.     \}  
27. \}  
28.   
29. **class** Dog \{  
30.     **private** **int** id = 0;  
31.     **private** String name = "";  
32.   
33.     **public** **int** getId() \{  
34.         **return** id;  
35.     \}  
36.   
37.     **public** **void** setId(**int** id) \{  
38.         **this**.id = id;  
39.     \}  
40.   
41.     **public** String getName() \{  
42.         **return** name;  
43.     \}  
44.   
45.     **public** **void** setName(String name) \{  
46.         **this**.name = name;  
47.     \}  
48.   
49.     @Override  
50.     **public** **int** hashCode() \{  
51.         System.out.println("dog's hashCode() invoked");  
52.         **return** id;  
53.     \}  
54.   
55.     @Override  
56.     **public** **boolean** equals(Object obj) \{  
57.         System.out.println("dog's equals invokes");  
58.         **return** **super**.equals(obj);  
59.     \}  
60. \}  
61.   
62. **class** Person \{  
63.     **private** **int** id = 0;  
64.     **private** String name = "";  
65.     **private** **int** height = 0;  
66.   
67.     @Override  
68.     **public** **int** hashCode() \{  
69.         System.out.println("person id:" + id + ",hashCode() invoked,"  
70.                 + "hashcode:" + **this**.name.hashCode() + **this**.height);  
71.         **return** **this**.name.hashCode() + **this**.height;// 重写的地方  
72.     \}  
73.   
74.     **public** **int** getId() \{  
75.         **return** id;  
76.     \}  
77.   
78.     **public** **void** setId(**int** id) \{  
79.         **this**.id = id;  
80.     \}  
81.   
82.     **public** String getName() \{  
83.         **return** name;  
84.     \}  
85.   
86.     **public** **void** setName(String name) \{  
87.         **this**.name = name;  
88.     \}  
89.   
90.     **public** **int** getHeight() \{  
91.         **return** height;  
92.     \}  
93.   
94.     **public** **void** setHeight(**int** height) \{  
95.         **this**.height = height;  
96.     \}  
97.   
98.     @Override  
99.     **public** String toString() \{  
100.         **return** "id:" + id + "; Name:" + **this**.name + "; height:" + **this**.height;  
101.     \}  
102.   
103.     @Override  
104.     **public** **boolean** equals(Object obj) \{  
105.         System.out.println("id:" + id + ", equals invokes");  
106.         **return** **super**.equals(obj);  
107.     \}  
108. \}

输出：

**\[java\]**  [view plain][]   [copy][view plain]

1.  person id:1,hashCode() invoked,hashcode:443164103180  
2.  person id:2,hashCode() invoked,hashcode:443164103180  
3.  id:2, equals invokes  
4.  person id:1,hashCode() invoked,hashcode:443164103180  
5.  id:1, equals invokes  
6.  \--dog\_1  
7.  person id:2,hashCode() invoked,hashcode:443164103180  
8.  \--dog\_2

解释：

（1）我们重写了Person，也就是key的hashCode方法，人为的产生hash碰撞现象

（2）从输出可以看出，上面的代码需要用到equals方法

回归put和get的源码；

下面是put的源码：

**\[java\]**  [view plain][]   [copy][view plain]

1.  **public** V put(K key, V value) \{  
2.         **if** (key == **null**)  
3.             **return** putForNullKey(value);  
4.         **int** hash = hash(key.hashCode());  
5.         **int** i = indexFor(hash, table.length);  
6.         **for** (Entry<K,V> e = table\[i\]; e != **null**; e = e.next) \{  
7.             Object k;  
8.             **if** (e.hash == hash && ((k = e.key) == key || key.equals(k))) \{ //注意的地方  
9.                 V oldValue = e.value;  
10.                e.value = value;  
11.                e.recordAccess(**this**);  
12.                **return** oldValue;  
13.            \}  
14.        \}  
15.   
16.        modCount++;  
17.        addEntry(hash, key, value, i);  
18.        **return** **null**;  
19.    \}

下面是get的源码：

**\[java\]**  [view plain][]   [copy][view plain]

1.  **public** V get(Object key) \{  
2.          **if** (key == **null**)  
3.              **return** getForNullKey();  
4.          **int** hash = hash(key.hashCode());  
5.          **for** (Entry<K,V> e = table\[indexFor(hash, table.length)\];  
6.               e != **null**;  
7.               e = e.next) \{  
8.              Object k;  
9.              **if** (e.hash == hash && ((k = e.key) == key || key.equals(k)))//注意的地方  
10.                 **return** e.value;  
11.         \}  
12.         **return** **null**;  
13.     \}

大家请注意我上面注释“注意的地方”：

（1）如果是平常没有hash碰撞的时候，前面的两个hash比较再加上key的地址的比较即可，然后后出现“短路”现象，使得后的句子不再执行。

（2）但是在出现hash碰撞的情况下，前面两个条件都成立，然后必须使用最后的equals来判断对象的相等。

3.hash碰撞出现的情景？

（1）一般会出现在大的数据情况之下

（2）hashcode的生成方法唯一性较弱（比如上面的人为的生产hashcode）

总结：这一章节主要通过介绍hash碰撞再一次深入了解HashMap的工作原理。

这一章节就到这里，谢谢。

[view plain]: http://blog.csdn.net/raylee2007/article/details/50449742#