hash沖突演算法

Ⅰ 哈希演算法從原理到實戰

引言 

       將任意長度的二進制字元串映射為定長二進制字元串的映射規則我們稱為散列（hash）演算法，又叫哈希（hash）演算法，而通過原始數據映射之後得到的二進制值稱為哈希值。哈希表（hash表）結構是哈希演算法的一種應用，也叫散列表。用的是數組支持按照下標隨機訪問數據的特性擴展、演化而來。可以說沒有數組就沒有散列表。

哈希演算法主要特點

        從哈希值不能反向推導原始數據，也叫單向哈希。

        對輸入數據敏感，哪怕只改了一個Bit，最後得到的哈希值也大不相同。

        散列沖突的概率要小。

        哈希演算法執行效率要高，散列結果要盡量均衡。

哈希演算法的核心應用

         安全加密 ：對於敏感數據比如密碼欄位進行MD5或SHA加密傳輸。

         唯一標識 ：比如圖片識別，可針對圖像二進制流進行摘要後MD5，得到的哈希值作為圖片唯一標識。

         散列函數 :是構造散列表的關鍵。它直接決定了散列沖突的概率和散列表的性質。不過相對哈希演算法的其他方面應用，散列函數對散列沖突要求較低，出現沖突時可以通過開放定址法或鏈表法解決沖突。對散列值是否能夠反向解密要求也不高。反而更加關注的是散列的均勻性，即是否散列值均勻落入槽中以及散列函數執行的快慢也會影響散列表性能。所以散列函數一般比較簡單，追求均勻和高效。

        *負載均衡 ：常用的負載均衡演算法有很多，比如輪詢、隨機、加權輪詢。如何實現一個會話粘滯的負載均衡演算法呢？可以通過哈希演算法，對客戶端IP地址或會話SessionID計算哈希值，將取得的哈希值與伺服器列表大小進行取模運算，最終得到應該被路由到的伺服器編號。這樣就可以把同一IP的客戶端請求發到同一個後端伺服器上。

        *數據分片 ：比如統計1T的日誌文件中「搜索關鍵詞」出現次數該如何解決？我們可以先對日誌進行分片，然後採用多機處理，來提高處理速度。從搜索的日誌中依次讀取搜索關鍵詞，並通過哈希函數計算哈希值，然後再跟n(機器數)取模，最終得到的值就是應該被分到的機器編號。這樣相同哈希值的關鍵詞就被分到同一台機器進行處理。每台機器分別計算關鍵詞出現的次數，再進行合並就是最終結果。這也是MapRece的基本思想。再比如圖片識別應用中給每個圖片的摘要信息取唯一標識然後構建散列表，如果圖庫中有大量圖片，單機的hash表會過大，超過單機內存容量。這時也可以使用分片思想，准備n台機器，每台機器負責散列表的一部分數據。每次從圖庫取一個圖片，計算唯一標識，然後與機器個數n求余取模，得到的值就是被分配到的機器編號，然後將這個唯一標識和圖片路徑發往對應機器構建散列表。當進行圖片查找時，使用相同的哈希函數對圖片摘要信息取唯一標識並對n求余取模操作後，得到的值k，就是當前圖片所存儲的機器編號，在該機器的散列表中查找該圖片即可。實際上海量數據的處理問題，都可以藉助這種數據分片思想，突破單機內存、CPU等資源限制。

        *分布式存儲 ：一致性哈希演算法解決緩存等分布式系統的擴容、縮容導致大量數據搬移難題。

         JDK集合工具實現 ：HashMap、 LinkedHashMap、ConcurrentHashMap、TreeMap等。Map實現類源碼分析，詳見  https://www.jianshu.com/p/602324fa59ac

總結

        本文從哈希演算法的原理及特點，總結了哈希演算法的常見應用場景。

        其中基於余數思想和同餘定理實現的哈希演算法（除留取余法），廣泛應用在分布式場景中（散列函數、數據分片、負載均衡）。由於組合數學中的「鴿巢」原理，理論上不存在完全沒有沖突的哈希演算法。（PS:「鴿巢」原理是指有限的槽位，放多於槽位數的鴿子時，勢必有不同的鴿子落在同一槽內，即沖突發生。同餘定理：如果a和b對x取余數操作時a%x = b%x，則a和b同餘）

        構造哈希函數的常規方法有：數據分析法、直接定址法、除留取余法、折疊法、隨機法、平方取中法等  。

        常規的解決哈希沖突方法有開放定址法（線性探測、再哈希）和鏈表法。JDK中的HashMap和LinkedHashMap均是採用鏈表法解決哈希沖突的。鏈表法適合大數據量的哈希沖突解決，可以使用動態數據結構（比如：跳錶、紅黑樹等）代替鏈表，防止鏈表時間復雜度過度退化導致性能下降；反之開放定址法適合少量數據的哈希沖突解決。

