淺談原理–hashCode方法
- 2019 年 10 月 28 日
- 筆記
我們時常會判斷一個元素是否相等重複，可以用equals方法。
每增加一個元素，我們就可以通過equals方法判斷集合中的每一個元素是否重複，但是如果集合中有10000個元素了，我們每添加一個元素的時候，就需要進行10000此的equals方法的調用，顯示效率非常的低下了。
於是基於這種問題，java集合的設計者採用了哈希表來實現。
哈希表也稱為散列算法，是依據數據特定算法產生的結果直接指定到一塊地址上，這個結果由hashCode方法產生。
這樣一來，當集合每添加一個新的元素的時候，就可以通過hashCode方法直接定位到該存放的物理位置上，而不需要大量的equals板的比較。
上面說到了hashCode方法，它是Object類中的一個被native修飾的方法，
那麼也就是說，我們每個對象都會繼承了這個方法，我們也就可以重寫它了
Object類的hashCode方法代碼：
public native int hashCode();
hashCode的比較方式
比如下方是在用HashSet存值
- 計算出來的位置上，如果這個位置上沒有元素，它就可以直接存儲在這個位置上了，不用進行任何的比較
- 如果這個位置有元素了，就調用它的（這個對象）equals方法與新的元素進行比較，相同的話就不存了
- 如果equals方法比較後，不相同，也就是放生了hashKey相同，導致衝突的情況。那麼就在這個hashKey的地方產生一個鏈表，將所有產生相同的hashKey的對象添加到這個鏈表上，串在一起（很少會出現）。這樣一來實際上我們調用equals方法的幾率就大大降低了。
下面以簡單的圖來表示
這裡有A B C D四個對象，分別通過hashCode方法產生了3個值
注意A和B對象調用hashCode產生的值是相同的，即 A.hashCode = B.hashCode()= 0x001
發生了哈希衝突，這時候由於最先插入了A，在插入B的時候，我們發現B要插入A的位置，而A已經插入，也就是這個位置已經有對象了。
這個時候就通過調用equals方法判斷A和B是否相同，如果相同就不插入B，如果不同則將B插入到A後面的位置。
所以對於equals方法和hashCode方法有如下的要求：
一、hashCode要求
- 在程序運行期間，只要對象（字段）變化不會影響到equals方法的決策結果，那麼在這個期間，無論調用多少次hashCode，都必須返回相同的散列碼的hashCode
- 通過equals調用返回true的2個對象的hashCode一定相同
- 通過equals返回false的2個對象的hashCode不需要不同，也就是允許hashCode相同。
因此得到以下結論
- 兩個對象相等，其hashCode一定相同
- 兩個對象不相等，其hashCode可能相等
- hashCode相等的兩個對象，不一定相同
- hashCode不相等的兩個對象，一定不同
可能會有人疑問，對於不能重複的集合，為什麼不直接通過 hashCode 對於每個元素都產生唯一的值，如果重複就是相同的值，這樣不就不需要調用 equals 方法來判斷是否相同了嗎？
實際上對於元素不是很多的情況下，直接通過 hashCode 產生唯一的索引值，通過這個索引值能直接找到元素，而且還能判斷是否相同。比如數據庫存儲的數據，ID 是有序排列的，我們能通過 ID 直接找到某個元素，如果新插入的元素 ID 已經有了，那就表示是重複數據，這是很完美的辦法。但現實是存儲的元素很難有這樣的 ID 關鍵字，也就很難這種實現 hashCode 的唯一算法，再者就算能實現，但是產生的 hashCode 碼是非常大的，這會大的超過 Java 所能表示的範圍（因為返回值是int類型，大小只能是232)，很占內存空間，所以也是不予考慮的。
二、重寫hashCode
我們應該注意：
- 不同對象的hashCode碼應該盡量不同，避免hash衝突，也就是算法獲得元素要盡量均勻。
- hash值是一個int類型，在java中佔用4個位元組，也就是232 次方，要避免溢出
下面是String的hashCode實現
public int hashCode() { int h = hash; if (h == 0 && value.length > 0) { char val[] = value; for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h; }
ps：
對於Map集合，我們可以選擇Java中的基本類型，還有引用類型String作為key，因為它們都按照規範重寫了equals方法和hashCode方法。
但是如果我們自定義對象作為key，那麼一定要覆蓋equals方法和hahshCode方法，要不然會有未知的suprise等着你。
