文章目錄
- 什么是哈希表
- 哈希表概念
- 哈希沖突
- 哈希沖突概念
- 解決沖突
- 閉散列
- 閉散列平均查找次數的問題
- 開散列/哈希桶
- 沖突嚴重時的解決辦法
- 避免沖突
- 哈希函式設計
- 常見的哈希函式
- 負載因子調節
什么是哈希表
先舉一個很常見的例子：
我們有一個衣柜
這是一個雜亂無章的衣柜，里面放了四季的衣服，每當要去找一件合適的衣服去穿的時候，要翻箱倒柜麻煩半天，為了解決這個問題，我們買了四個柜子，規定它們分別存放春夏秋冬四季的衣服：
從此之后找衣服就方便了很多，什么季節去哪個衣柜找就能找到合適的衣服，這個例子背后就是哈希表的原理，
哈希表概念
在順序結構以及平衡樹中，元素關鍵碼與其存盤位置之間沒有對應的關系，因此在查找一個元素時，必須要經過關鍵碼的多次比較，順序查找的時間復雜度為o(N)，平衡樹中為樹的高度，即O(log2N)，搜索的效率取決于搜索程序中元素的比較次數，
我們理想的搜索方法是可以不經過任何比較，一次直接從表中得到要搜索的元素，
如果構造一種存盤結構，通過某種函式使得元素的存盤位置與它的關鍵碼之間能夠建立一一對應的關系，那么在查找時通過該函式可以很快找到該元素，
當向該結構中：
- 插入元素
根據待插入元素的關鍵碼，以此函式計算出該元素的存盤位置并按此位置進行處存放 - 搜索元素
對元素的關鍵碼進行同樣的計算，把求得的函式值當做元素的存盤位置，在結構中按此位置取元素比較，若關鍵碼相等，則搜索成功
上述方法就是哈希（散列）方法，哈希方法中使用的轉換函式稱為哈希（散列）函式，構造出來的結構稱為韓系表（Hash Table）或者稱為散串列，
舉個例子：
資料集合：{ 1, 7, 6, 5, 9 }
哈希函式設定為：hash(key) = key % capacity；capacity為存盤元素底層空間總大小
用該方法進行搜索不必進行多次關鍵碼的比較，因此搜索的速度比較快，
可此時出現了這樣一個問題，繼續向上面這個集合插入元素44，會出現什么問題？
很明顯[4]號為已經有4了，此時遇到的這個問題叫做哈希沖突，
哈希沖突
哈希沖突概念
不同的關鍵字，通過相同的哈希函式計算出相同的哈希地址，這種現象稱為哈希沖突或者哈希碰撞，
遇到沖突當然就是要解決沖突了，
解決沖突
解決哈希沖突的兩種常見方法是：開散列和閉散列，
閉散列
閉散列：也叫開放定址法，當發生哈希沖突是，如果哈希表未被裝滿，說明在哈希表中必然還有空位置，那么可以吧Key存放到沖突位置中的“下一個”空位置中去，那么如何尋找下一個空位置呢？常見的有以下兩種解決方法：
-
線性探測
比如上面的場景，現在需要插入元素44時，先通過哈希函式計算哈希地址，下標為4，因此44理論上應該插在該位置，但是該位置已經放了值為4的元素，即發生哈希沖突，線性探測法就是從發生沖突的位置開始，依次向后探測，直到找到下一個空位置為止，像上面例子44最后就被插到下標為8的位置：
-
二次探測
線性探測法的缺陷是產生沖突的資料堆積在一塊，當要插入數字8時，它不能插入到本來通過計算得到的下標8處，要一直尋找空位到下標0，當資料堆積的多的時候無疑增加了操作的時間，二次探測法為了緩解這個問題，找下一個空位的方法是：第一次往后找找12個，第二次找22個，第三次找32個，，，，，，
當然還有三次探測法，四次探測法等等，
閉散列平均查找次數的問題
例題：
關鍵字集合放入到哈希表中：
- 平均成功查找次數：
成功查找次數就是對于一個關鍵字要比較幾次才能找到他，比如要找19，哈希地址為8，去下標8找19，第一次就找到了，1這就是19的成功查找次數，對于11，哈希地址為0，去下標0找沒有，1找沒有，2找沒有直到5才找到，那么一共找了6次才找到，6就是11的成功查找次數， 那么平均成功查找次數 = 成功查找總次數（每個關鍵字的平均查找次數加起來） / 關鍵字個數， - 平均失敗查找次數：
從下標0開始找一直沒找到就需要找10次到全陣列找完還沒找到，10就是下標0的失敗查找次數，從下標1開始找需要查找9次，，，，，平均失敗查找次數 = 所有下標失敗查找次數和 / 陣列長度，
開散列/哈希桶
開散列又叫鏈地址發，首先對關鍵碼集合用哈希函式計算地址，具有相同地址的關鍵碼歸于同一子集合，每一個子集合稱為一個桶，各個同種的元素通過一個單鏈表連接起來，各個鏈表的頭結點存盤在哈希表中：
從上圖中可以看出，開散列中每個桶中放的都是發生哈希沖突的元素，
開散列，可以認為是把一個在大集合中的搜索問題轉化為在小集合中搜索了，
沖突嚴重時的解決辦法
剛才我們提到了，哈希桶其實可以看做將大集合的搜索問題轉化為小集合的搜索問題了，那如果沖突嚴重，就意味著小集合的搜索性能也不佳時，這個時候我們就可以將小集合搜索問題繼續轉化：
- 每個桶的背后是另外一張哈希表、
- 每個桶的背后是一顆搜索樹，
雖然說遇到哈希沖突我們可以用各種辦法去盡量解決沖突，但是在沖突發生前我們能不能盡量避免沖突的發生呢？
答案是可以的：
避免沖突
首先，我們需要明確一點，由于我們哈希表底層陣列（順序結構）的容量往往是小于實際要存盤的關鍵字的范圍的，這就意味著沖突的發生是必然的，但我們能做的應該是盡量的降低沖突，有相面兩個大的思路去降低沖突的發發生：
哈希函式設計
引起哈希沖突的一個原因可能是：哈希函式設計不夠合理，
哈希函式設計原理：
- 哈希函式的定義域必須包括需要存盤的全部關鍵碼，而如果散串列允許有m個地址時，其值域必須在0到m - 1之間，
- 哈希函式計算出來的地址能均勻分布在整個空間中，
- 哈希函式應該比較簡單
常見的哈希函式
- 直接定制法
取關鍵字的某個線性函式為散列地址： Hash( Key ) = A * Key + B
優點：簡單、均勻
缺點：需要事先直到關鍵碼的分布情況
使用場景：適合查找比較小且連續的情況 - 除留余數法
設散串列中允許的地址數為m，取一個不大于m，但最接近或者等于m的質數p作為除數，按照哈希函式：Hash(key) = Key % p (p <= m)，將關鍵碼轉換成哈希地址，
哈希函式很多很多，這里就不做過渡到介紹了，
負載因子調節
哈希表的負載因子 = 填入表中的元素個數 / 散串列長度
哈希表的負載因子是哈希表裝滿程度的標志因子，由于表長是定值，負載因子和“填入表中的元素個數”成正比，所以負載因子越大，表明填入表中的元素越多，產生沖突的可能性就越大；反之，負載因子越小，表明填入表中的元素越少，長生沖突的可能性就越小，
對于開放定址法，負載因子是特別重要的因素，應嚴格限制在0.7 - 0.8以下，Java中將負載因子限制在0.75.超過此值將resize哈希表，即對底層順序結構擴容然后將舊表中的資料重新一一放入到新表中，
這是負載因子和沖突率的粗略關系：
所以當沖突率達到一個無法忍受的程度時，我們需要通過降低負載因子來變相的降低沖突率，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/299721.html
標籤：其他
上一篇：力扣刷題中最不想看到的！