hashCode詳解_ZenDei技術網路在線

一、hashcode是什麼要理解hashcode首先要理解hash表這個概念 1. 哈希表 hash表也稱散列表（Hash table），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數 ...

一、hashcode是什麼

要理解hashcode首先要理解hash表這個概念

1. 哈希表

hash表也稱散列表（Hash table），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表。
給定表M，存在函數f(key)，對任意給定的關鍵字值key，代入函數後若能得到包含該關鍵字的記錄在表中的地址，則稱表M為哈希(Hash）表，函數f(key)為哈希(Hash) 函數。
簡單理解就是：在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關係f，使每個關鍵字和結構中一個唯一的存儲位置相對應。
具有快速查找和插入操作的優點

2. hashcode

hashcode 通過hash函數計算得到，hashcode就是在hash表中有對應的位置
每個對象都有hashcode，通過將對象的物理地址轉換為一個整數，將整數通過hash計算就可以得到hashcode

二、hashcode的作用

HashCode的存在主要是為了查找的快捷性，HashCode是用來在散列存儲結構中確定對象的存儲地址的

對於容器類設計基本上都會涉及到hashCode。在Java中也一樣，hashCode方法的主要作用是為了配合基於散列的集合一起正常運行，這樣的散列集合包括HashSet、HashMap以及HashTable。

在對集合進行插入操作時，集合內時是不允許存在重覆元素的，這樣就引發了一個問題

如何判別在集合中是否已經存在該對象了？

首先想到的方法就是調用equals()方法，這個方法確實可行。但是如果集合中已經存在大量的數據或者更多的數據，如果採用equals方法去逐一比較，效率必然是一個問題。此時hashCode方法的作用就體現出來了，當集合要添加新的對象時，先調用這個對象的hashCode方法，得到對應的hashcode值，實際上在HashMap的具體實現中會一個表保存已經存進去的對象的hashcode值，如果table中沒有該hashcode值，它就可以直接存進去，不用再進行任何比較了；如果存在該hashcode值，就調用它的equals方法與新元素進行比較，相同的話就不存了，不相同就散列其它的地址，所以這裡存在一個衝突解決的問題，這樣一來實際調用equals方法的次數就大大降低了。

這也就解釋了為什麼equals()相等，則hashCode()必須相等。如果兩個對象equals()相等，則它們在哈希表(如HashSet、HashMap等)中只應該出現一次；如果hashCode()不相等，那麼它們會被散列到哈希表的不同位置，哈希表中出現了不止一次。

所以說hashCode方法的存在是為了減少equals方法的調用次數，從而提高程式效率。

三、 hashCode()和equals()

Java的基類Object中的 equals()方法用於判斷兩個對象是否相等，hashCode()方法用於計算對象的哈希碼。equals()和hashCode()都不是final方法，都可以被重寫(overwrite)

1. equals方法

Object類中equals()方法實現如下

public boolean equals(Object obj) {
    return (this == obj);
}

通過該實現可以看出，Object類的實現採用了區分度最高的演算法，即只要兩個對象不是同一個對象，那麼equals()一定返回false。
雖然可以重寫equals()方法，但是有一些註意事項；JDK中說明瞭實現equals()方法應該遵守的約定
- 自反性：x.equals(x)必須返回true。
- 對稱性：x.equals(y)與y.equals(x)的返回值必須相等。
- 傳遞性：x.equals(y)為true，y.equals(z)也為true，那麼x.equals(z)必須為true。
- 一致性：如果對象x和y在equals()中使用的信息都沒有改變，那麼x.equals(y)值始終不變。
- 非null：x不是null，y為null，則x.equals(y)必須為false。

2. hashCode 方法

Object類中hashCode()方法的聲明如下：
```
public native int hashCode();
```
可以看出，hashCode()是一個native方法，而且返回值類型是整形；實際上，該native方法將對象在記憶體中的地址作為哈希碼返回，可以保證不同對象的返回值不同。
與equals()方法類似，hashCode()方法可以被重寫。JDK中對hashCode()方法的作用，以及實現時的註意事項做了說明：
- （1）hashCode()在哈希表中起作用，如java.util.HashMap。
- （2）如果對象在equals()中使用的信息都沒有改變，那麼hashCode()值始終不變。
- （3）如果兩個對象使用equals()方法判斷為相等，則hashCode()方法也應該相等。
- （4）如果兩個對象使用equals()方法判斷為不相等，則不要求hashCode()也必須不相等；但是開發人員應該認識到，不相等的對象產生不相同的hashCode可以提高哈希表的性能。

重寫hashcode()的原則
- （1）如果重寫了equals()方法，檢查條件“兩個對象使用equals()方法判斷為相等，則hashCode()方法也應該相等”是否成立，如果不成立，則重寫hashCode ()方法。
- （2）hashCode()方法不能太過簡單，否則哈希衝突過多。
- （3）hashCode()方法不能太過複雜，否則計算複雜度過高，影響性能

hashCode()重寫方法

《Effective Java》中提出了一種簡單通用的hashCode演算法：

初始化一個整形變數，為此變數賦予一個非零的常數值，比如int result = 17;

選取equals方法中用於比較的所有域（之所以只選擇equals()中使用的域，是為了保證上述原則的第1條），然後針對每個域的屬性進行計算：

(1) 如果是boolean值，則計算f ? 1:0
(2) 如果是bytecharshortint,則計算(int)f
(3) 如果是long值，則計算(int)(f ^ (f >>> 32))
(4) 如果是float值，則計算Float.floatToIntBits(f)
(5) 如果是double值，則計算Double.doubleToLongBits(f)，然後返回的結果是long,再用規則(3)去處理long,得到int
(6) 如果是對象應用，如果equals方法中採取遞歸調用的比較方式，那麼hashCode中同樣採取遞歸調用hashCode的方式。否則需要為這個域計算一個範式，比如當這個域的值為null的時候，那麼hashCode 值為0
(7) 如果是數組，那麼需要為每個元素當做單獨的域來處理。java.util.Arrays.hashCode方法包含了8種基本類型數組和引用數組的hashCode計算，演算法同上。

最後，把每個域的散列碼合併到對象的哈希碼中。

四、HashMap中的hash()函數

HashMap中並沒有直接使用KV中K原有的hash值; 在HashMap的put、get操作時也未直接使用K中原有的hash值，而使用了一個hash()方法。讓我們一起看一下這個方法

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

這段代碼類似作用是為了增加hashcode的隨機性
key.hashCode()的作用是返回鍵值key所屬類型自帶的hashcode，返回的類型是int，如果直接拿散列值作為下標訪問HashMap的主數組的話，考慮到int類型值的範圍[-2^31 , 2^31 -1]，雖然只要hash表映射比較鬆散的話，碰撞幾率很小，但是映射空間太大，記憶體放不下，所以先做對數組的長度取模運算，得到的餘數才能用來訪問數組下標。
hashMap源碼中模運算是在這個indexFor( )函數里完成的把散列值和數組長度-1做一個"與"操作
```
static int indexFor(int h, int length) { return h & (length-1);}
```
- 這也正好解釋了為什麼HashMap的數組長度要取2的整數冪。因為數組長度-1相當於一個“低位掩碼”。“與”操作的結果就是散列值的高位全部歸零，只保留低位值.以初始長度16為例，16-1=15。2進位表示是00000000 00000000 00001111。和某散列值做“與”操作如下，結果就是截取了最低的四位值。h & (length - 1) 和 h % length，它倆是等價不等效的，明顯位運算效率非常高。
- ```
  01111010 00111100 00100101
& 00000000 00000000 00001111
----------------------------------
  00000000 00000000 00000101
  //高位全部歸零，只保留末四位 
```
- but 只取後四位，即使散列值分佈再鬆散，碰撞幾率還是很大。更糟糕的是如果散列函數做的比較差吧，分佈上成個等差數列啥的，恰好使最後幾個低位呈現規律性重覆，就比較蛋疼。
- 這時候 “hash”函數作用就出來了
  - 右位移16位，正好是32bit的一半，高半區和低半區做異或，就是為了混合原始哈希碼的高位和低位，以此來加大低位的隨機性。而且混合後的低位摻雜了高位的部分特征，這樣高位的信息也被變相保留下來。
  - 設計者考慮到現在的hashCode分佈的已經很不錯了，而且當發生較大碰撞時也用樹形存儲降低了衝突。僅僅異或一下，少了系統的開銷，也不會造成因為高位沒有參與下標的計算(table長度比較小時)，從而引起的碰撞。
  - 根據研究結果顯示，當HashMap數組長度為512的時候，也就是用掩碼取低9位的時候，在沒有使用hash()的情況下，發生了103次碰撞，接近30%。而在使用了hash()之後只有92次碰撞。碰撞減少了將近10%。看來擾hash()函數在將降低碰撞上還是有功效的。
hashMap中 MAXIMUM_CAPACITY = 1 << 30;最大為2的30次方（超過這個值就將threshold修改為Integer.MAX_VALUE（此時表的大小已經是2的31次方了），表明不進行擴容了）