一。概念
一種資料結構，用於存放資料，HashTable（雜湊表）=散列表
hash演算法基本原理：是把任意長度的輸入變成固定長度的輸出
雜湊函式：根據關鍵字設計的，有很多種函式，主要原理是根據陣列的大小進行求模運算，其陣列的大小一般設計為質數，因為需要均勻的散佈
二。構建方法
舉例：上學每個人都有學號，學號對應名字
key value
學號 姓名
1 ： 張三
2 ： 李四
3 ： 王五
需求：根據學號3迅速得到對應姓名
一般我們從頭遍歷到尾，先去查1然後2，最後3，如果有一萬個、那豈不是需要遍歷一萬次呢，此種做法非常慢，不可以取
陣列的結構可以使我們快速定位到3，陣列有下標、索引的概念，把學號當做索引，根據索引計算對應的元素記憶體在哪裡，
比如a陣列存以下資料
我們只需要看a［3］所對應的值是什麼，不需要看a［1］，a［2］，，這樣查詢非常塊，就算有一萬個元素，也可以一步到位，不需要從頭遍歷到尾
以上也為一種意義上的雜湊表，把key轉換為索引，陣列的元素存的是key對應的value的值
三。結構理解
像HashMap裡面有寫好雜湊表，當儲存一對key-value鍵值對元素的時候，把key拿出來，透過一個
hash函式
，找到一個記憶體地址，然後
key和value鍵值對Entry
放在對應的記憶體地址上
舉例：存學號1：張三
把1 拿出來透過hash函式，找到記憶體地址a ，記憶體地址a上對應著鍵值對 1：張三
1 a：1 張三
2 b：2 李四
3 c：3 王五
四。雜湊碰撞
1 現象
定義：兩個不同的key，透過同一個hash函式，得到的相同的記憶體地址，此種情況為雜湊碰撞
舉例：
key 1透過hash函式找到記憶體地址a，
key 2透過hash函式找到記憶體地址b
key 3透過hash函式找到記憶體地址c
此時有資料 4：趙六，拿key 4 透過hash函式算的記憶體地址也是c，但此時記憶體地址c已經儲存了元素，此種現象為雜湊碰撞O（K），k為碰撞的元素個數
2 連結串列式解決方案
連結串列，每一塊記憶體有一個空間引用儲存這下一塊記憶體的地址
每個雜湊表節點都有一個 next 指標， 多個雜湊表節點可以用 next 指標構成一個單向連結串列， 被分配到同一個索引上的多個節點可以用這個單向連結串列連線起來，這就解決了鍵衝突的問題，此種方案叫連結串列式解決方案。
3 開放地址解決方案
思想：與連結串列式解決方案相比，此種方案主要區別是不用next指標，把其它下標的位置都對外開放
3.1 線性探測法
tips：該方法不是很好，很容易把數字聚集到一個地方，查詢容易浪費效能，執行很多次
如果遇到衝突，就往下一個地址尋找空位，新位置=原下標位置+i （i是查詢的次數）
如圖：以下關鍵字2，38，28，4，12存入理解
當存入關鍵字2時
hash（2）=2，此時陣列下標的位置有元素，已被佔用，就往下找，陣列下標3的位置為空，因此關鍵字2存在陣列下標為3的位置
當存入關鍵字38時
hash（38）=12，陣列下標12的位置沒有元素，可直接將38存入
當存入關鍵字28時
hash（28）=2，下標2位置已被佔用，由於是線性探測法，可一直往下找到空的位置，所以關鍵字28放入下標為4的位置，同理，關鍵字4存入下標為5的位置
當存入關鍵字12時
hash（12）=12，位置已被佔用，就會轉回來從頭開始尋找，存入下標為0的位置
3.2 平方探測法
如果遇到衝突，就往（原始位置+i²）的位置尋找空位，i是查詢的次數
即新位置=原始位置+i²
1²，2²，3²，4²，5²，6² 距離越來越大比較分散，不扎堆，
解決了線性探測法扎堆的問題
也由關鍵字2，28，19，10 存入舉例說明
當存入關鍵字2時
hash（2）=2，下標為2的位置已被佔用，用平方探測法探測下一個位置是否為空，
第一次探測1²=1，是空的，可以直接放入
當存入關鍵字28時
hash（28）=2，下標為2位置已被佔用，平方探測法探測
第一次探測1²，下標2+1²=3的位置被關鍵字2佔用，
第二次探測2²，下標2+4=6的位置未被佔用，可直接放入
當存入關鍵字19時
hash（19）=6，下標為6的位置被佔用，平方探測法探測
第一次探測1²，下標6+1²=7的位置未被佔用，可直接存入
當存入關鍵字10時
hash（10）=10，下標為10的位置未本佔用，可直接存入
3.3 雙雜湊
要設定第二個hash函式，hash2（key）=R-（key mod R） 其中R 要取比陣列尺寸下的質數
如R=7： hash2（關鍵字）=7-（關鍵字 % 7） 也就是說二次hash的結果在1-7之間，不會等於0，（如果為0，則新位置=原位置，不合理）
如遇到衝突，新位置=原位置+i*hash2（key） 可以讓數字沒有太多規律的分配
由以下關鍵字舉例說明
當存入關鍵字15時
hash（15）=2，陣列下標為2的位置未被佔用，可直接存入
當存入關鍵字2時
hash（2）=2，陣列下標為2的位置被佔用，出現衝突，
需要計算hash2（2）=5，新位置下標=2+5=7，位置為空，可以直接放入
當存入關鍵字18時
hash（18）=5，陣列下標為5的位置為空，可直接放入
當存入關鍵字28時
hash（28）=2，產生衝突
需計算hash2（28）=7，儲存位置為7+2=9
4 一致性hash演算法
4.1 衍生場景
場景：分散式快取中，有三條伺服器S0，S1，S2 同時有3萬張圖片想均勻的快取到3臺伺服器
hash演算法：hash（圖片名稱）=圖片名稱 mod 機器數3 結果為0，1，2三種情況，正好與伺服器編號對應，快取對應的伺服器上
假如：圖片名稱為6，hash（6）=6%3=0，快取到伺服器S0上
缺陷：伺服器增加一臺，由3臺變成4臺，同一圖片名稱hash函式計算，除數由3變成4，餘數變化，即該快取的伺服器編號變化了
比如原先的圖片名稱6 ，hash（6）=6%4=2，程式會到伺服器S2上去尋找圖片，但實際上是儲存在伺服器S0上，讀取不到資料。由於伺服器數量發生變化，大量快取在同一時間失效，稱為快取雪崩此時，只有去後端伺服器上獲取資料，壓力都在後端伺服器，整個系統可能被壓垮，為避免此問題，需使用一致性hash演算法。
4.2 原理
有一個圓環（hash環），有2的32次方個點組成，還是有A，B，C三條伺服器
hash（A）=A%（2的32次方） 得出的整數代表伺服器A，hash環上必定有一點對應，伺服器A對映到hash環上，伺服器B、C一樣的方法。
同理，hash（a。jpg）%（2的32次方）也對映到hash環上
此時圖片和伺服器都被對映到hash環上
接下來怎麼確定圖片被快取到哪臺伺服器上呢？
從圖片的位置開始，順時針查詢，遇到的第一臺服務，為該圖片應該快取的伺服器
假設有a。jpg，b。jpg，c。jpg，由以下圖片和服務在hash環上的位置，由此可確定
a。jpg被快取到伺服器B上，
b。jpg被快取到伺服器C上
c。jpg被快取到伺服器A上
此時，加入增加一臺伺服器D，按一致性hash演算法規則，現將伺服器D對映到hash環上，此時一部分圖片延順時針方向遇到的伺服器由A變成伺服器D，增加一臺服務會導致一小部分圖片無法訪問，但大部分圖片順時針方向遇到的伺服器不變，可以正常訪問。
4.3 優點
快取伺服器的數量發生變化，只有一部分快取失效，快取依然能分擔整個系統的大部分壓力，不像hash演算法，不是所有的壓力同一時間集中在後端伺服器上
4.4 hash偏斜
以上hash演算法，一致認為三條伺服器均勻的對映到了hash環上，但在實際對映中，服務對映到hash環上很有可能是斜的，叫hash環偏斜
hash環偏斜時，大部分的快取物件很有可能快取到一臺伺服器上，導致快取不均勻，三臺伺服器沒有被平均使用。此時，如果快取較多的那臺伺服器出現故障，由於失效快取太多，在極端情況下，很有可能引起系統的故障，要想讓伺服器均勻分佈在伺服器上，伺服器儘量多，但實際伺服器數量固定，最好方案引入虛擬節點。
虛擬節點
：基於已有的物理節點，映射出很多虛擬節點。
比如伺服器A，映射出A1，A2，A3…An，n個虛擬節點，將這些虛擬節點加入hash環，引入後，hash化上的虛擬節點越多，伺服器節點越多，快取被均勻分佈的機率越大，這樣在一定程度上減小hash環傾斜帶來的影響。
快取讀寫時
：先找到快取對應的虛擬節點，在找自己的真實節點，在進行讀寫
5 公共溢位法
建立一個特殊儲存空間，專門放衝突的資料，此種方法使用於資料和衝突較少的情況下
