分析Java的hashCode 和 hashCode在HashMap的底层数据结构的应用

小灰灰 2022-09-25 04:20 115阅读 0赞

**一、java对象的比较**

等号(==)：

对比对象实例的内存地址（也即对象实例的ID），来判断是否是同一对象实例；又可以说是判断对象实例是否物理相等；

equals()：

对比两个对象实例是否相等。

当对象所属的类没有重写根类Object的equals()方法时，equals()判断的是对象实例的ID（内存地址），是否是同一对象实例；该方法就是使用的等号(==)的判断结果，如Object类的源代码所示：

Java代码 ![收藏代码][icon_star.png]

1.  **public****boolean** equals(Object obj) \{ 
2.  **return** (**this** == obj); 
3.  \}

当对象所属的类重写equals()方法（可能因为需要自己特有的“逻辑相等”概念)时，equals()判断的根据就因具体实现而异，有些类是需要比较对象的某些指或内容，如String类重写equals()来判断字符串的值是否相等。判断逻辑相等。

hashCode():

计算出对象实例的哈希码，并返回哈希码，又称为散列函数。根类Object的hashCode()方法的计算依赖于对象实例的D（内存地址），故每个Object对象的hashCode都是唯一的；当然，当对象所对应的类重写了hashCode()方法时，结果就截然不同了。

**二、Java的类为什么需要hashCode？---hashCode的作用，从Java中的集合的角度看。**

总的来说，Java中的集合（Collection）有两类，一类是List，再有一类是Set。你知道它们的区别吗？前者集合内的元素是有序的，元素可以重复；后者元素无序，但元素不可重复。那么这里就有一个比较严重的问题了：要想保证元素不重复，可两个元素是否重复应该依据什么来判断呢？这就是 Object.equals方法了。但是，如果每增加一个元素就检查一次，那么当元素很多时，后添加到集合中的元素比较的次数就非常多了。也就是说，如果集合中现在已经有1000个元素，那么第1001个元素加入集合时，它就要调用1000次equals方法。这显然会大大降低效率。

于是，Java采用了哈希表的原理。哈希算法也称为散列算法，是将数据依特定算法直接指定到一个地址上。关于哈希算法，这里就不详细介绍。可以这样简单理解，hashCode方法实际上返回的就是对象存储位置的映像。

这样一来，当集合要添加新的元素时，先调用这个元素的hashCode方法，就能定位到它应该放置的存储位置。如果这个位置上没有元素，它就可以直接存储在这个位置上，不用再进行任何比较了；如果这个位置上已经有元素了，就调用它的equals方法与新元素进行比较，相同的话就不存了，不相同就表示发生冲突了，散列表对于冲突有具体的解决办法，但最终还会将新元素保存在适当的位置。这样一来，实际调用equals方法的次数就大大降低了，几乎只需要一两次。

所以，Java对于eqauls方法和hashCode方法是这样规定的：  
**1、相等的对象必须具有相等的哈希码（或者散列码）。  
2、如果两个对象的hashCode相同，它们并不一定相同。**  
  
上述的对象相同指的是通过eqauls方法判断，结果为true。

你当然可以不按要求去做了，但你会发现，相同的对象可以出现在Set集合中。同时，增加新元素的效率会大大下降。

**三、深入解析HashMap类的底层数据结构**

Map接口  
　　Map没有继承Collection接口，Map提供key到value的映射。一个Map中不能包含相同的key，每个key只能映射一个 value。Map接口提供3种集合的视图，Map的内容可以被当作一组key集合，一组value集合，或者一组key-value映射。

Hashtable类  
　　Hashtable继承Map接口，实现一个key-value映射的哈希表。任何非空（non-null）的对象都可作为key或者value。添加数据使用put(key, value)，取出数据使用get(key)，这两个基本操作的时间开销为常数。