Ⅱ hash演算法是什麼

Hash，就是把任意長度的輸入（又叫做預此模映射，pre-image），通過散列演算法，變換成固定長度的輸出，該輸出就是散列值。

這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。

使用哈希查找有兩個步驟：

1、使用哈希函數將被查找的鍵轉換為數組的索引。在理想的情況下，不同的鍵會被轉換為不同的索引值，但是在有些情況下乎扒腔我們需要處理多個鍵被哈希到同一個索引值的情況。所以哈希查找的第二個步驟就是處理沖突。

2、處理哈希碰撞沖突。有很多處理哈希碰撞沖突的方法，本文後面會介歲衫紹拉鏈法和線性探測法。

Ⅲ 哈希值為什麼會沖突

1、哈希就是做一個映射,為的是查找快.沖突是zd因為映射畢竟是有一個范圍的,這個范圍可能會小於你原來的那個范圍,所以可能好多個值映射了之後成為一個值了.
舉例來說,可能希望查版找字元串比較快,你會用一種計算方法將一個字元串權映射為一個整數,而且要求這個數字在100以內.那麼如果處理了10000個字元串,他們映射的值肯定會沖突.

2、hash：hashing定義了一種百將字元組成的字元串轉換為固定長度度(一般是更短長度)的數值或索引值的方法，稱為問散列法，也叫哈希法。
沖突：兩個不同的關答鍵字，由於散列函數值相同，因而被內映射到同一表位置上。該容現象稱為沖突(collision)或碰撞。

3、哈希計算就是努力的把比較大的數據存放到相百對較小的空間中。
最常見的哈希演算法是取模法。
下面簡單講講取模法的計算過程。
比如：數組的長度是5。這時有度一個數據是6。那麼如何把這個
6存放到長度只有5的數組中呢。按照取模法，計算
6％5，結果是1，那麼就把6放到數組下標是1的位問置。那麼，7
就應該放到2這個位置。到此位置，哈希沖突還沒有出現。
這時，有個數據是11，按照取模法，11％5＝1，也等於1。那麼
原來數組下標是1的地方已經有數了答，是6。這時又計算出1這個
位置，那麼數組1這個位置，就回必須儲存兩個數了。這時，就叫
哈希答沖突。沖突之後就要按照順序來存放了。
如果數據的分布比較廣泛，而且儲存數據的數組長度比較大。
那麼哈希沖突就比較少。否則沖突是很高的。
具體的演算法你要參照更加專業的書籍。
希望對你有幫助。
出自：網路知道

Ⅳ hash演算法原理詳解

散列方法的主要思想是根據結點的關鍵碼值來確定其存儲地址：以關鍵碼值K為自變數，通過一定的函數關系h(K)(稱為散列函數)，計算出對應的函數值來，把這個值解釋為結點的存儲地址，將結點存入到此存儲單元中。檢索時，用同樣的方法計算地址，然後到相應的單元里去取要找的結點。通過散列方法可以對結點進行快速檢索。散列（hash，也稱「哈希」）是一種重要的存儲方式，也是一種常見的檢索方法。

按散列存儲方式構造的存儲結構稱為散列表（hash table）。散列表中的一個位置稱為槽(slot)。散列技術的核心是散列函數(hash function)。 對任意給定的動態查找表DL，如果選定了某個「理想的」散列函數h及相應的散列表HT，則對DL中的每個數據元素X。函數值h（X.key）就是X在散列表HT中的存儲位置。插入（或建表）時數據元素X將被安置在該位置上，並且檢索X時也到該位置上去查找。由散列函數決定的存儲位置稱為散列地址。 因此，散列的核心就是：由散列函數決定關鍵碼值(X.key)與散列地址h(X.key)之間的對應關系，通過這種關系來實現組織存儲並進行檢索。

一般情況下，散列表的存儲空間是一個一維數組HT[M]，散列地址是數組的下標。設計散列方法的目標，就是設計某個散列函數h，0<=h( K ) < M；對於關鍵碼值K，得到HT[i] = K。 在一般情況下，散列表的空間必須比結點的集合大，此時雖然浪費了一定的空間，但換取的是檢索效率。設散列表的空間大小為M，填入表中的結點數為N，則稱為散列表的負載因子（load factor，也有人翻譯為「裝填因子」）。建立散列表時，若關鍵碼與散列地址是一對一的關系，則在檢索時只需根據散列函數對給定值進行某種運算，即可得到待查結點的存儲位置。但是，散列函數可能對於不相等的關鍵碼計算出相同的散列地址，我旅做襪們稱該現象為沖突（collision），發生沖突的兩個關鍵碼稱為該散列函數的同義詞。在實際應用中，很少存在不產生沖突的散列函數，胡陸我們必須考慮在沖突發生時的處理辦法。

