1.Hash函數(別名:散列函數,又叫Hash演算法) Hash函數指將哈希表中元素的關鍵鍵值映射為元素存儲位置的函數。 把任意長度的輸入通過散列演算法變換成固定長度的輸出，該輸出就是散列值。 散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，所以不可能從散列值來確定唯一的輸入值。因此 ...
1.Hash函數(別名:散列函數,又叫Hash演算法)
Hash函數指將哈希表中元素的關鍵鍵值映射為元素存儲位置的函數。
把任意長度的輸入通過散列演算法變換成固定長度的輸出，該輸出就是散列值。
散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，所以不可能從散列值來確定唯一的輸入值。因此，散列值是不可逆的，無法通過散列值確定輸入值
簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。
常用的Hash演算法
- UUID(Hash Function For Sequence of Unique Ids)
- MD5(Message-Digest Algorithm 5)
- SHA(Secure Hash Algorithm)
Sha1哈希值長度為160位，Sha256為256位，更安全。
常用的Hash函數
1．直接定址法。
取關鍵字或關鍵字的某個線性函數值為散列地址。即H(key)=key或H(key) = a·key + b，其中a和b為常數（這種散列函數叫做自身函數）
2．數字分析法。
分析一組數據，比如一組員工的出生年月日，這時我們發現出生年月日的前幾位數字大體相同，這樣的話，出現衝突的幾率就會很大，但是我們發現年月日的後幾位表示月份和具體日期的數字差別很大，如果用後面的數字來構成散列地址，則衝突的幾率會明顯降低。因此數字分析法就是找出數字的規律，儘可能利用這些數據來構造衝突幾率較低的散列地址。
3．平方取中法。
取關鍵字平方後的中間幾位作為散列地址。
4．摺疊法。
將關鍵字分割成位數相同的幾部分，最後一部分位數可以不同，然後取這幾部分的疊加和（去除進位）作為散列地址。
5．隨機數法。
選擇一隨機函數，取關鍵字作為隨機函數的種子生成隨機值作為散列地址，通常用於關鍵字長度不同的場合。
6．除留餘數法。
取關鍵字被某個不大於散列表表長m的數p除後所得的餘數為散列地址。即 H(key) = key MOD p,p<=m。不僅可以對關鍵字直接取模，也可在摺疊、平方取中等運算之後取模。對p的選擇很重要，一般取素數或m，若p選的不好，容易產生碰撞。
著名的ELFhash演算法
int ELFhash(char*key) { unsigned long h=0; while(*key) { h = (h << 4) + *key++; unsigned long g = h & 0xF0000000L; if(g) h ^= g >> 24; h &= ~g; } return h % MOD; }
2.Hash表(別名: 散列表)
散列表（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表。
3.Hash 衝突
所謂 hash 衝突，是由於哈希演算法被計算的數據是無限的，而計算後的結果範圍有限，所以總會存在不同的數據經過計算後得到的值相同，這就是哈希衝突。
無論哈希函數設計有多麼精細，都會產生衝突現象，也就是2個關鍵字(key)處理函數f(key)的結果hashValue映射在了同一位置上，因此，有一些方法可以避免衝突。
4.解決 hash 衝突的方法
- 開放定址法，也稱為線性探測法
就是從發生衝突的那個位置開始，按照一定的次序從 hash 表中找到一個空閑的位置，然後把發生衝突的元素存入到這個空閑位置中。ThreadLocal 就用到了線性探測法來解決 hash 衝突的。
向這樣一種情況（如圖），在 hash 表索引 1 的位置存了一個 key=name，當再次添加
key=hobby 時，hash 計算得到的索引也是 1，這個就是 hash 衝突。而開放定址法，
就是按順序向前找到一個空閑的位置來存儲衝突的 key。
- 鏈式定址法
這是一種非常常見的方法，簡單理解就是把存在 hash 衝突
的 key，以單向鏈表的方式來存儲，比如 HashMap 就是採用鏈式定址法
來實現的。
向這樣一種情況（如圖），存在衝突的 key 直接以單向鏈表的方式進行存儲。
- 多hash法
就是當通過某個 hash 函數計算的 key 存在衝突時，再用另外一個 hash 函數對這個 key 做 hash，一直運算直到不再產生衝突。這種方式會增加計算時間，性能影響較大。
- 建立公共溢出區
就是把 hash 表分為基本表和溢出表兩個部分，凡事存在衝突的元素，一律放入到溢出表中。
【註意】HashMap 在 JDK1.8 版本中，通過鏈式定址法+紅黑樹的方式來解決 hash 衝突問題，其中紅黑樹是為了優化 Hash 錶鏈表過長導致時間複雜度增加的問題。當鏈表長度大於 8 並且 hash 表的容量大於 64 的時候，再向鏈表中添加元素就會觸發轉化。
