從一道面試題徹底搞懂hashCode與equals的作用與區別及應當注意的細節

從一道面試題徹底搞懂hashCode與equals的作用與區別及應當注意的細節

   最近去面試了幾家公司,被問到hashCode的作用,雖然回答出來了,但是自己還是對hashCode和equals的作用一知半解的,所以決定把它們研究一下。

以前寫程式一直沒有注意hashCode的作用,一般都是覆蓋了equals,缺沒有覆蓋hashCode,現在發現這是埋下了很多潛在的Bug!今天就來說一說hashCode和equals的作用。

       先來試想一個場景,如果你想查詢一個集合中是否包含某個物件,那麼程式應該怎麼寫呢?通常的做法是逐一取出每個元素與要查詢的物件一一比較,當發現兩者進行equals比較結果相等時,則停止查詢並返回true,否則,返回false。但是這個做法的一個缺點是當集合中的元素很多時,譬如有一萬個元素,那麼逐一的比較效率勢必下降很快。於是有人發明了一種雜湊演算法來提高從該集合中查詢元素的效率,這種方式將集合分成若干個儲存區域(可以看成一個個桶),每個物件可以計算出一個雜湊碼,可以根據雜湊碼分組,每組分別對應某個儲存區域,這樣一個物件根據它的雜湊碼就可以分到不同的儲存區域(不同的桶中)。如下圖所示:

                           
                

實際的使用中,一個物件一般有key和value,可以根據key來計算它的hashCode。假設現在全部的物件都已經根據自己的hashCode值儲存在不同的儲存區域中了,那麼現在查詢某個物件(根據物件的key來查詢),不需要遍歷整個集合了,現在只需要計算要查詢物件的key的hashCode,然後找到該hashCode對應的儲存區域,在該儲存區域中來查詢就可以了,這樣效率也就提升了很多。說了這麼多相信你對hashCode的作用有了一定的瞭解,下面就來看看hashCode和equals的區別和聯絡。

在研究這個問題之前,首先說明一下JDK對equals(Object obj)和hashCode()這兩個方法的定義和規範:在Java中任何一個物件都具備equals(Object
obj)和hashCode()這兩個方法,因為他們是在Object類中定義的。 equals(Object obj)方法用來判斷兩個物件是否“相同”,如果“相同”則返回true,否則返回false。 hashCode()方法返回一個int數,在Object類中的預設實現是“將該物件的內部地址轉換成一個整數返回”。 

下面是官方文件給出的一些說明:

hashCode 的常規協定是:   
在 Java 應用程式執行期間,在同一物件上多次呼叫 hashCode 方法時,必須一致地返回相同的整數,前提是物件上 equals 比較中所用的資訊沒有被修改。從某一應用程式的一次執行到同一應用程式的另一次執行,該整數無需保持一致。   
如果根據 equals(Object) 方法,兩個物件是相等的,那麼在兩個物件中的每個物件上呼叫 hashCode 方法都必須生成相同的整數結果。   
以下情況不 是必需的:如果根據 equals(java.lang.Object) 方法,兩個物件不相等,那麼在兩個物件中的任一物件上呼叫 hashCode 方法必定會生成不同的整數結果。但是,程式設計師應該知道,為不相等的物件生成不同整數結果可以提高雜湊表的效能。   
實際上,由 Object 類定義的 hashCode 方法確實會針對不同的物件返回不同的整數。(這一般是通過將該物件的內部地址轉換成一個整數來實現的,但是 JavaTM 程式語言不需要這種實現技巧。)   
當equals方法被重寫時,通常有必要重寫 hashCode 方法,以維護 hashCode 方法的常規協定,該協定宣告相等物件必須具有相等的雜湊碼。

下面是我查閱了相關資料之後對以上的說明做的歸納總結:

1.若重寫了equals(Object obj)方法,則有必要重寫hashCode()方法。

2.若兩個物件equals(Object obj)返回true,則hashCode()有必要也返回相同的int數。

3.若兩個物件equals(Object obj)返回false,則hashCode()不一定返回不同的int數。

4.若兩個物件hashCode()返回相同int數,則equals(Object obj)不一定返回true。

5.若兩個物件hashCode()返回不同int數,則equals(Object
obj)一定返回false。

6.同一物件在執行期間若已經儲存在集合中,則不能修改影響hashCode值的相關資訊,否則會導致記憶體洩露問題。

想要弄清楚以上六點,先要知道什麼時候需要重寫equals和hashCode。一般來說涉及到物件之間的比較大小就需要重寫equals方法,但是為什麼第一點說重寫了equals就需要重寫hashCode呢?實際上這只是一條規範,如果不這樣做程式也可以執行,只不過會隱藏bug。一般一個類的物件如果會儲存在HashTable,HashSet,HashMap等雜湊儲存結構中,那麼重寫equals後最好也重寫hashCode,否則會導致儲存資料的不唯一性(儲存了兩個equals相等的資料)。而如果確定不會儲存在這些雜湊結構中,則可以不重寫hashCode。但是個人覺得還是重寫比較好一點,誰能保證後期不會儲存在這些結構中呢,況且重寫了hashCode也不會降低效能,因為線上性結構(如ArrayList)中是不會呼叫hashCode,所以重寫了也不要緊,也為後期的修改打了補丁。
下面來看一張物件放入雜湊集合的流程圖:

從上面的圖中可以清晰地看到在儲存一個物件時,先進行hashCode值的比較,然後進行equals的比較。可能現在你已經對上面的6點歸納有了一些認識。我們還可以通過JDK中得原始碼來認識一下具體hashCode和equals在程式碼中是如何呼叫的。