在以下的討論中，我們假設處理的是值為整型的關鍵碼，否則我們總可以建立一種關鍵碼與正整數之間的一一對應關系，從而把該關鍵碼的檢索轉化為對與其對應的正整數的檢索；同時，進一步假定散列函數的值落在0到M－1之間。散列函數的選取原則是：運算盡可能簡單；函數的值域必須在散列表的范圍內；盡可能使得結點均勻分布，也就是盡量讓不同的關鍵碼具有不同的散列函數值。需要考慮各種因素：關鍵碼長度、散列表大小、關鍵碼分布情況、記錄的檢索頻率等等。下面我們介紹幾種常用的散列函數。

顧名思義，除余法就是用關鍵碼x除以M（往往取散列表長度），並取余數作為散列地址。除余法幾乎是最簡單的散列方法，散列函數為： h(x) ＝ x mod M。

使用此方法拆激時，先讓關鍵碼key乘上一個常數A (0< A < 1)，提取乘積的小數部分。然後，再用整數n乘以這個值，對結果向下取整，把它做為散列的地址。散列函數為： hash ( key ) = _LOW( n × ( A × key % 1 ) )。 其中，「A × key % 1」表示取 A × key 小數部分，即： A × key % 1 = A × key - _LOW(A × key), 而_LOW(X)是表示對X取下整

由於整數相除的運行速度通常比相乘要慢，所以有意識地避免使用除余法運算可以提高散列演算法的運行時間。平方取中法的具體實現是：先通過求關鍵碼的平方值，從而擴大相近數的差別，然後根據表長度取中間的幾位數（往往取二進制的比特位）作為散列函數值。因為一個乘積的中間幾位數與乘數的每一數位都相關，所以由此產生的散列地址較為均勻。

假設關鍵字集合中的每個關鍵字都是由 s 位數字組成 (u1, u2, …, us)，分析關鍵字集中的全體，並從中提取分布均勻的若干位或它們的組合作為地址。數字分析法是取數據元素關鍵字中某些取值較均勻的數字位作為哈希地址的方法。即當關鍵字的位數很多時，可以通過對關鍵字的各位進行分析，丟掉分布不均勻的位，作為哈希值。它只適合於所有關鍵字值已知的情況。通過分析分布情況把關鍵字取值區間轉化為一個較小的關鍵字取值區間。

舉個例子：要構造一個數據元素個數n=80,哈希長度m=100的哈希表。不失一般性，我們這里只給出其中8個關鍵字進行分析，8個關鍵字如下所示：

K1=61317602 K2=61326875 K3=62739628 K4=61343634

K5=62706815 K6=62774638 K7=61381262 K8=61394220

分析上述8個關鍵字可知，關鍵字從左到右的第1、2、3、6位取值比較集中，不宜作為哈希地址，剩餘的第4、5、7、8位取值較均勻，可選取其中的兩位作為哈希地址。設選取最後兩位作為哈希地址，則這8個關鍵字的哈希地址分別為：2，75，28，34，15，38，62，20。

此法適於:能預先估計出全體關鍵字的每一位上各種數字出現的頻度。

將關鍵碼值看成另一種進制的數再轉換成原來進制的數，然後選其中幾位作為散列地址。

例Hash(80127429)=(80127429)13=8 137+0 136+1 135+2 134+7 133+4 132+2*131+9=(502432641)10如果取中間三位作為哈希值，得Hash（80127429）=432
為了獲得良好的哈希函數，可以將幾種方法聯合起來使用，比如先變基，再折疊或平方取中等等，只要散列均勻，就可以隨意拼湊。

有時關鍵碼所含的位數很多，採用平方取中法計算太復雜，則可將關鍵碼分割成位數相同的幾部分（最後一部分的位數可以不同），然後取這幾部分的疊加和（捨去進位）作為散列地址，這方法稱為折疊法。

分為：

盡管散列函數的目標是使得沖突最少，但實際上沖突是無法避免的。因此，我們必須研究沖突解決策略。沖突解決技術可以分為兩類：開散列方法( open hashing，也稱為拉鏈法，separate chaining )和閉散列方法( closed hashing，也稱為開地址方法，open addressing )。這兩種方法的不同之處在於：開散列法把發生沖突的關鍵碼存儲在散列表主表之外，而閉散列法把發生沖突的關鍵碼存儲在表中另一個槽內。

(1)拉鏈法

