1.Hash函數(shù)(別名:散列函數(shù),又叫Hash算法)

Hash函數(shù)指將哈希表中元素的關(guān)鍵鍵值映射為元素存儲位置的函數(shù)。

把任意長度的輸入通過散列算法變換成固定長度的輸出，該輸出就是散列值。

散列值的空間通常遠(yuǎn)小于輸入的空間，不同的輸入可能會散列成相同的輸出，所以不可能從散列值來確定唯一的輸入值。因此，散列值是不可逆的，無法通過散列值確定輸入值

簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數(shù)。

常用的Hash算法

• UUID(Hash Function For Sequence of Unique Ids)

• MD5(Message-Digest Algorithm 5)

• SHA(Secure Hash Algorithm)

  Sha1哈希值長度為160位，Sha256為256位，更安全。

常用的Hash函數(shù)

1．直接尋址法。

取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為散列地址。即H(key)=key或H(key) = a·key + b，其中a和b為常數(shù)（這種散列函數(shù)叫做自身函數(shù)）

2．?dāng)?shù)字分析法。

分析一組數(shù)據(jù)，比如一組員工的出生年月日，這時我們發(fā)現(xiàn)出生年月日的前幾位數(shù)字大體相同，這樣的話，出現(xiàn)沖突的幾率就會很大，但是我們發(fā)現(xiàn)年月日的后幾位表示月份和具體日期的數(shù)字差別很大，如果用后面的數(shù)字來構(gòu)成散列地址，則沖突的幾率會明顯降低。因此數(shù)字分析法就是找出數(shù)字的規(guī)律，盡可能利用這些數(shù)據(jù)來構(gòu)造沖突幾率較低的散列地址。

3．平方取中法。

取關(guān)鍵字平方后的中間幾位作為散列地址。

4．折疊法。

將關(guān)鍵字分割成位數(shù)相同的幾部分，最后一部分位數(shù)可以不同，然后取這幾部分的疊加和（去除進(jìn)位）作為散列地址。

5．隨機(jī)數(shù)法。

選擇一隨機(jī)函數(shù)，取關(guān)鍵字作為隨機(jī)函數(shù)的種子生成隨機(jī)值作為散列地址，通常用于關(guān)鍵字長度不同的場合。

6．除留余數(shù)法。

取關(guān)鍵字被某個不大于散列表表長m的數(shù)p除后所得的余數(shù)為散列地址。即 H(key) = key MOD p,p<=m。不僅可以對關(guān)鍵字直接取模，也可在折疊、平方取中等運算之后取模。對p的選擇很重要，一般取素數(shù)或m，若p選的不好，容易產(chǎn)生碰撞。

著名的ELFhash算法

2.Hash表(別名: 散列表)

散列表（Hash table，也叫哈希表），是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。

3.Hash 沖突

所謂 hash 沖突，是由于哈希算法被計算的數(shù)據(jù)是無限的，而計算后的結(jié)果范圍有限，所以總會存在不同的數(shù)據(jù)經(jīng)過計算后得到的值相同，這就是哈希沖突。

無論哈希函數(shù)設(shè)計有多么精細(xì)，都會產(chǎn)生沖突現(xiàn)象，也就是2個關(guān)鍵字(key)處理函數(shù)f(key)的結(jié)果hashValue映射在了同一位置上，因此，有一些方法可以避免沖突。

4.解決 hash 沖突的方法

1. 開放定址法，也稱為線性探測法

就是從發(fā)生沖突的那個位置開始，按照一定的次序從 hash 表中找到一個空閑的位置，然后把發(fā)生沖突的元素存入到這個空閑位置中。ThreadLocal 就用到了線性探測法來解決 hash 沖突的。

向這樣一種情況（如圖），在 hash 表索引 1 的位置存了一個 key=name，當(dāng)再次添加
key=hobby 時，hash 計算得到的索引也是 1，這個就是 hash 沖突。而開放定址法，
就是按順序向前找到一個空閑的位置來存儲沖突的 key。

2. 鏈?zhǔn)綄ぶ贩?/p>

這是一種非常常見的方法，簡單理解就是把存在 hash 沖突
的 key，以單向鏈表的方式來存儲，比如 HashMap 就是采用鏈?zhǔn)綄ぶ贩?br>來實現(xiàn)的。

向這樣一種情況（如圖），存在沖突的 key 直接以單向鏈表的方式進(jìn)行存儲。

3. 多hash法

就是當(dāng)通過某個 hash 函數(shù)計算的 key 存在沖突時，再用另外一個 hash 函數(shù)對這個 key 做 hash，一直運算直到不再產(chǎn)生沖突。這種方式會增加計算時間，性能影響較大。

4. 建立公共溢出區(qū)

就是把 hash 表分為基本表和溢出表兩個部分，凡事存在沖突的元素，一律放入到溢出表中。

【注意】HashMap 在 JDK1.8 版本中，通過鏈?zhǔn)綄ぶ贩?紅黑樹的方式來解決 hash 沖突問題，其中紅黑樹是為了優(yōu)化 Hash 表鏈表過長導(dǎo)致時間復(fù)雜度增加的問題。當(dāng)鏈表長度大于 8 并且 hash 表的容量大于 64 的時候，再向鏈表中添加元素就會觸發(fā)轉(zhuǎn)化。

【參考資料】

https://baike.baidu.com/item/Hash/390310
https://baike.baidu.com/item/%E5%93%88%E5%B8%8C%E5%87%BD%E6%95%B0?fromModule=lemma_search-box
https://cloud.tencent.com/developer/article/2281026
https://baijiahao.baidu.com/s?id=1767196288371128445&wfr=spider&for=pc