溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要講解了“Hash沖突常用的解決方案有哪些”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“Hash沖突常用的解決方案有哪些”吧！
散列函數（英語：Hash function）又稱散列算法、哈希函數，是一種從任何一種數據中創建小的數字“指紋”的方法。散列函數把消息或數據壓縮成摘要，使得數據量變小，將數據的格式固定下來。該函數將數據打亂混合，重新創建一個叫做散列值（hash values，hash codes，hash sums，或hashes）的指紋。散列值通常用一個短的隨機字母和數字組成的字符串來代表。
哈希表就是一種以 鍵-值(key-indexed) 存儲數據的結構，我們只要輸入待查找的值即key，即可查找到其對應的值。
哈希的思路很簡單，如果所有的鍵都是整數，那么就可以使用一個簡單的無序數組來實現：將鍵作為索引，值即為其對應的值，這樣就可以快速訪問任意鍵的值。這是對于簡單的鍵的情況，我們將其擴展到可以處理更加復雜的類型的鍵。
Hash算法可以將一個數據轉換為一個標志，這個標志和源數據的每一個字節都有十分緊密的關系。Hash算法還具有一個特點，就是很難找到逆向規律。
Hash算法也被稱為散列算法，Hash算法雖然被稱為算法，但實際上它更像是一種思想。Hash算法沒有一個固定的公式，只要符合散列思想的算法都可以被稱為是Hash算法。
常見Hash算法介紹：
1）MD4
MD4（RFC 1320）是 MIT 的Ronald L. Rivest在 1990 年設計的，MD 是 Message Digest（消息摘要） 的縮寫。它適用在32位字長的處理器上用高速軟件實現——它是基于 32位操作數地位操作來實現的。
2）MD5
MD5（RFC 1321）是 Rivest 于1991年對MD4的改進版本。它對輸入仍以512位分組，其輸出是4個32位字的級聯，與 MD4 相同。MD5比MD4來得復雜，并且速度較之要慢一點，但更安全，在抗分析和抗差分方面表現更好。
3）SHA-1及其他
SHA1是由NIST NSA設計為同DSA一起使用的，它對長度小于264的輸入，產生長度為160bit的散列值，因此抗窮舉（brute-force）性更好。SHA-1 設計師基于和MD4相同原理，并且模仿了該算法。
所有散列函數都有如下一個基本特性：如果兩個散列值是不相同的（根據同一函數），那么這兩個散列值的原始輸入也是不相同的。這個特性是散列函數具有確定性的結果，具有這種性質的散列函數稱為單向散列函數。
散列表，它是基于快速存取的角度設計的，也是一種典型的“空間換時間”的做法。顧名思義，該數據結構可以理解為一個線性表，但是其中的元素不是緊密排列的，而是可能存在空隙。
比如我們存儲70個元素，但我們可能為這70個元素申請了100個元素的空間。70/100=0.7，這個數字稱為負載因子。
我們之所以這樣做，也是為了“快速存取”的目的。
我們基于一種結果盡可能隨機平均分布的固定函數H為每個元素安排存儲位置，這樣就可以避免遍歷性質的線性搜索，以達到快速存取。
這類似于70個人去一個有100個椅子的飯店吃飯。散列函數的計算結果是一個存儲單位地址，每個存儲單位稱為“桶”。設一個散列表有m個桶，則散列函數的值域應為［0，m-1］。
如果不同的輸入經哈希映射得到了同一個哈希值，就發生了"哈希碰撞"（collision）。
假設hash表的大小為11（即有11個槽），現在要把一串數據存到表里：1，2，3，4，5，6...
簡單計算一下：hash(1) = 5, 即數據1應該放在hash表的第5個槽里；hash(2)=1，所以數據2應該放在hash表的第1個槽里；hash(3)=1，也就是說，數據3也應該放在hash表的第1個槽里——于是就造成了碰撞（也稱為沖突）。
常用的Hash沖突解決方法有以下幾種：
這種方法也稱再散列法，其基本思想是：當關鍵字key的哈希地址p=H（key）出現沖突時，以p為基礎，產生另一個哈希地址p1，如果p1仍然沖突，再以p為基礎，產生另一個哈希地址p2，…，直到找出一個不沖突的哈希地址pi ，將相應元素存入其中。這種方法有一個通用的再散列函數形式：
Hi=（H（key）+di）% m i=1，2，…，n
其中H（key）為哈希函數，m 為表長，di稱為增量序列。增量序列的取值方式不同，相應的再散列方式也不同。主要有以下三種：
線性探測再散列
dii=1，2，3，…，m-1
這種方法的特點是：沖突發生時，順序查看表中下一單元，直到找出一個空單元或查遍全表。
二次探測再散列
di=12，-12，22，-22，…，k2，-k2 ( k<=m/2 )
這種方法的特點是：沖突發生時，在表的左右進行跳躍式探測，比較靈活。
偽隨機探測再散列
di=偽隨機數序列。
具體實現時，應建立一個偽隨機數發生器，（如i=(i+p) % m），并給定一個隨機數做起點。
舉個實際應用例子
例如，已知哈希表長度m=11，哈希函數為：
H（key）= key % 11
則H（47）=3，H（26）=4，H（60）=5，假設下一個關鍵字為69，則H（69）=3，與47沖突。
case1：如果用線性探測再散列處理沖突
下一個哈希地址為
H1=（3 + 1）% 11 = 4
仍然沖突，再找下一個哈希地址為
H2=（3 + 2）% 11 = 5
還是沖突，繼續找下一個哈希地址為
H3=（3 + 3）% 11 = 6
此時不再沖突，將69填入5號單元。
case2：二次探測再散列處理沖突
下一個哈希地址為：
H1=（3 + 12）% 11 = 4
仍然沖突，再找下一個哈希地址為
H2=（3 - 12）% 11 = 2
此時不再沖突，將69填入2號單元。
case3：用偽隨機探測再散列處理沖突
且偽隨機數序列為：2，5，9，……..，則下一個哈希地址為
H1=（3 + 2）% 11 = 5
仍然沖突，再找下一個哈希地址為
H2=（3 + 5）% 11 = 8
此時不再沖突，將69填入8號單元。
這種方法是同時構造多個不同的哈希函數：
Hi=RH1（key） i=1，2，…，k
當哈希地址Hi=RH1（key）發生沖突時，再計算Hi=RH2（key）……，直到沖突不再產生。這種方法不易產生聚集，但增加了計算時間。
這種方法的基本思想是將所有哈希地址為i的元素構成一個稱為同義詞鏈的單鏈表，并將單鏈表的頭指針存在哈希表的第i個單元中，因而查找、插入和刪除主要在同義詞鏈中進行。鏈地址法適用于經常進行插入和刪除的情況。
鏈地址法優缺點分析：
優點
1）拉鏈法處理沖突簡單，且無堆積現象，即非同義詞決不會發生沖突，因此平均查找長度較短；
2）由于拉鏈法中各鏈表上的結點空間是動態申請的，故它更適合于造表前無法確定表長的情況；
3）開放定址法為減少沖突，要求裝填因子α較小，故當結點規模較大時會浪費很多空間。而拉鏈法中可取α≥1，且結點較大時，拉鏈法中增加的指針域可忽略不計，因此節省空間；
4）在用拉鏈法構造的散列表中，刪除結點的操作易于實現。只要簡單地刪去鏈表上相應的結點即可。
而對開放地址法構造的散列表，空地址單元(即開放地址)都是查找失敗的條件，刪除結點不能簡單地將被刪結點的空間置為空，否則將截斷在它之后填入散列表的同義詞結點的查找路徑。只能在被刪結點上做刪除標記，而不能真正刪除結點。
缺點
拉鏈法的缺點是：
指針需要額外的空間，故當結點規模較小時，開放定址法較為節省空間，而若將節省的指針空間用來擴大散列表的規模，可使裝填因子變小，這又減少了開放定址法中的沖突，從而提高平均查找速度。
上面說到的md5就是其中的一個, 好像還有一個什么SHA, 不過我不知道, 也就不展開探討了.
md5可以將一個文件經過計算轉換成一個指定長度的字符串, 可以防止文件被篡改, 但是通過加密后的字符串很難逆向推出原文.
前面那個例子可以看到, 即使文件被修改了一點點, 也會導致計算后的值發生很大變化.
比如說, 現在有十萬個文件, 給你一個文件, 要你在這十萬個文件中查找是否存在. 一個很笨的辦法就是把每一文件都拿出來, 然后按照二進制串一一進行對比. 但是這個操作注定是比較費時的.
可以用哈希算法對文件進行計算, 然后比較哈希值是否相同. 因為存在哈希沖突的情況, 你可以在相同哈希值的文件再進行二進制串比較.
在哈希表中使用哈希函數已經并不陌生了, 在此不再贅述。
比如說, 現在又多臺服務器, 來了一個請求, 如何確定這個請求應該路由到哪個路由器呢?當然, 必須確保相同的請求經過路由到達同一個服務器. 一種辦法就是保存一張路由關系的表, 比如客戶端IP和服務器編號的映射, 但是如果客戶端很多, 勢必查找的時間會很長. 這時, 可以將客戶端的唯一標識信息(如:IP、username等)進行哈希計算, 然后與服務器個數取模, 得到的就是服務器的編號.
當我們有大量數據時, 一般會選擇將數據存儲到多個服務器, 為了提高讀取與寫入的速度嘛. 決定將文件存儲到哪臺服務器, 就可以通過哈希算法取模的操作來得到。
感謝各位的閱讀，以上就是“Hash沖突常用的解決方案有哪些”的內容了，經過本文的學習后，相信大家對Hash沖突常用的解決方案有哪些這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