開散列方法的一種簡單形式是把散列表中的每個槽定義為一個鏈表的表頭。散列到一個特定槽的所有記錄都放到這個槽的鏈表中。圖9-5說明了一個開散列的散列表，這個表中每一個槽存儲一個記錄和一個指向鏈表其餘部分的指針。這7個數存儲在有11個槽的散列表中，使用的散列函數是h(K) = K mod 11。數的插入順序是77、7、110、95、14、75和62。有2個值散列到第0個槽，1個值散列到第3個槽，3個值散列到第7個槽，1個值散列到第9個槽。

閉散列方法把所有記錄直接存儲在散列表中。每個記錄關鍵碼key有一個由散列函數計算出來的基位置，即h(key)。如果要插入一個關鍵碼，而另一個記錄已經占據了R的基位置(發生碰撞)，那麼就把R存儲在表中的其它地址內，由沖突解決策略確定是哪個地址。

閉散列表解決沖突的基本思想是：當沖突發生時，使用某種方法為關鍵碼K生成一個散列地址序列d0，d1，d2，... di ，...dm-1。其中d0=h（K）稱為K的基地址地置( home position )；所有di(0< i< m)是後繼散列地址。當插入K時，若基地址上的結點已被別的數據元素佔用，則按上述地址序列依次探查，將找到的第一個開放的空閑位置di作為K的存儲位置；若所有後繼散列地址都不空閑，說明該閉散列表已滿，報告溢出。相應地，檢索K時，將按同值的後繼地址序列依次查找，檢索成功時返回該位置di ；如果沿著探查序列檢索時，遇到了開放的空閑地址，則說明表中沒有待查的關鍵碼。刪除K時，也按同值的後繼地址序列依次查找，查找到某個位置di具有該K值，則刪除該位置di上的數據元素（刪除操作實際上只是對該結點加以刪除標記）；如果遇到了開放的空閑地址，則說明表中沒有待刪除的關鍵碼。因此，對於閉散列表來說，構造後繼散列地址序列的方法，也就是處理沖突的方法。

形成探查的方法不同，所得到的解決沖突的方法也不同。下面是幾種常見的構造方法。

(1)線性探測法

將散列表看成是一個環形表，若在基地址d（即h(K)=d）發生沖突，則依次探查下述地址單元：d+1，d+2，......，M-1，0，1，......，d-1直到找到一個空閑地址或查找到關鍵碼為key的結點為止。當然，若沿著該探查序列檢索一遍之後，又回到了地址d，則無論是做插入操作還是做檢索操作，都意味著失敗。 用於簡單線性探查的探查函數是： p(K，i) = i

例9.7 已知一組關鍵碼為（26，36，41，38，44，15，68，12，06，51，25），散列表長度M= 15，用線性探查法解決沖突構造這組關鍵碼的散列表。 因為n=11，利用除余法構造散列函數，選取小於M的最大質數P=13，則散列函數為：h(key) = key%13。按順序插入各個結點： 26: h(26) = 0，36: h(36) = 10， 41: h(41) = 2，38: h(38) = 12， 44: h(44) = 5。 插入15時，其散列地址為2，由於2已被關鍵碼為41的元素佔用，故需進行探查。按順序探查法，顯然3為開放的空閑地址，故可將其放在3單元。類似地，68和12可分別放在4和13單元中.

(2)二次探查法

二次探查法的基本思想是：生成的後繼散列地址不是連續的，而是跳躍式的，以便為後續數據元素留下空間從而減少聚集。二次探查法的探查序列依次為：12，-12，22 ，-22，...等，也就是說，發生沖突時，將同義詞來回散列在第一個地址的兩端。求下一個開放地址的公式為：

(3)隨機探查法

理想的探查函數應當在探查序列中隨機地從未訪問過的槽中選擇下一個位置，即探查序列應當是散列表位置的一個隨機排列。但是，我們實際上不能隨機地從探查序列中選擇一個位置，因為在檢索關鍵碼的時候不能建立起同樣的探查序列。然而，我們可以做一些類似於偽隨機探查( pseudo-random probing )的事情。在偽隨機探查中，探查序列中的第i個槽是(h(K) + ri) mod M，其中ri是1到M - 1之間數的「隨機」數序列。所有插入和檢索都使用相同的「隨機」數。探查函數將是 p(K，i) = perm[i - 1]， 這里perm是一個長度為M - 1的數組，它包含值從1到M – 1的隨機序列。

