哈希表發生沖突解決方法

Ⅰ 哈希查找的解決沖突

影響哈希查找效率的一個重要因素是哈希函數本身。當兩個不同的數據元素的哈希值相同時，就會發生沖突。為減少發生沖突的可能性，哈希函數應該將數據盡可能分散地映射到哈希表的每一個表項中。解決沖突的方法有以下兩種：
(1) 開放地址法
如果兩個數據元素的哈希值相同，則在哈希表中為後插入的數據元素另外選擇一個表項。
當程序查找哈希表時，如果沒有在第一個對應的哈希表項中找到符合查找要求的數據元素，程序就會繼續往後查找，直到找到一個符合查找要求的數據元素，或者遇到一個空的表項。
(2) 鏈地址法
將哈希值相同的數據元素存放在一個鏈表中，在查找哈希表的過程中，當查找到這個鏈表時，必須採用線性查找方法。
例3. 6是一個簡單的哈希查找演算法程序，你可以將它和本章結尾的有關代碼一起編譯連接成一個可執行程序。
例3．6一個簡單的哈希查找演算法程序
1: #include<stdlib.h>
2: #include<string.h>
3: #include list.h
4: #include hash.h
5:
6: #define HASH_SIZE 1024
7:
8: static listnode_t *hashTable[HASH_SIZE];
9:
10: void insert(const char * s)
11: {
12: listnode_t *ele = newNode((void * ) s)
13: unsigned int h = hash(s) % HASH_SIZE;
14:
15: ele->next = hashTable[h]
16: hashTable[h] = ele;
17: }
18:
19: void print (void)
20: {
21: int h;
22:
23: for (h = 0; h < HASH_SIZE; h++)
24: {
25: listnode_t * lp = hashTalbe[h];
26:
27: if(lp == NULL)
28: continue;
29: printf([%d] , h);
30: while (lp)
31: {
32: printf( '%s' , lp->u.str)
33: lp = ip->next;
34: }
35: putchar (' ');
36: }
37: }
38:
39: const char *search(const char *s)
40: {
39: unsigned int h = hash(s) % HASH_SIZE;
42: listnode_t * lp = hashTable[h];
43:
44: while (lp)
45: {
46: if (! strcmp (s, lp->u.str))
47: return lp->u.str;
48: lp = lp->next;
49: }
50: return NULL;
51: }
請參見：
3. 4 哪一種查找方法最方便?
3．5 哪一種查找方法最快?
3．8 怎樣查找鏈表中的數據?
_____________________________________________
以下是一個簡單示例：
#include<iostream>
#include<string>
using namespace std;
#define m 5 //人數
#define n 10 //哈希表長度
#define q 7 //隨機數
struct name{
char *py;
int k;
};
name namelist[n];
struct hash{
char *py;
int k;
int s;
};
hash hashlist[n];
void listname()
{
char *f;
int s0,r,i;
namelist[0].py=as;
namelist[1].py=sa;
namelist[2].py=d;
namelist[3].py=f;
namelist[4].py=g;
for(i=0;i<m;i++)
{
s0=0;
f=namelist[i].py;
for(r=0;*(f+r)!='';r++)
s0+=*(f+r);
namelist[i].k=s0;
}
}
void creathash()
{
int i;
for(i=0;i<n;i++)
{
hashlist[i].py=;
hashlist[i].k=0;
hashlist[i].s=0;
}
for(i=0;i<m;i++)
{
int sum=0;
int adr=(namelist[i].k)%q;
int d=adr;
if(hashlist[adr].s==0)
{
hashlist[adr].py=namelist[i].py;
hashlist[adr].k=namelist[i].k;
hashlist[adr].s=1;
}
else
{
while(hashlist[d].k!=0)
{
d=(d+namelist[i].k%5+1)%q;
sum+=1;
}
hashlist[d].py=namelist[i].py;
hashlist[d].k=namelist[i].k;
hashlist[d].s=sum+1;
}
}
}
void find()
{
string nam;
int s0=0,r,sum=1,adr,d;
cout<<請輸入姓名的拼音：<<endl;
cin>>nam;;
for(r=0;r<20;r++)
s0+=nam[r];
adr=s0%q;
d=adr;
if(hashlist[adr].k==s0)
cout<<姓名:<<hashlist[d].py<< <<關鍵字:<<s0<< <<查找長度為: 1<<endl;
else if(hashlist[adr].k==0)
cout<<無此記錄！<<endl;
else
{
int g=0;
while(g==0)
{
d=(d+s0%5+1)%q;
sum+=1;
if(hashlist[d].k==0)
{
cout<<無此記錄！<<endl;
g=1;
}
if(hashlist[d].k==s0)
{
cout<<姓名:<<hashlist[d].py<< <<關鍵字:<<s0<< <<查找長度為: 1<<endl;
g=1;
}
}
}
}
void display()
{
int i;
float av=0;
for(i=0;i<n;i++)
{
cout<<姓名:<<hashlist[i].py<< <<關鍵字:<<hashlist[i].k<<搜索長度：<<hashlist[i].s<<endl;
}
for(i=0;i<7;i++)
{
av+=hashlist[i].s;
}
av/=m;
cout<<平均查找長度：=<<av<<endl;
}
int main()
{
char x;
listname();
creathash();
cout<<d. 顯示哈希表 f. 查找 任意鍵退出 請選擇：<<endl;
while(cin>>x){
if(x=='d'){display(); cout<<endl;}
else if(x=='f'){find();cout<<endl;}
else break;
}
return 0;
}