Hashtable通过initial capacity和load factor两个参数调整性能。通常缺省的load factor 0.75较好地实现了时间和空间的均衡。增大load factor可以节省空间但相应的查找时间将增大，这会影响像get和put这样的操作。  
使用Hashtable的简单示例如下，将1，2，3放到Hashtable中，他们的key分别是”one”，”two”，”three”：  
　　　　Hashtable numbers = new Hashtable();  
　　　　numbers.put(“one”, new Integer(1));  
　　　　numbers.put(“two”, new Integer(2));  
　　　　numbers.put(“three”, new Integer(3));  
　　要取出一个数，比如2，用相应的key：  
　　　　Integer n = (Integer)numbers.get(“two”);  
　　　　System.out.println(“two = ” + n);

1. HashMap概述：  
HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。  
  
2. HashMap的数据结构：  
HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。首先，HashMap类的属性中定义了Entry类型的数组。Entry类实现java.ultil.Map.Entry接口，同时每一对key和value是作为Entry类的属性被包装在Entry的类中。

如图所示，HashMap的数据结构：  
  
![eab581f9-889f-31e7-9d72-321919d99c37.jpg][]

HashMap的部分源码如下：

Java代码 ![收藏代码][icon_star.png]

1.  /\*\*
2.   \* The table, resized as necessary. Length MUST Always be a power of two.
3.   \*/
4.  
5.  **transient** Entry\[\] table; 
6.  
7.  **static****class** Entry<K,V> **implements** Map.Entry<K,V> \{ 
8.  **final** K key; 
9.   V value; 
10.  Entry<K,V> next; 
11. **final****int** hash; 
12.  …… 
13. \}

可以看出，HashMap底层就是一个数组结构，数组中的每一项又是一个链表。当新建一个HashMap的时候，就会初始化一个数组。table数组的元素是Entry类型的。每个 Entry元素其实就是一个key-value对，并且它持有一个指向下一个 Entry元素的引用，这就说明table数组的每个Entry元素同时也作为某个Entry链表的首节点，指向了该链表的下一个Entry元素，这就是所谓的“链表散列”数据结构，即数组和链表的结合体。

3. HashMap的存取实现：

1) 添加元素：

当我们往HashMap中put元素的时候，先根据key的重新计算元素的hashCode，根据hashCode得到这个元素在table数组中的位置（即下标），如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。

HashMap的部分源码如下：

Java代码 ![收藏代码][icon_star.png]

1.  **public** V put(K key, V value) \{ 
2.  // HashMap允许存放null键和null值。
3.  // 当key为null时，调用putForNullKey方法，将value放置在数组第一个位置。
4.  **if** (key == **null**) 
5.  **return** putForNullKey(value); 
6.  // 根据key的keyCode重新计算hash值。
7.  **int** hash = hash(key.hashCode()); 
8.  // 搜索指定hash值在对应table中的索引。
9.  **int** i = indexFor(hash, table.length); 
10. // 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素。
11. **for** (Entry<K,V> e = table\[i\]; e != **null**; e = e.next) \{ 
12.  Object k; 
13. // 如果发现 i 索引处的链表的某个Entry的hash和新Entry的hash相等且两者的key相同，则新Entry覆盖旧Entry，返回。
14. **if** (e.hash == hash && ((k = e.key) == key || key.equals(k))) \{ 
15.  V oldValue = e.value; 
16.  e.value = value; 
17.  e.recordAccess(**this**); 
18. **return** oldValue; 
19.  \} 
20.  \} 
21. // 如果i索引处的Entry为null，表明此处还没有Entry。
22.  modCount++; 
23. // 将key、value添加到i索引处。
24.  addEntry(hash, key, value, i); 
25. **return****null**;

2) 读取元素：

有了上面存储时的hash算法作为基础，理解起来这段代码就很容易了。从上面的源代码中可以看出：从HashMap中get元素时，首先计算key的hashCode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。

HashMap的部分源码如下：

Java代码 ![收藏代码][icon_star.png]

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. \}

3) 归纳起来简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry\[\] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。

**四、关于“相等的对象必须具有相等的哈希码”**