例子：
例如，已知哈希表長度m=11，哈希函數為：H（key）= key % 11，則H（47）=3，H（26）=4，H（60）=5，假設下一個關鍵字為69，則H（69）=3，與47沖突。如果用線性探測再散列處理沖突，下一個哈希地址為H1=（3 + 1）% 11 = 4，仍然沖突，再找下一個哈希地址為H2=（3 + 2）% 11 = 5，還是沖突，繼續找下一個哈希地址為H3=（3 + 3）% 11 = 6，此時不再沖突，將69填入5號單元，參圖8.26 (a)。如果用二次探測再散列處理沖突，下一個哈希地址為H1=（3 + 12）% 11 = 4，仍然沖突，再找下一個哈希地址為H2=（3 - 12）% 11 = 2，此時不再沖突，將69填入2號單元，參圖8.26 (b)。如果用偽隨機探測再散列處理沖突，且偽隨機數序列為：2，5，9，……..，則下一個哈希地址為H1=（3 + 2）% 11 = 5，仍然沖突，再找下一個哈希地址為H2=（3 + 5）% 11 = 8，此時不再沖突，將69填入8號單元，參圖8.26 (c)。

(4)雙散列探查法

偽隨機探查和二次探查都能消除基本聚集——即基地址不同的關鍵碼，其探查序列的某些段重疊在一起——的問題。然而，如果兩個關鍵碼散列到同一個基地址，那麼採用這兩種方法還是得到同樣的探查序列，仍然會產生聚集。這是因為偽隨機探查和二次探查產生的探查序列只是基地址的函數，而不是原來關鍵碼值的函數。這個問題稱為二級聚集( secondary clustering )。

為了避免二級聚集，我們需要使得探查序列是原來關鍵碼值的函數，而不是基位置的函數。雙散列探查法利用第二個散列函數作為常數，每次跳過常數項，做線性探查。

Ⅳ 如何解決Hash中的沖突問題

1、開放定址法
用開放定址法解決沖突的做法是：當沖突發生時，使用某種探查(亦稱探測)技術在散列表中形成一個探查(測)序列。沿此序列逐個單元地查找，直到找到給定 的關鍵字，或者碰到一個開放的地址(即該地址單元為空)為止（若要插入，在探查到開放的地址，則可將待插入的新結點存人該地址單元）。查找時探查到開放的 地址則表明表中無待查的關鍵字，即查找失敗。注意：
①用開放定址法建立散列表時，建表前須將表中所有單元(更嚴格地說，是指單元中存儲的關鍵字)置空。
②空單元的表示與具體的應用相關。
按照形成探查序列的方法不同，可將開放定址法區分為線性探查法、線性補償探測法、隨機探測等。
（1）線性探查法(Linear Probing)
該方法的基本思想是：
將散列表T[0..m-1]看成是一個循環向量，若初始探查的地址為d(即h(key)=d)，則最長的探查序列為：
d，d+l，d+2，…，m-1，0，1，…，d-1
即:探查時從地址d開始，首先探查T[d]，然後依次探查T[d+1]，…，直到T[m-1]，此後又循環到T[0]，T[1]，…，直到探查到 T[d-1]為止。
探查過程終止於三種情況：
(1)若當前探查的單元為空，則表示查找失敗（若是插入則將key寫入其中）；
(2)若當前探查的單元中含有key，則查找成功，但對於插入意味著失敗；
(3)若探查到T[d-1]時仍未發現空單元也未找到key，則無論是查找還是插入均意味著失敗(此時表滿)。
利用開放地址法的一般形式，線性探查法的探查序列為：
hi=(h(key)+i)％m 0≤i≤m-1 //即di=i
用線性探測法處理沖突，思路清晰，演算法簡單，但存在下列缺點：
① 處理溢出需另編程序。一般可另外設立一個溢出表，專門用來存放上述哈希表中放不下的記錄。此溢出表最簡單的結構是順序表，查找方法可用順序查找。
② 按上述演算法建立起來的哈希表，刪除工作非常困難。假如要從哈希表 HT 中刪除一個記錄，按理應將這個記錄所在位置置為空，但我們不能這樣做，而只能標上已被刪除的標記，否則，將會影響以後的查找。
③ 線性探測法很容易產生堆聚現象。所謂堆聚現象，就是存入哈希表的記錄在表中連成一片。按照線性探測法處理沖突，如果生成哈希地址的連續序列愈長 ( 即不同關鍵字值的哈希地址相鄰在一起愈長 ) ，則當新的記錄加入該表時，與這個序列發生沖突的可能性愈大。因此，哈希地址的較長連續序列比較短連續序列生長得快，這就意味著，一旦出現堆聚 ( 伴隨著沖突 ) ，就將引起進一步的堆聚。
（2）線性補償探測法
線性補償探測法的基本思想是：
將線性探測的步長從 1 改為 Q ，即將上述演算法中的 j ＝ (j ＋ 1) % m 改為： j ＝ (j ＋ Q) % m ，而且要求 Q 與 m 是互質的，以便能探測到哈希表中的所有單元。
【例】 PDP-11 小型計算機中的匯編程序所用的符合表，就採用此方法來解決沖突，所用表長 m ＝ 1321 ，選用 Q ＝ 25 。 2、拉鏈法
（1）拉鏈法解決沖突的方法
拉鏈法解決沖突的做法是：將所有關鍵字為同義詞的結點鏈接在同一個單鏈表中。若選定的散列表長度為m，則可將散列表定義為一個由m個頭指針組成的指針數 組T[0..m-1]。凡是散列地址為i的結點，均插入到以T[i]為頭指針的單鏈表中。T中各分量的初值均應為空指針。在拉鏈法中，裝填因子α可以大於 1，但一般均取α≤1。
【例】設有 m ＝ 5 ， H(K) ＝ K mod 5 ，關鍵字值序例 5 ， 21 ， 17 ， 9 ， 15 ， 36 ， 41 ， 24 ，按外鏈地址法所建立的哈希表如下圖所示：

