引用緻謝：https://zhuanlan.zhihu.com/p/78107140
https://cloud.tencent.com/developer/news/321607
一、基本概念
一般翻譯做“散列”，也有直接音譯為“哈希”的，就是把任意長度的輸入（又叫做預映射， pre-image），通過雜湊演算法，變換成固定長度的輸出，該輸出就是散列值。
這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小于輸入的空間，不同的輸入可能會散列成相同的輸出，是以不可能從散列值來唯一的确定輸入值。簡單的說就是一種将任意長度的消息壓縮到某一固定長度的消息摘要的函數
是以說了這麼多，到底什麼是Hash呢
這麼在網上看到了一個說明，很通俗，這裡引用說明：
你很想學太極拳，聽說學校有個叫張三豐的人打得特别好，于是你到學校學生處找人，
學生處的從業人員可能會拿出學生名單，一個一個的查找，最終告訴你，學校沒這個人，
并說張三豐幾百年前就已經在武當山作古了。
可如果你找對了人，比如在操場上找那些愛運動的同學，人家會告訴你，"哦，你找張三豐呀，
有有有，我帶你去。于是他把你帶到了體育館内，并告訴你，那個教大家打太極的小夥子就是張三豐'，
原來"張三豐.是因為他太極拳打得好而得到的外号。學生處的老師找張三豐，那就是順序表查找，
依賴的是姓名關鍵字的比較。而通過愛好運動的同學詢問時，沒有周遊，沒有比較，
就憑他們"欲找太極'張三豐'，必在體育館當中"的經驗，直接告訴你位置。 HASH主要用于資訊安全領域中加密算法，它把一些不同長度的資訊轉化成雜亂的128位的編碼,這些編碼值叫做HASH值. 也可以說，通俗的說hash就是找到一種資料内容和資料存放位址之間的映射關系。
hashCode
1、hashCode的存在主要是用于查找的快捷性，如Hashtable，HashMap等，hashCode是用來在散列存儲結構中确定對象的存儲位址的；
2、如果兩個對象相同，就是适用于equals(java.lang.Object) 方法，那麼這兩個對象的hashCode一定要相同；
3、如果對象的equals方法被重寫，那麼對象的hashCode也盡量重寫，并且産生hashCode使用的對象，一定要和equals方法中使用的一緻，否則就會違反上面提到的第2點；
4、兩個對象的hashCode相同，并不一定表示兩個對象就相同，也就是不一定适用于equals(java.lang.Object) 方法，隻能夠說明這兩個對象在散列存儲結構中，如Hashtable，他們“存放在同一個籃子裡”。
再歸納一下就是hashCode是用于查找使用的，而equals是用于比較兩個對象的是否相等的。以下這段話是從别人文章回複拷貝過來的：
舉例說說
1.hashcode是用來查找的，如果你學過資料結構就應該知道，在查找和排序這一章有
例如記憶體中有這樣的位置
0 1 2 3 4 5 6 7
而我有個類，這個類有個字段叫ID,我要把這個類存放在以上8個位置之一，如果不用hashcode而任意存放，那麼當查找時就需要到這八個位置裡挨個去找，或者用二分法一類的算法。
但如果用hashcode那就會使效率提高很多。
我們這個類中有個字段叫ID,那麼我們就定義我們的hashcode為ID％8，然後把我們的類存放在取得得餘數那個位置。比如我們的ID為9，9除8的餘數為1，那麼我們就把該類存在1這個位置，如果ID是13，求得的餘數是5，那麼我們就把該類放在5這個位置。這樣，以後在查找該類時就可以通過ID除 8求餘數直接找到存放的位置了。
2.但是如果兩個類有相同的hashcode怎麼辦那（我們假設上面的類的ID不是唯一的），例如9除以8和17除以8的餘數都是1，那麼這是不是合法的，回答是：可以這樣。那麼如何判斷呢？在這個時候就需要定義 equals了。
也就是說，我們先通過 hashcode來判斷兩個類是否存放某個桶裡，但這個桶裡可能有很多類，那麼我們就需要再通過 equals 來在這個桶裡找到我們要的類。
那麼。重寫了equals()，為什麼還要重寫hashCode()呢？
想想，你要在一個桶裡找東西，你必須先要找到這個桶啊，你不通過重寫hashcode()來找到桶，光重寫equals()有什麼用啊 JDK中String.hashCode方法：
二、hashCode在Java中的應用
在上面我們提到過，hash函數算法會有一定的沖突情況，比如在字元串的hashCode計算過程中，會出現兩個不同的字元串但hashCode一樣的情況，例如：
除了上述兩種情況，還有很多沖突的案例，大家可以寫代碼嘗試一下。
那問題來了，既然hashCode并不能完全表示唯一性，那Java中用什麼來比較兩個字元串，對象呢？hashCode還有什麼作用呢？
equals
在Java中，我們比較字元串，比較對象，用的方法常常是，我們摘錄equal重點部分
上面代碼就是使用最簡單的乘法疊代算法實作擷取唯一的hash值
我們看到，equals 對字元串做了嚴格字元級别比較，可以保證完全相同。
equals v.s. hashCode
由上面的分析，我們得出一下兩個結論：
1.相等的兩個對象他們的肯定相等，也就是用對比是絕對可靠的。
2.相等的兩個對象他們的不一定相等，也就是不是絕對可靠的。
但，如果所有的比較都使用equal去比較，顯然效率太低，是以解決方案是：
每當對比的時候，首先用hashCode去對比，如果hashCode不一樣，則表示兩個對象不相等。如果hashCode相同，此時再對比進行equal比較，如果equal相同就是真的相同。
HashSet, HashMap, HashTable
在Java 容器中（Set，Map，Table），經常會用到key值的檢索，是以提供了，，三種具體實作方案，利用上面我們重點标注的解決方案【先hashCode，後equal比較】，可以大大提高對比檢索效率。
三、哈希表
1.hash表的特性
Hash 表是使用 O(1) 時間進行資料的插入删除和查找，但是 hash 表不保證表中資料的有序性，這樣在 hash 表中查找最大資料或者最小資料的時間是 O(N) 。
2.尋址和 hash 函數
理想狀态下 hash 足夠大，每一資料儲存在一個 hash 存儲單元内，這樣對于插入删除和查找某一個資料就可以直接得到。但是現實情況下 hash 表不可能無限大，而且理論上儲存的資料的個數是沒有限制的，這樣儲存的資料的數量就遠遠大于 hash 表的存儲單元的數量。
為了實作在 O(1) 内對資料進行插入删除和查找，就必須将一個資料映射到 hash 表中的固定位置，這個映射函數就是 hash 函數。 Hash 函數通過對資料進行計算得到一個在 hash 表中的位置位址。
要選擇較好的 hash 函數，以及 hash 表存儲單元的數量，這樣才能使儲存在 hash 表中的資料均勻分布。理想狀态不太可能實作，由于存儲的資料數量遠遠大于 hash 表存儲單元的數量，是以再好的 hash 函數也可能使不同的資料得到相同的映射位置，這就造成了沖突。但是好的 hash 函數可以将這種沖突降到最低。
3.分離連結
解決這種沖突的第一種方法是借助連結清單來實作，就是将資料實際存放在與 hash 表存儲單元相連結的連結清單中，而不是 hash 的存儲單元中。
4.開放位址
使用開放位址方法解決沖突的時候，資料仍然儲存在 hash 表的存儲單元中，但是當沖突發生的時候，要再次計算新的位址。
常用的開放位址法是線性探查，就是當對一個資料進行插入删除或者查找的時候，通過 hash 函數計算，發現這個位置不是要找的資料，這時候就檢查下一個存儲單元，一直找到要操作的資料為止。
除了線性探查外還有二次探查，再 hash 等等方法，都是當一次計算得到的位置不是要找到的資料的時候，怎樣再次确定新的位置。
5.完全 hash 表
采用分離連結清單的方式解決沖突的時候，當多個資料被映射到一個位址的時候，它們就形成了一個連結清單，要操作這其中的一個資料，那麼就必須在這個連結清單中進行操作。如果 hash 函數選擇的好的話，連結清單會很短，這樣的操作近似 O(1) ，但并不是精确的等于 O(1) ，它與連結清單的長度有關。對于資料的通路的最壞情況的通路也是 O(1) 的 hash 叫做完全 hash 表。
這樣的 hash 表是一個兩級的 hash 表，第一級的 hash 與使用分離連結方法的 hash 一樣，但是 hash 存儲單元中指向的不是一個連結清單，而是另一個 hash 表。