哈希錶、哈希沖突

大家好，又見面了，我是你們的朋友全棧君。

哈希錶 1.哈希錶是一種以鍵值key存儲數據value的結構，以key作為標識值存儲value值；只要輸入待查找的key，即可獲取其對應的value值。當按照鍵值查詢元素時，使用相同的hash函數將key轉換為數組下標，從數組中按照下標對應的比特置獲取數據。它實際上是數組的一種擴展，數組+鏈錶+紅黑樹。 2.哈希錶的設計 哈希函數的設計首先不能過於複雜，複雜的哈希函數會間接的影響hash錶的性能；其次要求哈希值應該盡可能隨機且均勻分布，避免或者减少哈希沖突的數量，使每個桶中存儲的數據比較平均。

常規的設計方法有數據分析法，選擇數據的業務特征提取部分數據進行計算，然後得到結果再與哈希錶數組的長度求餘後最為哈希值。另外還有直接尋址法、平方取中法、折疊法和隨機數法等。

負載因子（加載因子）：减少鏈錶長度 低效擴容：乘以2進行擴容 加載因子越大，哈希錶中存儲的元素越多，空閑的比特置就越少，哈希沖突的概率就越大，插入、删除和查找數據時的性能就隨之降低。 應該避免低效擴容，因為極個別情况插入速度非常慢，會導致用戶崩潰。 哈希函數 1.哈希函數計算達到的哈希值應該是一個非負整數 2.如果key1==key2，那麼hash(key1)==hash(key2) 3.即使兩個key的hash值相等，但是有可能key值不相等 4.應用場景：安全加密、唯一標識、數據校驗、負載均衡、數據分片和分布式存儲等 哈希沖突 由於映射的範圍限制，key取值的可能性大於映射範圍，出現兩個不同的key映射到同一個比特置

解决哈希沖突的常見方法有開放地址法和鏈錶法。 開放地址法：一旦出現hash值沖突則通過重新探測新比特置的方法來解决沖突。對於線性探測法當哈希錶中存儲的元素越多時，哈希沖突的概率越高，極端情况下需要探測整個哈希錶，時間複雜度為O(n)。 鏈錶法：鏈地址法，在具體的應用中使用較多，在哈希錶中每個桶對應一個鏈錶，把哈希值相同的元素存放在相同桶比特置的對應鏈錶中，由於需要對比key值所以插入時間複雜度為O(k)，查找和删除時的時間複雜度與鏈錶的長度成正比O(k)，一般當k值不是很大時可以粗略的認為O(1)。需要盡量减少鏈錶長度，可以引入一個參數：負載因子或者稱為加載因子。負載因子用於間接的限定鏈錶的長度，如果值越大則允許的鏈錶長度越大，哈希錶的性能越差，但是加載因子越小空間浪費越嚴重。

HashMap采用的是鏈錶法解决hash沖突，ThreadLocalMap通過基於線性檢測的開放尋址法解决沖突。

開放尋址法數據存儲在數組中，可以有效地利用CPU緩存加快查詢速度，不會涉及鏈錶和指針的問題。當加載因子較大時會導致大量的探測行為操作，性能會急劇下降，同時删除數據也很麻煩，而且比鏈錶法需要占用更多的存儲空間。數據量比較小、負載因子小的時候適合開放地址法。 鏈錶法數據存儲在鏈錶中，對內存的利用率比開發地址法高一些，可以容忍比較大的裝載因子，由於節點中需要存儲next指針，會消耗額外的內存空間【有效載荷問題】。實際上如果考慮鏈錶長度變長的問題，可以考慮引入紅黑樹，以避免惡意的將數據存儲在一個桶中的哈希碰撞攻擊問題。

發布者：全棧程序員棧長，轉載請注明出處：https://javaforall.cn/151682.html原文鏈接：https://javaforall.cn