（2）拉鏈法的優點
與開放定址法相比，拉鏈法有如下幾個優點：
①拉鏈法處理沖突簡單，且無堆積現象，即非同義詞決不會發生沖突，因此平均查找長度較短；
②由於拉鏈法中各鏈表上的結點空間是動態申請的，故它更適合於造表前無法確定表長的情況；
③開放定址法為減少沖突，要求裝填因子α較小，故當結點規模較大時會浪費很多空間。而拉鏈法中可取α≥1，且結點較大時，拉鏈法中增加的指針域可忽略不計，因此節省空間；
④在用拉鏈法構造的散列表中，刪除結點的操作易於實現。只要簡單地刪去鏈表上相應的結點即可。而對開放地址法構造的散列表，刪除結點不能簡單地將被刪結 點的空間置為空，否則將截斷在它之後填人散列表的同義詞結點的查找路徑。這是因為各種開放地址法中，空地址單元(即開放地址)都是查找失敗的條件。因此在 用開放地址法處理沖突的散列表上執行刪除操作，只能在被刪結點上做刪除標記，而不能真正刪除結點。

（3）拉鏈法的缺點
拉鏈法的缺點是：指針需要額外的空間，故當結點規模較小時，開放定址法較為節省空間，而若將節省的指針空間用來擴大散列表的規模，可使裝填因子變小，這又減少了開放定址法中的沖突，從而提高平均查找速度。

Ⅵ 什麼是哈希沖突

哈希計算就是努力的把比較大的數據存放到相對較小的空間中。
最常見的哈希演算法是取模法。
下面簡單講講取模法的計算過程。
比如：數組的長度是5。這時有一個數據是6。那麼如何把這個
6存放到長度只有5的數組中呢。按照取模法，計算
6％5，結果是1，那麼就把6放到數組下標是1的位置。那麼，7
就應該放到2這個位置。到此位置，哈斯團碧沖突還沒有出悔或絕現。
這時，有個數據是11，按照取模法，11％5＝1，也等於1。那麼
原來數組下標是1的地方已經有數了，是6。這時又計算出1這個
位置，那麼數組1這個位置，就必須儲存兩個數了。這時，就叫
哈希沖突。沖突之後就要按照順序來存放了。
如果數據的分布比較廣泛，而且儲存數據的數組長度比較大。
那麼哈希沖突就比較少碧姿。否則沖突是很高的。
具體的演算法你要參照更加專業的書籍。
希望對你有幫助。

Ⅶ Hash沖突的解決方法

哈希非哈希區別在於關鍵字在表中位置和它之間是否存在一個確定關系，哈希存在，非哈希不存在。
hash就是散列，就是把任意長度的輸入，通過散列演算法，變成固定長度的輸出，輸出就是散列值，該轉換是壓縮轉換，散列值空間遠小於輸入的空間，不同的輸入可能會散列成相同的輸出。

Hash沖突，也就是經過一個函數結果作為地址去存放當前key value鍵值對(這個是hashmap存值方式)。
解決hash沖突發方法有
1）開放定址法，m為表長度，增量di有三種取法，線性探測再散列，平方探測再散列。
2）鏈地址法，就是key值取模再運算，java的HashMap就是這么實現的，在put()方法裡面。
3）重哈希法，在創建hashmap的時候一般默認初始化容量，創建的hash表是桶的數量，負載因子：map的size/初始化容量，當hash表中負載因子達到負載極限，hash表會自動成倍增加容量，並將原有的對象重新分配加入新的值，成為rehash，rehash非常影響性能，所以初始化容量要設置灶睜好，不能太過浪費空間，也不能過小造成rehash情況經常出現。
4）建立一個公共溢出區域，就是把沖突的都放在另一個地方，不在表裡面。

