細說Hash（哈希）

一. 散列函數（Hash function)

含義：

把任意長度的輸入，提取資料摘要，通過雜湊演算法轉換成固定長度的輸出。

特性：

1.散列的值不同，則輸入的内容必定不同。

2.散列的值相同，輸入的值不一定相同（存在哈希碰撞的情況）。

3.散列的值不可逆（無法通過散列的值推導出原輸入内容）

Hash算法：

Hash算法沒有固定的公式，隻要符合散列思想的算法都可以稱之為Hash算法。MD5 和 SHA-1 可以算是目前用途最廣泛的Hash算法了。

MD5被廣泛用于校驗資料完整性，如：當下載下傳完檔案後，可以生成一份MD5檔案和源檔案的MD5做對比，如果一樣的話，則視為檔案完整，否則，就可能因為下載下傳有缺失、資料被人修改過等導緻下載下傳的檔案和源檔案不一緻。

PS：小知識，即使是MD5也是會出現哈希碰撞的情況的，不過機率極低極低而且很難通過人為修改資料讓散列值一緻~ 是以基本還是可以認為MD5校驗是準确的。 如果需要極高準度，不希望有任何哈希碰撞的可能的話，可以對源檔案進行一次MD5得出散列值A，然後再對源檔案進行一次SHA-1得出散列值B，再把A和B連接配接起來再進行一次MD5，這樣通過結合MD5和SHA-1的方式來得出的校驗結果，應該是高度精準了~

二.哈希表（Hash table）

數組：讀資料速度很快，可增删資料效率卻很低。

連結清單：增删資料效率很高，可讀資料的速度就很慢。

哈希表：我認為是集數組和連結清單的優點于一身，讀寫都能有較高的效率。

哈希表的工作流程：

1.使用者輸入一組鍵值對{key, value}資料。

2.使用hash函數對使用者輸入的key進行處理F(key)。

3.通過F(key)的處理結果直接得到對應存儲位置上的值。PS：不需要一個個周遊，直接得到值。

4.如果對應位置上的值為空，則直接放入value即可。

哈希碰撞：

上面工作流程的第四步，一旦對應位置上已經有值存在了，且該值對應的key 不等于目前使用者輸入的key，則發生了哈希碰撞。因為不同的輸入源（key）經過Hash函數處理後是有可能生成相同的散列值的。

處理哈希碰撞的方法有多種，此處拿hashmap的方案來作為解決方案（我認為他的方案挺好的~）。 我們儲存資料時可以以連結清單的形式來儲存資料，當發生哈希沖突時，隻需要周遊連結清單，看看有沒存在相同key的，有就覆寫，沒就在連結清單末端追加這組新的資料就可以了。 然後為了加快查找速度，當連結清單的數量大于8個時，我們可以把連結清單轉換成紅黑樹。

PS：即使發生哈希碰撞，最理想的情況依然是均勻分布在每個散列值下面，如果某幾個散列值發生碰撞的次數過多，導緻分布不均，此時的哈希表效率就變低了，也不是我們想要的結果，可以考慮換一種雜湊演算法試試。