在前面三篇博文中 LZ 講解了（HashMap、HashSet、HashTable），在其中 LZ 不斷地講解他們的 put 和 get 方法，在這兩個(gè)方法中計(jì)算 key 的 hashCode 應(yīng)該是最重要也是最精華的部分，所以下面 LZ 揭開(kāi) hashCode 的“神秘”面紗。
要想了解一個(gè)方法的內(nèi)在原理，我們首先需要明白它是干什么的，也就是這個(gè)方法的作用。在講解數(shù)組時(shí)（java 提高篇（十八）——數(shù)組），我們提到數(shù)組是java中效率最高的數(shù)據(jù)結(jié)構(gòu)，但是“最高”是有前提的。第一我們需要知道所查詢(xún)數(shù)據(jù)的所在位置。第二：如果我們進(jìn)行迭代查找時(shí)，數(shù)據(jù)量一定要小，對(duì)于大數(shù)據(jù)量而言一般推薦集合。
在 Java 集合中有兩類(lèi)，一類(lèi)是 List，一類(lèi)是 Set 他們之間的區(qū)別就在于 List 集合中的元素師有序的，且可以重復(fù)，而 Set 集合中元素是無(wú)序不可重復(fù)的。對(duì)于 List 好處理，但是對(duì)于 Set 而言我們要如何來(lái)保證元素不重復(fù)呢？通過(guò)迭代來(lái) equals() 是否相等。數(shù)據(jù)量小還可以接受，當(dāng)我們的數(shù)據(jù)量大的時(shí)候效率可想而知（當(dāng)然我們可以利用算法進(jìn)行優(yōu)化）。比如我們向 HashSet 插入 1000 數(shù)據(jù)，難道我們真的要迭代 1000 次，調(diào)用 1000 次 equals() 方法嗎？hashCode 提供了解決方案。怎么實(shí)現(xiàn)？我們先看 hashCode 的源碼(Object)。
public native int hashCode();
它是一個(gè)本地方法，它的實(shí)現(xiàn)與本地機(jī)器有關(guān)，這里我們暫且認(rèn)為他返回的是對(duì)象存儲(chǔ)的物理位置（實(shí)際上不是，這里寫(xiě)是便于理解）。當(dāng)我們向一個(gè)集合中添加某個(gè)元素，集合會(huì)首先調(diào)用 hashCode 方法，這樣就可以直接定位它所存儲(chǔ)的位置，若該處沒(méi)有其他元素，則直接保存。若該處已經(jīng)有元素存在，就調(diào)用 equals 方法來(lái)匹配這兩個(gè)元素是否相同，相同則不存，不同則散列到其他位置（具體情況請(qǐng)參考（Java 提高篇（）—–HashMap））。這樣處理，當(dāng)我們存入大量元素時(shí)就可以大大減少調(diào)用 equals() 方法的次數(shù)，極大地提高了效率。
所以 hashCode 在上面扮演的角色為尋域（尋找某個(gè)對(duì)象在集合中區(qū)域位置）。hashCode 可以將集合分成若干個(gè)區(qū)域，每個(gè)對(duì)象都可以計(jì)算出他們的 hash 碼，可以將 hash 碼分組，每個(gè)分組對(duì)應(yīng)著某個(gè)存儲(chǔ)區(qū)域，根據(jù)一個(gè)對(duì)象的 hash 碼就可以確定該對(duì)象所存儲(chǔ)區(qū)域，這樣就大大減少查詢(xún)匹配元素的數(shù)量，提高了查詢(xún)效率。
hashCode 重要么？不重要，對(duì)于 List 集合、數(shù)組而言，他就是一個(gè)累贅，但是對(duì)于 HashMap、HashSet、HashTable 而言，它變得異常重要。所以在使用 HashMap、HashSet、HashTable 時(shí)一定要注意 hashCode。對(duì)于一個(gè)對(duì)象而言，其 hashCode 過(guò)程就是一個(gè)簡(jiǎn)單的 Hash 算法的實(shí)現(xiàn)，其實(shí)現(xiàn)過(guò)程對(duì)你實(shí)現(xiàn)對(duì)象的存取過(guò)程起到非常重要的作用。
在前面 LZ 提到了 HashMap 和 HashTable 兩種數(shù)據(jù)結(jié)構(gòu)，雖然他們存在若干個(gè)區(qū)別，但是他們的實(shí)現(xiàn)原理是相同的，這里我以 HashTable 為例闡述 hashCode 對(duì)于一個(gè)對(duì)象的重要性。
一個(gè)對(duì)象勢(shì)必會(huì)存在若干個(gè)屬性，如何選擇屬性來(lái)進(jìn)行散列考驗(yàn)著一個(gè)人的設(shè)計(jì)能力。如果我們將所有屬性進(jìn)行散列，這必定會(huì)是一個(gè)糟糕的設(shè)計(jì)，因?yàn)閷?duì)象的 hashCode 方法無(wú)時(shí)無(wú)刻不是在被調(diào)用，如果太多的屬性參與散列，那么需要的操作數(shù)時(shí)間將會(huì)大大增加，這將嚴(yán)重影響程序的性能。但是如果較少屬相參與散列，散列的多樣性會(huì)削弱，會(huì)產(chǎn)生大量的散列“沖突”，除了不能夠很好的利用空間外，在某種程度也會(huì)影響對(duì)象的查詢(xún)效率。其實(shí)這兩者是一個(gè)矛盾體，散列的多樣性會(huì)帶來(lái)性能的降低。
那么如何對(duì)對(duì)象的 hashCode 進(jìn)行設(shè)計(jì)，LZ 也沒(méi)有經(jīng)驗(yàn)。從網(wǎng)上查到了這樣一種解決方案：設(shè)置一個(gè)緩存標(biāo)識(shí)來(lái)緩存當(dāng)前的散列碼，只有當(dāng)參與散列的對(duì)象改變時(shí)才會(huì)重新計(jì)算，否則調(diào)用緩存的 hashCode，這樣就可以從很大程度上提高性能。
在 HashTable 計(jì)算某個(gè)對(duì)象在 table[] 數(shù)組中的索引位置，其代碼如下：
int index = (hash & 0x7FFFFFFF) % tab.length;
為什么要 &0x7FFFFFFF？因?yàn)槟承?duì)象的 hashCode 可能會(huì)為負(fù)值，與 0x7FFFFFFF 進(jìn)行與運(yùn)算可以確保 index 為一個(gè)正數(shù)。通過(guò)這步我可以直接定位某個(gè)對(duì)象的位置，所以從理論上來(lái)說(shuō)我們是完全可以利用 hashCode 直接定位對(duì)象的散列表中的位置，但是為什么會(huì)存在一個(gè) key-value 的鍵值對(duì)，利用 key 的 hashCode 來(lái)存入數(shù)據(jù)而不是直接存放 value 呢？這就關(guān)系 HashTable 性能問(wèn)題的最重要的問(wèn)題:Hash 沖突！
我們知道沖突的產(chǎn)生是由于不同的對(duì)象產(chǎn)生了相同的散列碼，假如我們?cè)O(shè)計(jì)對(duì)象的散列碼可以確保 99.999999999% 的不重復(fù)，但是有一種絕對(duì)且?guī)缀醪豢赡苡龅降臎_突你是絕對(duì)避免不了的。我們知道 hashcode 返回的是 int，它的值只可能在 int 范圍內(nèi)。如果我們存放的數(shù)據(jù)超過(guò)了 int 的范圍呢？這樣就必定會(huì)產(chǎn)生兩個(gè)相同的 index，這時(shí)在 index 位置處會(huì)存儲(chǔ)兩個(gè)對(duì)象，我們就可以利用 key 本身來(lái)進(jìn)行判斷。所以具有相索引的對(duì)象，在該 index 位置處存在多個(gè)對(duì)象，我們必須依靠 key 的 hashCode和key 本身來(lái)進(jìn)行區(qū)分。
在 Java 中 hashCode 的實(shí)現(xiàn)總是伴隨著 equals，他們是緊密配合的，你要是自己設(shè)計(jì)了其中一個(gè)，就要設(shè)計(jì)另外一個(gè)。當(dāng)然在多數(shù)情況下，這兩個(gè)方法是不用我們考慮的，直接使用默認(rèn)方法就可以幫助我們解決很多問(wèn)題。但是在有些情況，我們必須要自己動(dòng)手來(lái)實(shí)現(xiàn)它，才能確保程序更好的運(yùn)作。
對(duì)于 equals，我們必須遵循如下規(guī)則：
對(duì)稱(chēng)性：如果 x.equals(y) 返回是“true”，那么 y.equals(x) 也應(yīng)該返回是“true”。
反射性：x.equals(x) 必須返回是“true”。
類(lèi)推性：如果 x.equals(y) 返回是“true”，而且 y.equals(z) 返回是“true”，那么 z.equals(x) 也應(yīng)該返回是“true”。
一致性：如果 x.equals(y) 返回是“true”，只要x和y內(nèi)容一直不變，不管你重復(fù) x.equals(y) 多少次，返回都是“true”。
任何情況下，x.equals(null)，永遠(yuǎn)返回是“false”；x.equals(和x不同類(lèi)型的對(duì)象)永遠(yuǎn)返回是“false”。
對(duì)于 hashCode，我們應(yīng)該遵循如下規(guī)則：
在一個(gè)應(yīng)用程序執(zhí)行期間，如果一個(gè)對(duì)象的 equals 方法做比較所用到的信息沒(méi)有被修改的話(huà)，則對(duì)該對(duì)象調(diào)用 hashCode 方法多次，它必須始終如一地返回同一個(gè)整數(shù)。
如果兩個(gè)對(duì)象根據(jù) equals(Object o) 方法是相等的，則調(diào)用這兩個(gè)對(duì)象中任一對(duì)象的 hashCode 方法必須產(chǎn)生相同的整數(shù)結(jié)果。
至于兩者之間的關(guān)聯(lián)關(guān)系，我們只需要記住如下即可：
如果 x.equals(y) 返回“true”，那么 x 和 y 的 hashCode() 必須相等。
如果 x.equals(y) 返回“false”，那么 x 和 y 的 hashCode() 有可能相等，也有可能不等。
理清了上面的關(guān)系我們就知道他們兩者是如何配合起來(lái)工作的。先看下圖：
http://wiki.jikexueyuan.com/project/java-enhancement/images/26-1.png" alt="fig.1" />
整個(gè)處理流程是：
1、判斷兩個(gè)對(duì)象的 hashcode 是否相等，若不等，則認(rèn)為兩個(gè)對(duì)象不等，完畢，若相等，則比較 equals。
2、若兩個(gè)對(duì)象的 equals 不等，則可以認(rèn)為兩個(gè)對(duì)象不等，否則認(rèn)為他們相等。
實(shí)例：
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("調(diào)用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;
}
/**
* 重寫(xiě)hashCode()
*/
public boolean equals(Object obj) {
System.out.println("調(diào)用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;
}
}
該 Bean 為一個(gè)標(biāo)準(zhǔn)的 Java Bean，重新實(shí)現(xiàn)了 hashCode 方法和 equals 方法。
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, "李四");
//只驗(yàn)證p1、p3
System.out.println("p1 == p3? :" + (p1 == p3));
System.out.println("p1.equals(p3)?:"+p1.equals(p3));
System.out.println("-----------------------分割線(xiàn)--------------------------");
set.add(p1);
set.add(p2);
set.add(p3);
set.add(p4);
System.out.println("set.size()="+set.size());
}
}
運(yùn)行結(jié)果如下：
http://wiki.jikexueyuan.com/project/java-enhancement/images/26-2.png" alt="fig.2" />
從上圖可以看出，程序調(diào)用四次 hashCode 方法，一次 equals 方法，其 set 的長(zhǎng)度只有 3。add 方法運(yùn)行流程完全符合他們兩者之間的處理流程。
更多請(qǐng)關(guān)注：
>>>>>>>>>Java提高篇（十三）——equals()
>>>>>>>>>Java提高篇（二三）——HashMap
>>>>>>>>>Java提高篇（二四）——HashSet
>>>>>>>>>Java提高篇（二五）——HashTable
掃碼關(guān)注鍍金池微信號(hào)
手機(jī)訂課，優(yōu)惠多多