先看HashMap的數據結構，HashMap的底層主要是基於數組和鏈表來實現的，它之所以有相當快的查詢速度主要是因為它通過計算散列碼來決定存儲的位置，HashMap中主要是通過key的hashCode來計算hash值的，只要hashCode相同，出來的hash值一樣，不同對象出來的隱虛歲hash值一樣，出現所謂hash沖突，HashMap底層通過鏈表解決hash沖突的。
HashMap其實就是一個Entry數組（類似pair），Entry對象中包含了鏈和值，其中next也是一個Entry對象，它就是用來處理hash沖突的，形成一個鏈表。
在Java8之前，如果發生hash沖突往往是將該value直接鏈接到該位置的其他所有value的頭部，即相互沖突的所有value形成一個鏈表，因此，最壞情況HashMap的查找時間復雜度退化到O(n)，在Java8中做了改進，一個是改頭插法為尾插法，還有一個是當一個位置沖突過多時（大於等於8），存儲的value將形成一排序二叉樹，排序的依據為key的hashCode，這樣在最壞情況下，性能也只退化到O(logn)。
這樣的改進意義重大，譽銀一是從O(n)提升到O(logn)的時間開銷（最壞情況），二是如果惡意程序知道我們利用的Hash演算法，在純鏈表情況下，發送大量請求導致hash碰撞，不停訪問這些key使HashMap忙於查找，最終癱瘓。

Ⅷ 哈希表與哈希（Hash）演算法

根據設定的 哈希函數H（key） 和 處理沖突的方法 將一組關鍵字影像到一個有限的連續的地址集（區間）上，並以關鍵字在地址集中的「像」作為記錄在表中的存儲位置，這種表便成為 哈希表 ，這一映像過程稱為哈希造表或 散列 ，所得存儲位置稱 哈希地址 或 散列地址 。

上面所提到的 哈希函數 是指：有一個對應關系 f ，使得每個關鍵字和結構中一個唯一的存儲位置相對應，這樣在查找時，我們不需要像傳統的爛碼查找演算法那樣進行比較，而是根據這個對應關系 f 找到給定值K的像 f（K） 。

哈希函數也可叫哈希演算法，它可以用於檢驗信息是否相同（ 文件校驗 ），或兆歷褲者檢驗信息的擁有者是否真實（ 數字簽名 ）。

下面分別就哈希函數和族簡處理沖突的方法進行討論;

構造哈希函數的方法有很多。在介紹各種方法前，首先需要明確什麼是「好」 的哈希演算法。若對於關鍵字集合中的任一個關鍵字，經哈希函數映像到地址集合中任何一個地址的概率是相等的，則稱此類哈希函數是 均勻的 （Uniform）哈希函數。換句話說，就是使關鍵字經過哈希函數得到一個「隨機的地址」，以便使一組關鍵字的哈希地址均勻分布在整個地址區間中，從而減少沖突。
常用的構造哈希函數的方法有：

理論研究表明， 除留余數法的模 p 取不大於表長且最接近表長 m 的素數效果最好，且 p 最好取1.1 ⁿ ~ 1.7 ⁿ 之間的一個素數（n為存在的數據元素個數） 。

以上便是常用的6種構造哈希函數的方法，實際工作中需視不同的情況採用採用不同的哈希函數，通常考慮的因素有：

前面有提到過 均勻的哈希函數可以減少沖突，但不能避免 ，因此，如何處理沖突是哈希造表不可缺少的另一方面。

通常用的處理沖突的方法有下列幾種：

在哈希表上進行查找的過程和哈希建表的過程基本一致。 給定K值，根據建表時設定的哈希函數求得哈希地址，若表中此位置上沒有記錄，則查找不成功；否則比較關鍵字，若和給定值相等，則查找成功；否則根據造表時設定的處理沖突的方案找「下一地址」 ，直到找到為止。

Ⅸ redis使用什麼演算法來解決hash沖突

因為Memcached的哈希策略是在其客戶端實現的，因此不同的客戶端實現也有區別，以Spymemcache、Xmemcache為例，都是使用了KETAMA作為其實現。
因此，我們也可以使用一致性hash演算法來解決Redis分布式這個問題。在介紹一致性hash演算法之前，先介紹一下我之前想的一個方法，怎麼把Key均勻的映射到多台Redis Server上。

Ⅹ 哈希（hash） - 哈希演算法的應用

通過之前的學習，我們已經了解了哈希函數在散列表中的應用，哈希函數就是哈希演算法的一個應用。那麼在這里給出哈希的定義： 將任意長度的二進制值串映射為固定長度的二進制值串，這個映射規則就是哈希演算法，得到的二進制值串就是哈希值 。
要設計一個好的哈希演算法並不容易，它應該滿足以下幾點要求：