Ⅱ 哈希表概念以及哈希沖突的處理

哈希表（散列表 Hash）是相對於線性表、樹形結構的一種數據結構，它能在元素的存儲位置和其關鍵字直接建立某種之間關系，那麼在進行查找時，就無需做或者做很少次的比較，就能通過這個關系直接由關鍵字找到對對應的記錄。這就是散列查找法（Hase Search）的思想，它通過對元素的關鍵字值進行某種運算，直接求出元素的地址。即使用關鍵字到地址的直接轉換方法，而不需要反復比較。因此，散列查找法又叫雜湊法或者散列法。

選擇一個好的散列函數可以在一定程度上減少沖突，但在實際應用中，很難完全避免發生沖突，所以選擇一個有效的處理沖突的方法是散列表的另一個關鍵問題。
處理沖突的方法與散列表本身的組織形式有關。按組織形式的不同，通常分為兩大類：開放地址法和鏈地址法。

開放地址法的基本思想是：把記錄都存儲在散列表數組中，當某一記錄關鍵字key的初始散列地址H0=H(key)發生沖突時，以H0為基礎，採取合適方法計算得到另一地址H1，如果H1仍然發生沖突，已H1位基礎再求下一個地址H2，若H2仍然沖突，再求得H3，以此類推，直至Hk不發生沖突為止，則Hk為該記錄在表中的散列地址。
根據計算方法，可以分為以下三種探測方法：

線性探測法會在出現在處理過程中發生沖突的發生第一個散列地址不同的記錄爭奪同一個後繼散列地址的現象，稱為二次聚集或者堆積。即在處理同義詞的沖突過程中，又添加了非同義詞的沖突。
它的優點是，只要散列表未滿，就一定能找到一個不發生沖突的地址

而二次探測法和偽隨機數探測法可以避免出現二次聚集現象，但是不保證一定能找到不發生沖突的地址。

鏈地址法的基本思想是：把具有相同散列地址的記錄放在同一個單鏈表中，稱為同義詞鏈表。有m個散列地址就有m個單鏈表，同時用數組HT[0..m-1]存放各個鏈表的頭指針，凡是散列地址為i的記錄都以結點的方式插入已HT[i]為頭結點的單鏈表中。

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

Ⅳ hashmap怎麼解決哈希沖突

java 中的 HashMap 是「數組+鏈表「結構，通過 key 計算出 hash 值，然後通過 hash 值算出數組下標。數組中的元素是一個鏈表，HashMap 的元素實際是存放在這個鏈表中的。
也就是說，通過在數組中創建一個鏈表，來解決哈希沖突。
另外，在 jdk1.8 中，鏈表長度大於 8 時，這個鏈表會轉為「紅黑樹結構」。

Ⅳ 哈希表演算法的處理沖突的方法