HashSet.java 

  public boolean add(E e) {
return map.put(e, PRESENT)==null;
}

HashMap.java

    public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount  ;
addEntry(hash, key, value, i);
return null;
}

最後再來看幾個測試的例子吧:

測試一:覆蓋equals(Object obj)但不覆蓋hashCode(),導致資料不唯一性

public class HashCodeTest {
public static void main(String[] args) {
Collection set = new HashSet();
Point p1 = new Point(1, 1);
Point p2 = new Point(1, 1);
System.out.println(p1.equals(p2));
set.add(p1);   //(1)
set.add(p2);   //(2)
set.add(p1);   //(3)
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
Object object = iterator.next();
System.out.println(object);
}
}
}
class Point {
private int x;
private int y;
public Point(int x, int y) {
super();
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Point other = (Point) obj;
if (x != other.x)
return false;
if (y != other.y)
return false;
return true;
}
@Override
public String toString() {
return "x:"   x   ",y:"   y;
}
}

輸出結果:

true
x:1,y:1
x:1,y:1

原因分析:

(1)當執行set.add(p1)時(1),集合為空,直接存入集合;

(2)當執行set.add(p2)時(2),首先判斷該物件(p2)的hashCode值所在的儲存區域是否有相同的hashCode,因為沒有覆蓋hashCode方法,所以jdk使用預設Object的hashCode方法,返回記憶體地址轉換後的整數,因為不同物件的地址值不同,所以這裡不存在與p2相同hashCode值的物件,因此jdk預設不同hashCode值,equals一定返回false,所以直接存入集合。

 (3)當執行set.add(p1)時(3),時,因為p1已經存入集合,同一物件返回的hashCode值是一樣的,繼續判斷equals是否返回true,因為是同一物件所以返回true。此時jdk認為該物件已經存在於集合中,所以捨棄。

測試二:覆蓋hashCode方法,但不覆蓋equals方法,仍然會導致資料的不唯一性

修改Point類:

class Point {
private int x;
private int y;
public Point(int x, int y) {
super();
this.x = x;
this.y = y;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result   x;
result = prime * result   y;
return result;
}
@Override
public String toString() {
return "x:"   x   ",y:"   y;
}
}

輸出結果:

false
x:1,y:1
x:1,y:1

原因分析:

(1)當執行set.add(p1)時(1),集合為空,直接存入集合;

(2)當執行set.add(p2)時(2),首先判斷該物件(p2)的hashCode值所在的儲存區域是否有相同的hashCode,這裡覆蓋了hashCode方法,p1和p2的hashCode相等,所以繼續判斷equals是否相等,因為這裡沒有覆蓋equals,預設使用’==’來判斷,所以這裡equals返回false,jdk認為是不同的物件,所以將p2存入集合。

 (3)當執行set.add(p1)時(3),時,因為p1已經存入集合,同一物件返回的hashCode值是一樣的,並且equals返回true。此時jdk認為該物件已經存在於集合中,所以捨棄。

綜合上述兩個測試,要想保證元素的唯一性,必須同時覆蓋hashCode和equals才行。
(注意:在HashSet中插入同一個元素(hashCode和equals均相等)時,會被捨棄,而在HashMap中插入同一個Key(Value 不同)時,原來的元素會被覆蓋。)
測試三:在記憶體洩露問題
public class HashCodeTest {
public static void main(String[] args) {
Collection set = new HashSet();
Point p1 = new Point(1, 1);
Point p2 = new Point(1, 2);
set.add(p1);
set.add(p2);
p2.setX(10);
p2.setY(10);
set.remove(p2);
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
Object object = iterator.next();
System.out.println(object);
}
}
}
class Point {
private int x;
private int y;
public Point(int x, int y) {
super();
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result   x;
result = prime * result   y;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Point other = (Point) obj;
if (x != other.x)
return false;
if (y != other.y)
return false;
return true;
}
@Override
public String toString() {
return "x:"   x   ",y:"   y;
}
}

執行結果:

x:1,y:1
x:10,y:10

原因分析:

    假設p1的hashCode為1,p2的hashCode為2,在儲存時p1被分配在1號桶中,p2被分配在2號筒中。這時修改了p2中與計算hashCode有關的資訊(x和y),當呼叫remove(Object obj)時,首先會查詢該hashCode值得物件是否在集合中。假設修改後的hashCode值為10(仍存在2號桶中),這時查詢結果空,jdk認為該物件不在集合中,所以不會進行刪除操作。然而使用者以為該物件已經被刪除,導致該物件長時間不能被釋放,造成記憶體洩露。解決該問題的辦法是不要在執行期間修改與hashCode值有關的物件資訊,如果非要修改,則必須先從集合中刪除,更新資訊後再加入集合中。
總結:
   1.hashCode是為了提高在雜湊結構儲存中查詢的效率,線上性表中沒有作用。
   2.equals和hashCode需要同時覆蓋。
   3.若兩個物件equals返回true,則hashCode有必要也返回相同的int數。

4.若兩個物件equals返回false,則hashCode不一定返回不同的int數,但為不相等的物件生成不同hashCode值可以提高
雜湊表的效能。

5.若兩個物件hashCode返回相同int數,則equals不一定返回true。

6.若兩個物件hashCode返回不同int數,則equals一定返回false。

   7.同一物件在執行期間若已經儲存在集合中,則不能修改影響hashCode值的相關資訊,否則會導致記憶體洩露問題。