哈希演算法的應用非常廣泛，在這里就介紹七點應用：

有很多著名的哈希加密演算法：MD5、SHA、DES...它們都是通過哈希進行加密的演算法。
對於加密的哈希演算法來說，有兩點十分重要：一是很難根據哈希值反推導出原始數據；二是散列沖突的概率要很小。
當然，哈希演算法不可能排除散列沖突的可能，這用數學中的 鴿巢原理 就可以很好解釋。以MD5演算法來說，得到的哈希值為一個 128 位的二進制數，它的數據容量最多為 2 ¹²⁸ bit，如果超過這個數據量，必然會出現散列沖突。
在加密解密領域沒有絕對安全的演算法，一般來說，只要解密的計算量極其龐大，我們就可以認為這種加密方法是較為安全的。

假設我們有100萬個圖片，如果我們在圖片中尋找某一個圖片是非常耗時的，這是我們就可以使用哈希演算法的原理為圖片設置唯一標識。比如，我們可以從圖片的二進制碼串開頭取100個位元組，從中間取100個位元組，從結尾取100個位元組，然後將它們合並，並使用哈希演算法計算得到一個哈希值，將其作為圖片的唯一標識。
使用這個唯一標識判斷圖片是否在圖庫中，這可以減少甚多工作量。

在傳輸消息的過程中，我們擔心通信數據被人篡改，這時就可以使用哈希函數進行數據校驗。比如BT協議中就使用哈希栓發進行數據校驗。

在散列表那一篇中我們就講過散列函數的應用，相比於其它應用，散列函數對於散列演算法沖突的要求低很多（我們可以通過開放定址法或鏈表法解決沖突），同時散列函數對於散列演算法是否能逆向解密也並不關心。
散列函數比較在意函數的執行效率，至於其它要求，在之前的我們已經講過，就不再贅述了。

接下來的三個應用主要是在分布式系統中的應用

復雜均衡的演算法很多，如何實現一個會話粘滯的負載均衡演算法呢？也就是說，我們需要在同一個客戶端上，在一次會話中的所有請求都路由到同一個伺服器上。

最簡單的辦法是我們根據客戶端的 IP 地址或會話 ID 創建一個映射關系。但是這樣很浪費內存，客戶端上線下線，伺服器擴容等都會導致映射失效，維護成本很大。

藉助哈希演算法，我們可以很輕松的解決這些問題：對客戶端的 IP 地址或會話 ID 計算哈希值，將取得的哈希值域伺服器的列表的大小進行取模運算，最後得到的值就是被路由到的伺服器的編號。

假設有一個非常大的日誌文件，裡面記錄了用戶的搜索關鍵詞，我們想要快速統計出每個關鍵詞被搜索的次數，該怎麼做呢？

分析一下，這個問題有兩個難點：一是搜索日誌很大，沒辦法放到一台機器的內存中；二是如果用一台機器處理這么大的數據，處理時間會很長。

針對這兩個難點，我們可以先對數據進行分片，然後使用多台機器處理，提高處理速度。具體思路：使用 n 台機器並行處理，從日誌文件中讀出每個搜索關鍵詞，通過哈希函數計算哈希值，然後用 n 取模，最終得到的值就是被分配的機器編號。
這樣，相同的關鍵詞被分配到了相同的機器上，不同機器只要記錄屬於自己那部分的關鍵詞的出現次數，最終合並不同機器上的結果即可。

針對這種海量數據的處理問題，我們都可以採用多機分布式處理。藉助這種分片思路，可以突破單機內存、CPU等資源的限制。

處理思路和上面出現的思路類似：對數據進行哈希運算，對機器數取模，最終將存儲數據（可能是硬碟存儲，或者是緩存分配）分配到不同的機器上。

你可以看一下上圖，你會發現之前存儲的數據在新的存儲規則下全部失效，這種情況是災難性的。面對這種情況，我們就需要使用一致性哈希演算法。

哈希演算法是應用非常廣泛的演算法，你可以回顧上面的七個應用感受一下。

其實在這里我想說的是一個思想： 用優勢彌補不足 。
例如，在計算機中，數據的計算主要依賴 CPU ，數據的存儲交換主要依賴內存。兩者一起配合才能實現各種功能，而兩者在性能上依然無法匹配，這種差距主要是： CPU運算性能對內存的要求遠高於現在的內存能提供的性能。
也就是說，CPU運算很快，內存相對較慢，為了抹平這種差距，工程師們想了很多方法。在我看來，散列表的使用就是利用電腦的高計算性能（優勢）去彌補內存速度（不足）的不足，你仔細思考散列表的執行過程，就會明白我的意思。

以上就是哈希的全部內容