如果兩個同學分別叫 劉麗 劉蘭，當加入劉蘭時，地址24發生了沖突，我們可以以某種規律使用其它的存儲位置，如果選擇的一個其它位置仍有沖突，則再選下一個，直到找到沒有沖突的位置。選擇其它位置的方法有：
1、開放定址法
Hi=(H(key)+di) MOD m i=1,2,...,k(k

Ⅵ 解決哈希沖突的方法

https://blog.csdn.net/xtzmm1215/article/details/47177701
https://blog.csdn.net/afterlife_qiye/article/details/47976917

首先在元素的關鍵字k和元素的存儲位置p之間建立一個對應關系f，使得p=f(k)，f稱為 哈希函數 。創建哈希表時，把關鍵字為k的元素直接存入地址為f(k)的單元；以後當查找關鍵字為k的元素時，再利用哈希函數計算出該元素的存儲位置p=f(k)，從而達到按關鍵字直接存取元素的目的。
沖突 ：當關鍵字集合很大時，關鍵字值不同的元素可能會映象到哈希表的同一地址上，即 k1≠k2 ，但 H（k1）=H（k2），這種現象稱為 沖突 ，此時稱k1和k2為同義詞。
哈希法主要包括以下兩方面的內容：
1）如何構造哈希函數
2）如何處理沖突。
本文介紹解決沖突的辦法

這種方法也稱 再散列法 ，其基本思想是：當關鍵字key的哈希地址p=H（key）出現沖突時，以p為基礎，產生另一個哈希地址p1，如果p1仍然沖突，再以p為基礎，產生另一個哈希地址p2，…，直到找出一個不沖突的哈希地址pi ，將相應元素存入其中。這種方法有一個通用的再散列函數形式：

主要有以下三種：
線性探測再散列

這種方法的特點是：沖突發生時，順序查看錶中下一單元，直到找出一個空單元或查遍全表。

二次探測再散列

偽隨機探測再散列

具體實現時，應建立一個偽隨機數發生器，（如i=(i+p) % m），並給定一個隨機數做起點。

從上述例子可以看出，線性探測再散列容易產生「二次聚集」，即在處理同義詞的沖突時又導致非同義詞的沖突。例如，當表中i, i+1 ,i+2三個單元已滿時，下一個哈希地址為i, 或i+1 ,或i+2，或i+3的元素，都將填入i+3這同一個單元，而這四個元素並非同義詞。線性探測再散列的優點是：只要哈希表不滿，就一定能找到一個不沖突的哈希地址，而二次探測再散列和偽隨機探測再散列則不一定。

拉鏈法解決沖突的做法是：將所有關鍵字為同義詞的結點鏈接在同一個單鏈表中。若選定的散列表長度為m，則可將散列表定義為一個由m個頭指針組成的指針數 組T[0..m-1]。凡是散列地址為i的結點，均插入到以T[i]為頭指針的單鏈表中。T中各分量的初值均應為空指針。
特點

這種方法是同時構造多個不同的哈希函數：

當哈希地址Hi=RH1（key）發生沖突時，再計算Hi=RH2（key）……，直到沖突不再產生。這種方法不易產生聚集，但增加了計算時間。

這種方法的基本思想是：將哈希表分為 基本表 和 溢出表 兩部分，凡是和基本表發生沖突的元素，一律填入溢出表

Ⅶ 哈希表的處理沖突

1. 開放定址法：Hi=(H(key) + di) MOD m,i=1,2，…，k(k<=m-1），其中H(key）為散列函數，m為散列表長，di為增量序列，可有下列三種取法：
1.1. di=1,2,3，…，m-1，稱線性探測再散列；
1.2. di=1^2,-1^2,2^2,-2^2，⑶^2，…，±（k)^2,(k<=m/2）稱二次探測再散列；
1.3. di=偽隨機數序列，稱偽隨機探測再散列。
2. 再散列法：Hi=RHi(key),i=1,2，…，k RHi均是不同的散列函數，即在同義詞產生地址沖突時計算另一個散列函數地址，直到沖突不再發生，這種方法不易產生「聚集」，但增加了計算時間。
3. 鏈地址法（拉鏈法）
4. 建立一個公共溢出區

Ⅷ hash沖突的方法

當沖突發生後，直接去下一個位置找是否存在沒用的位置，例如2位置發生沖突，然後去下一位置3查找，如果3也被佔用，去找4，直到問題解決

未發生沖突前

直到現在2插入，發現2位置上上是5，已經有值，所以去找下一個發現沒有了，緊接著直接擴容和線性探測

後面4插入時，先去看1，發現有1，看2發現有5，看3發現有2，擴容插入4

可以看到非常容易產生一次聚類

以上為例：
當2發現發生沖突時直接每次增長i^2 倍，即2（hash值）+（-） i^2

當4發生沖突，先是尋找2（1+1^2）再尋找5（1+ 2^2）

發生沖突：如果用偽隨機探測再散列處理沖突，且偽隨機數序列為：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）……，直到沖突不再產生。這種方法不易產生聚集，但增加了計算時間。

在我hashcode的後面建立一個鏈表，每一個鏈表表示現在hashcode為當前的所有元素
但是這個方法很容易就造成鏈表的長度過大，在訪問時候可能會時間很長，
所有適時的要增大數組的長度。來換取鏈表的長度
例如上面是mod3，我們可以mod5

什麼時候擴容？
「我們可以定義這樣一個變數 α = 所有元素個數/數組的大小，我們叫它裝載因子吧，它代表著我們的Hash表（也就是數組）的裝滿程度，在這里也代表鏈表的平均長度
例如上面的 數組{5,1,3,2,4} 當取mod3時候就是 α = 5%3，這時候我們擴容
即使Hash函數設計的合理，基本上每次存放元素的時候就會沖突，所以鑒於兩者之間我覺得 0.6 - 0.9 之間是一個不錯的選擇，不妨選0.75吧」
參考： https://cloud.tencent.com/developer/article/1361248

Ⅸ 哈希表、哈希演算法、一致性哈希表

    散列表（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。它通過把關鍵碼映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數（哈希函數），存放記錄的數組叫做散列表。

  優點：

        哈希表可以提供快速的操作。

缺點：

        哈希表通常是基於數組的，數組創建後難於擴展。

        也沒有一種簡便的方法可以以任何一種順序〔例如從小到大）遍歷表中的數據項 。

    綜上， 如果不需要有序遍歷數據，井且可以提前預測數據量的大小。那麼哈希表在速度和易用性方面是無與倫比的。

        1. 使用哈希函數將被查找的鍵轉換為數組的索引。

        2. 處理哈希碰撞沖突。

    若關鍵字為 k ，則其值存放在 f(k) 的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應關系 f 為散列函數，按這個思想建立的表為散列表。

    若對於關鍵字集合中的任一個關鍵字，經散列函數映象到地址集合中任何一個地址的概率是相等的，則稱此類散列函數為 均勻散列函數 (Uniform Hash function)，這就是使關鍵字經過散列函數得到一個"隨機的地址"，從而減少碰撞。

散列函數能使對一個數據序列的訪問過程更加迅速有效，通過散列函數，數據元素將被更快地定位。

一個好的散列函數一般應該考慮下列因素 ：

    1.計算簡單，以便提高轉換速度。

    2.關鍵詞對應的地址空間分布均勻，以盡量減少沖突。

1.   直接定址法

    取關鍵字或者關鍵字的某個線性函數值作為哈希地址,即H(Key)=Key或者H(Key)=a*Key+b(a,b為整數),這種散列函數也叫做自身函數.如果H(Key)的哈希地址上已經有值了,那麼就往下一個位置找,直到找到H(Key)的位置沒有值了就把元素放進去。

2.   數字分析法

    數字分析法就是找出數字的規律，盡可能利用這些數據來構造沖突幾率較低的散列地址。

3.   平方取中法

    取關鍵字平方後的中間幾位作為散列地址。這種方法的原理是通過取平方擴大差別，平方值的中間幾位和這個數的每一位都相關，則對不同的關鍵字得到的哈希函數值不易產生沖突，由此產生的哈希地址也較為均勻。該方法適用於關鍵字中的每一位都有某些數字重復出現頻度很高的現象。

4.   折疊法

    折疊法是將關鍵字分割成位數相同的幾部分,最後一部分位數可以不同,然後取這幾部分的疊加和(注意:疊加和時去除進位)作為散列地址。

    數位疊加可以有移位疊加和間界疊加兩種方法。移位疊加是將分割後的每一部分的最低位對齊,然後相加;間界疊加是從一端向另一端沿分割界來回折疊,然後對齊相加。

    該方法適用於關鍵字特別多的情況。

5.   隨機數法

    選擇一個隨機數,作為散列地址,通常用於關鍵字長度不同的場合。

6.   除留余數法

    取關鍵字被某個不大於散列表表長m的數p除後所得的余數為散列地址.即H(Key)=Key MOD p,p<=m.不僅可以對關鍵字直接取模,也可在折疊、平方取中等運算之後取模。對p的選擇很重要，一般取素數或m，若p選得不好，則很容易產生沖突。

    對不同的關鍵字可能得到同一散列地址，即 k1≠k2 ，而 f(k1)=f(k2) ，這種現象稱為碰撞(英語:Collision)。具有相同函數值的關鍵字對該散列函數來說稱做同義詞。

    通過構造性能良好的散列函數，可以減少沖突，但一般不可能完全避免沖突，因此解決沖突是哈希法的另一個關鍵問題。 創建哈希表和查找哈希表都會遇到沖突，兩種情況下解決沖突的方法應該一致。

下面以創建哈希表為例，說明解決沖突的方法。

1.開放定址法

    這種方法也稱再散列法，其基本思想是：當關鍵字key的哈希地址p=H(key)出現沖突時，以p為基礎，產生另一個哈希地址p1，如果p1仍然沖突，再以p為基礎，產生另一個哈希地址p2，…，直到找出一個不沖突的哈希地址pi ，將相應元素存入其中。這種方法有一個通用的再散列函數形式：Hi=(H(key)+di)%m   i=1，2，…，m-1,其中H（key）為哈希函數，m 為表長，di稱為增量序列，i為碰撞次數。增量序列的取值方式不同，相應的再散列方式也不同。增量序列主要有以下幾種：

    (1) 線性探測再散列

        di=1，2，3，…，m-1

        這種方法的特點是：沖突發生時，順序查看錶中下一單元，直到找出一個空單元或查遍全表。

    (2)二次探測再散列

        di=12，-12，22，-22，…，k2，-k2( k<=m/2 )

        這種方法的特點是：沖突發生時，在表的左右進行跳躍式探測，比較靈活。

    (3)偽隨機探測再散列

        di=偽隨機數序列。

    線性探測再散列的 優點 是：只要哈希表不滿，就一定能找到一個不沖突的哈希地址，而二次探測再散列和偽隨機探測再散列則不一定。線性探測再散列容易產生「二次聚集」，即在處理同義詞的沖突時又導致非同義詞的沖突。

    其實除了上面的幾種方法，開放定址法還有很多變種，不過都是對di有不同的表示方法。（如雙散列探測法：di=i*h2(k)）

2.再哈希法

    這種方法是同時構造多個不同的哈希函數：Hi=RHi（key），i=1，2,3，…,n。

    當哈希地址H1=RH1（key）發生沖突時，再計算H2=RH2（key）……，直到沖突不再產生。這種方法不易產生聚集，但增加了計算時間。

 3.鏈地址法(拉鏈法)

    這種方法的基本思想是將所有哈希地址相同的元素構成一個稱為同義詞鏈的單鏈表，並將單鏈表的頭指針存在哈希表（數組）中，因而查找、插入和刪除主要在同義詞鏈中進行。若選定的散列表長度為m，則可將散列表定義為一個由m個頭指針組成的指針數組T[0..m-1]。凡是散列地址為i的結點，均插入到以T[i]為頭指針的單鏈表中。T中各分量的初值均應為空指針。鏈地址法適用於經常進行插入和刪除的情況。

     拉鏈法的優點

        與開放定址法相比，拉鏈法有如下幾個優點：

            (1)拉鏈法處理沖突簡單，且無堆積現象，即非同義詞決不會發生沖突，因此平均查找長度較短；

            (2)由於拉鏈法中各鏈表上的結點空間是動態申請的，故它更適合於造表前無法確定表長的情況；

            (3)開放定址法為減少沖突，要求裝填因子α較小，故當結點規模較大時會浪費很多空間。而拉鏈法中理論上可取α≥1，且結點較大時，拉鏈法中增加的指針域可忽略不計，因此節省空間；（散列表的裝填因子定義為：α= 填入表中的元素個數 / 散列表的長度）

註：HashMap默認裝填因子是0.75。

            (4)在用拉鏈法構造的散列表中，刪除結點的操作易於實現。只要簡單地刪去鏈表上相應的結點即可。而對開放定址法構造的散列表，刪除結點不能簡單地將被刪結點的空間置為空，否則將截斷在它之後填入散列表的同義詞結點的查找路徑。這是因為各種開放定址法中，空地址單元都被理解沒有查找到元素。 因此在用開放定址法處理沖突的散列表上執行刪除操作，只能在被刪結點上做刪除標記，而不能真正刪除結點。

     拉鏈法的缺點

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

4、建立公共溢出區

    這種方法的基本思想是：將哈希表分為基本表和溢出表兩部分，凡是和基本表發生沖突的元素，一律填入溢出表(在這個方法裡面是把元素分開兩個表來存儲)。

    散列表的查找過程基本上和造表過程相同。一些關鍵碼可通過散列函數轉換的地址直接找到，另一些關鍵碼在散列函數得到的地址上產生了沖突，需要按處理沖突的方法進行查找。在介紹的三種處理沖突的方法中，產生沖突後的查找仍然是給定值與關鍵碼進行比較的過程。所以，對散列表查找效率的量度，依然用平均查找長度來衡量。

    查找過程中，關鍵碼的比較次數，取決於產生沖突的多少，產生的沖突少，查找效率就高，產生的沖突多，查找效率就低。因此，影響產生沖突多少的因素，也就是影響查找效率的因素。

影響產生沖突多少有以下三個因素:

    1. 散列函數是否均勻;

    2. 處理沖突的方法;

    3. 散列表的裝填因子。

     散列表的裝填因子

        定義為:α= 填入表中的元素個數 / 散列表的長度

        α是散列表裝滿程度的標志因子。由於表長是定值，α與"填入表中的元素個數"成正比，所以，α越大，填入表中的元素較多，產生沖突的可能性就越大;α越小，填入表中的元素較少，產生沖突的可能性就越小。

        實際上，散列表的平均查找長度是裝填因子α的函數，只是不同處理沖突的方法有不同的函數。

    這個HASH演算法不是大學里數據結構課里那個HASH表的演算法。這里的HASH演算法是密碼學的基礎，了解了hash基本定義，就不能不提到一些著名的hash演算法，MD5 和 SHA-1 可以說是目前應用最廣泛的Hash演算法，而它們都是以 MD4 為基礎設計的。

Hash演算法在信息安全方面的應用主要體現在以下的3個方面:

     ⑴  文件校驗

        我們比較熟悉的校驗演算法有奇偶校驗和CRC校驗，這2種校驗並沒有抗 數據篡改 的能力，它們一定程度上能檢測出數據傳輸中的信道誤碼，但卻不能防止對數據的惡意破壞。

        MD5 Hash演算法的"數字指紋"特性，使它成為目前應用最廣泛的一種文件完整性 校驗和 (Checksum)演算法，不少Unix系統有提供計算md5 checksum的命令。

     ⑵  數字簽名

        Hash 演算法也是現代密碼體系中的一個重要組成部分。由於非對稱演算法的運算速度較慢，所以在 數字簽名 協議中，單向散列函數扮演了一個重要的角色。對 Hash 值，又稱"數字摘要"進行數字簽名，在統計上可以認為與對文件本身進行數字簽名是等效的。而且這樣的協議還有其他的優點。

     ⑶ 鑒權協議

        如下的鑒權協議又被稱作挑戰--認證模式:在傳輸信道是可被偵聽，但不可被篡改的情況下，這是一種簡單而安全的方法。

    一致性哈希表簡稱DHT，主要應用於分布式緩存中，可以用來解決分布式存儲結構下動態增加和刪除節點所帶來的問題。比如，一個分布式的存儲系統，要將數據存儲到具體的節點上，如果採用普通的hash方法，將數據映射到具體的節點上，如key%N（key是數據的key，N是機器節點數），如果有一個機器加入或退出這個集群，則所有的數據映射都無效了，如果是持久化存儲則要做數據遷移，如果是分布式緩存，則其他緩存就失效了。

判定哈希演算法好壞的四個定義 ：

    1、平衡性(Balance)：平衡性是指哈希的結果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。

    2、單調性(Monotonicity)：單調性是指如果已經有一些內容通過哈希分派到了相應的緩沖中，又有新的緩沖加入到系統中。哈希的結果應能夠保證原有已分配的內容可以被映射到原有的或者新的緩沖中去，而不會被映射到舊的緩沖集合中的其他緩沖區。

    3、分散性(Spread)：在分布式環境中，終端有可能看不到所有的緩沖，而是只能看到其中的一部分。當終端希望通過哈希過程將內容映射到緩沖上時，由於不同終端所見的緩沖范圍有可能不同，從而導致哈希的結果不一致，最終的結果是相同的內容被不同的終端映射到不同的緩沖區中。這種情況顯然是應該避免的，因為它導致相同內容被存儲到不同緩沖中去，降低了系統存儲的效率。 分散性的定義就是上述情況發生的嚴重程度。好的哈希演算法應能夠盡量避免不一致的情況發生，也就是盡量降低分散性。

    4、負載(Load)：負載問題實際上是從另一個角度看待分散性問題。既然不同的終端可能將相同的內容映射到不同的緩沖區中，那麼對於一個特定的緩沖區而言，也可能被不同的用戶映射為不同的內容。與分散性一樣，這種情況也是應當避免的， 因此好的哈希演算法應能夠盡量降低緩沖的負荷。

    在分布式集群中，對機器的添加刪除，或者機器故障後自動脫離集群這些操作是分布式集群管理最基本的功能。如果採用常用的hash取模演算法，那麼在有機器添加或者刪除後，很多原有的數據就無法找到了，這樣嚴重的違反了單調性原則。接下來主要說明一下一致性哈希演算法是如何設計的。

以SpyMemcached的ketama演算法來說，思路是這樣的：

把數據用hash函數，映射到一個很大的空間里，如圖所示。數據的存儲時，先得到一個hash值，對應到這個環中的每個位置，如k1對應到了圖中所示的位置，然後沿順時針找到一個機器節點B，將k1存儲到B這個節點中。

如果B節點宕機了，則B上的數據就會落到C節點上，如下圖所示：

這樣，只會影響C節點，對其他的節點A，D的數據不會造成影響。然而，這又會造成一個「雪崩」的情況，即C節點由於承擔了B節點的數據，所以C節點的負載會變高，C節點很容易也宕機，這樣依次下去，這樣造成整個集群都掛了。

為此，引入了「虛擬節點」的概念：即把想像在這個環上有很多「虛擬節點」，數據的存儲是沿著環的順時針方向找一個虛擬節點，每個虛擬節點都會關聯到一個真實節點，如下圖所使用：

圖中的A1、A2、B1、B2、C1、C2、D1、D2都是虛擬節點，機器A負載存儲A1、A2的數據，機器B負載存儲B1、B2的數據，機器C負載存儲C1、C2的數據。由於這些虛擬節點數量很多，均勻分布，因此不會造成「雪崩」現象。

Ⅹ HashMap發生hash沖突怎麼辦

排解hash沖突的方法有很多，大致可以劃分為兩類：封閉定址法和開放定址法。
封閉定址法：

多槽位 multiple slots：桶單元細分成若干槽位slot，存放沖突的詞條；（無法根本解決問題）
獨立鏈法 linked-list chaining：每個桶存放一個指針，沖突的詞條組織成列表（效率太低）
公共溢出區 overflow area：單獨開辟一塊連續空間，發生沖突的詞條順序存入此區域（可能導致沖突次數激增）
開放定址法：每個桶都事先約定若干備用桶，構成一個查找鏈。
線性試探：一旦沖突，則試探後一緊鄰桶單元，直到命中或抵達空桶。
平方試探：以平方數為距離，確定下一個試探的桶單元。

雙平方試探：
再散列 double hashing：即用第二個散列函數確定偏移。