在 Java 集合中有兩類,一類是 List,一類是 Set 他們之間的區別就在於 List 集合中的元素師有序的,且可以重復,而 Set 集合中元素是無序不可重復的。對於 List 好處理,但是對於 Set 而言我們要如何來保證元素不重復呢?通過迭代來 equals() 是否相等。數據量小還可以接受,當我們的數據量大的時候效率可想而知(當然我們可以利用算法進行優化)。比如我們向 HashSet 插入 1000 數據,難道我們真的要迭代 1000 次,調用 1000 次 equals() 方法嗎?hashCode 提供了解決方案。怎麼實現?我們先看 hashCode 的源碼:
public native int hashCode();
當我們向一個集合中添加某個元素,集合會首先調用 hashCode 方法,這樣就可以直接定位它所存儲的位置,若該處沒有其他元素,則直接保存。若該處已經有元素存在,就調用 equals 方法來匹配這兩個元素是否相同,相同則不存,不同則散列到其他位置。
這樣處理,當我們存入大量元素時就可以大大減少調用 equals() 方法的次數,極大地提高了效率。
所以 hashCode 在上面扮演的角色為尋域(尋找某個對象在集合中區域位置)。hashCode 可以將集合分成若干個區域,每個對象都可以計算出他們的 hash 碼,可以將 hash 碼分組,每個分組對應著某個存儲區域,根據一個對象的 hash 碼就可以確定該對象所存儲區域,這樣就大大減少查詢匹配元素的數量,提高了查詢效率。
hashCode 重要麼?不重要,對於 List 集合、數組而言,他就是一個累贅,但是對於 HashMap、HashSet、HashTable 而言,它變得異常重要。所以在使用 HashMap、HashSet、HashTable 時一定要注意 hashCode。對於一個對象而言,其 hashCode 過程就是一個簡單的 Hash 算法的實現,其實現過程對你實現對象的存取過程起到非常重要的作用。
在前面提到了 HashMap 和 HashTable 兩種數據結構,雖然他們存在若干個區別,但是他們的實現原理是相同的,這裡我以 HashTable 為例闡述 hashCode 對於一個對象的重要性。
一個對象勢必會存在若干個屬性,如何選擇屬性來進行散列考驗著一個人的設計能力。如果我們將所有屬性進行散列,這必定會是一個糟糕的設計,因為對象的 hashCode 方法無時無刻不是在被調用,如果太多的屬性參與散列,那麼需要的操作數時間將會大大增加,這將嚴重影響程序的性能。但是如果較少屬相參與散列,散列的多樣性會削弱,會產生大量的散列“沖突”,除了不能夠很好的利用空間外,在某種程度也會影響對象的查詢效率。其實這兩者是一個矛盾體,散列的多樣性會帶來性能的降低。
那麼如何對對象的 hashCode 進行設計。從網上查到了這樣一種解決方案:設置一個緩存標識來緩存當前的散列碼,只有當參與散列的對象改變時才會重新計算,否則調用緩存的 hashCode,這樣就可以從很大程度上提高性能。
在 HashTable 計算某個對象在 table[] 數組中的索引位置,其代碼如下:
int index = (hash & 0x7FFFFFFF) % tab.length;
為什麼要 &0x7FFFFFFF?因為某些對象的 hashCode 可能會為負值,與 0x7FFFFFFF 進行與運算可以確保 index 為一個正數。通過這步我可以直接定位某個對象的位置,所以從理論上來說我們是完全可以利用 hashCode 直接定位對象的散列表中的位置,但是為什麼會存在一個 key-value 的鍵值對,利用 key 的 hashCode 來存入數據而不是直接存放 value 呢?這就關系 HashTable 性能問題的最重要的問題:Hash 沖突!
我們知道沖突的產生是由於不同的對象產生了相同的散列碼,假如我們設計對象的散列碼可以確保 99.999999999% 的不重復,但是有一種絕對且幾乎不可能遇到的沖突你是絕對避免不了的。我們知道 hashcode 返回的是 int,它的值只可能在 int 范圍內。如果我們存放的數據超過了 int 的范圍呢?這樣就必定會產生兩個相同的 index,這時在 index 位置處會存儲兩個對象,我們就可以利用 key 本身來進行判斷。所以具有相索引的對象,在該 index 位置處存在多個對象,我們必須依靠 key 的 hashCode和key 本身來進行區分。
在 Java 中 hashCode 的實現總是伴隨著 equals,他們是緊密配合的,你要是自己設計了其中一個,就要設計另外一個。當然在多數情況下,這兩個方法是不用我們考慮的,直接使用默認方法就可以幫助我們解決很多問題。但是在有些情況,我們必須要自己動手來實現它,才能確保程序更好的運作。
對於 equals,我們必須遵循如下規則:
對稱性:如果 x.equals(y) 返回是“true”,那麼 y.equals(x) 也應該返回是“true”。
反射性:x.equals(x) 必須返回是“true”。
類推性:如果 x.equals(y) 返回是“true”,而且 y.equals(z) 返回是“true”,那麼 z.equals(x) 也應該返回是“true”。
一致性:如果 x.equals(y) 返回是“true”,只要x和y內容一直不變,不管你重復 x.equals(y) 多少次,返回都是“true”。
任何情況下,x.equals(null),永遠返回是“false”;x.equals(和x不同類型的對象)永遠返回是“false”。
對於 hashCode,我們應該遵循如下規則:
在一個應用程序執行期間,如果一個對象的 equals 方法做比較所用到的信息沒有被修改的話,則對該對象調用 hashCode 方法多次,它必須始終如一地返回同一個整數。
如果兩個對象根據 equals(Object o) 方法是相等的,則調用這兩個對象中任一對象的 hashCode 方法必須產生相同的整數結果。
至於兩者之間的關聯關系,我們只需要記住如下即可:
如果 x.equals(y) 返回“true”,那麼 x 和 y 的 hashCode() 必須相等。
如果 x.equals(y) 返回“false”,那麼 x 和 y 的 hashCode() 有可能相等,也有可能不等。
理清了上面的關系我們就知道他們兩者是如何配合起來工作的。先看下圖:
整個處理流程是:
1、判斷兩個對象的 hashcode 是否相等,若不等,則認為兩個對象不等,完畢,若相等,則比較 equals。
2、若兩個對象的 equals 不等,則可以認為兩個對象不等,否則認為他們相等。
實例:
public class Person { private int age; private int sex; //0:男,1:女 private String name; private final int PRIME = 37; Person(int age ,int sex ,String name){ this.age = age; this.sex = sex; this.name = name; } /** 省略getter、setter方法 **/ @Override public int hashCode() { System.out.println("調用hashCode方法..........."); int hashResult = 1; hashResult = (hashResult + Integer.valueOf(age).hashCode() + Integer.valueOf(sex).hashCode()) * PRIME; hashResult = PRIME * hashResult + ((name == null) ? 0 : name.hashCode()); System.out.println("name:"+name +" hashCode:" + hashResult); return hashResult; } /** * 重寫hashCode() */ public boolean equals(Object obj) { System.out.println("調用equals方法..........."); if(obj == null){ return false; } if(obj.getClass() != this.getClass()){ return false; } if(this == obj){ return true; } Person person = (Person) obj; if(getAge() != person.getAge() || getSex()!= person.getSex()){ return false; } if(getName() != null){ if(!getName().equals(person.getName())){ return false; } } else if(person != null){ return false; } return true; } }
public class Main extends JPanel { public static void main(String[] args) { Set<Person> set = new HashSet<Person>(); Person p1 = new Person(11, 1, "張三"); Person p2 = new Person(12, 1, "李四"); Person p3 = new Person(11, 1, "張三"); Person p4 = new Person(11, 1, "李四"); //只驗證p1、p3 System.out.println("p1 == p3? :" + (p1 == p3)); System.out.println("p1.equals(p3)?:"+p1.equals(p3)); System.out.println("-----------------------分割線--------------------------"); set.add(p1); set.add(p2); set.add(p3); set.add(p4); System.out.println("set.size()="+set.size()); } }