由于作为key的对象将通过计算其散列函数hashCode()来确定与之对应的value的位置，因此任何作为key的对象都必须实现hashCode和equals方法。hashCode和equals方法继承自根类Object，如果你用自定义的类当作key的话，要相当小心，按照散列函数的定义，如果两个对象相同，即obj1.equals(obj2)=true，则它们的hashCode必须相同，但如果两个对象不同，则它们的hashCode不一定不同，如果两个不同对象的hashCode相同，这种现象称为冲突，冲突会导致操作哈希表的时间开销增大，所以尽量定义好的hashCode()方法，能加快哈希表的操作。  
　　如果相同的对象有不同的hashCode，对哈希表的操作会出现意想不到的结果（期待的get方法返回null），要避免这种问题，只需要牢记一条：要同时复写equals方法和hashCode方法，而不要只写其中一个。

同时复写equals方法和hashCode方法,必须保证“相等的对象必须具有相等的哈希码”，也就是当两个对象通过equals()比较的结果为true时，这两个对象调用hashCode（）方法生成的哈希码必须相等。

如何保证相等，可以参考下面的方法：

复写equals方法和hashCode方法时，equals方法的判断根据和计算hashCode的依据相同。如String的equals方法是比较字符串每个字符，String的hashCode也是通过对该字符串每个字符的ASC码简单的算术运算所得，这样就可以保证相同的字符串的hashCode相同且equals()为真。

String类的equals方法的源代码：

Java代码 ![收藏代码][icon_star.png]

1.  /\*\*
2.   \* Compares this string to the specified object. The result is \{@code
3.   \* true\} if and only if the argument is not \{@code null\} and is a \{@code
4.   \* String\} object that represents the same sequence of characters as this
5.   \* object.
6.   \*
7.   \* @param anObject
8.   \* The object to compare this \{@code String\} against
9.   \*
10.  \* @return \{@code true\} if the given object represents a \{@code String\}
11.  \* equivalent to this string, \{@code false\} otherwise
12.  \*
13.  \* @see \#compareTo(String)
14.  \* @see \#equalsIgnoreCase(String)
15.  \*/
16. **public****boolean** equals(Object anObject) \{ 
17. **if** (**this** == anObject) \{ 
18. **return****true**; 
19. \} 
20. **if** (anObject **instanceof** String) \{ 
21.  String anotherString = (String)anObject; 
22. **int** n = count; 
23. **if** (n == anotherString.count) \{ 
24. **char** v1\[\] = value; 
25. **char** v2\[\] = anotherString.value; 
26. **int** i = offset; 
27. **int** j = anotherString.offset; 
28. **while** (n-- != 0) \{ 
29. **if** (v1\[i++\] != v2\[j++\]) 
30. **return****false**; 
31.  \} 
32. **return****true**; 
33.  \} 
34. \} 
35. **return****false**; 
36.  \}

String类的hashCode方法计算hashCode的源代码：

Java代码 ![收藏代码][icon_star.png]

1.  /\*\*
2.   \* Returns a hash code for this string. The hash code for a
3.   \* <code>String</code> object is computed as
4.   \* <blockquote><pre>
5.   \* s\[0\]\*31^(n-1) + s\[1\]\*31^(n-2) + ... + s\[n-1\]
6.   \* </pre></blockquote>
7.   \* using <code>int</code> arithmetic, where <code>s\[i\]</code> is the
8.   \* <i>i</i>th character of the string, <code>n</code> is the length of
9.   \* the string, and <code>^</code> indicates exponentiation.
10.  \* (The hash value of the empty string is zero.)
11.  \*
12.  \* @return a hash code value for this object.
13.  \*/
14. **public****int** hashCode() \{ 
15. **int** h = hash; 
16. **int** len = count; 
17. **if** (h == 0 && len > 0) \{ 
18. **int** off = offset; 
19. **char** val\[\] = value; 
20. 
21. **for** (**int** i = 0; i < len; i++) \{ 
22.  h = 31\*h + val\[off++\]; 
23.  \} 
24.  hash = h; 
25.  \} 
26. **return** h; 
27.  \}

来自：http://kakajw.iteye.com/blog/935226

[icon_star.png]: /images/20220718/95df1e0459394f1f8a4c934bffe2b454.png
[eab581f9-889f-31e7-9d72-321919d99c37.jpg]: /images/20220718/223de6cb9ee94284bd2f8cbcde32b9ab.png