散列表中解決沖突的兩種方法是

① 散列表的查找效率主要取決於建表時所選取的散列函數和處理沖突的方法

散列表的查找效益主要取決於建表示所選的散列函數和儲蓄方式的這段換成這個是寫三角函數的處理方法。

② 關於散列表，散列函數的兩個問題。

散列表是一種數據結構，通過散列函數（也就是 hash 函數）將輸入映射到一個數字，一般用映射出的數字作為存儲位置的索引。數組在查找時效率很高，但是插入和刪除卻很低。而鏈表剛好反過來。設計合理的散列函數可以集成鏈表和數組的優點，在查找、插入、刪除時實現 O(1) 的效率。散列表的存儲結構使用的也是數組加鏈表。執行效率對比可以看下圖 1.3：

散列表的主要特點：

1. 將輸入映射到數字

2.不同的輸入產生不同的輸出

3.相同的輸入產生相同的輸出

4. 當填裝因子超過閾值時，能自動擴展。填裝因子 = 散列表包含的元素數 / 位置總數，當填裝因子 =1，即散列表滿的時候，就需要調整散列表的長度，自動擴展的方式是：申請一塊舊存儲容量 X 擴容系數的新內存地址，然後把原內存地址的值通過其中的 key 再次使用 hash 函數計算存儲位置，拷貝到新申請的地址。

5. 值呈均勻分布。這里的均勻指水平方向的，即數組維度的。如果多個值被映射到同一個位置，就產生了沖突，需要用鏈表來存儲多個沖突的鍵值。極端情況是極限沖突，這與一開始就將所有元素存儲到一個鏈表中一樣。這時候查找性能將變為最差的 O(n)，如果水平方向填充因子很小，但某些節點下的鏈表又很長，那值的均勻性就比較差。

③ 有一個表長為m的散列表，初始狀態為空，現將n（n<m）個不同的關鍵碼插入到散列表中，解決沖突的方法是用線

假設n個關鍵碼的散列值均為x，那麼：
插入第一個關鍵碼時，檢查x位置，結果為空，直接插入，探測次數為0；
插入第二個關鍵碼時，檢查x位置，結果不為空，採用線性探測法，繼續探測x+1位置，結果為空，插入，探測次數為1；
……
插入第n個關鍵碼時，x位置不為空，從x+1位置開始探測，直至探測到x+(n-1)位置時才為空（這里假設x+(n-1)<m），執行插入操作，探測次數為n-1次。
所以，總的探測次數是一個等差數列，首項為0，公差為1，項數為n，那麼，總次數自然可以用等差數列的求和公式算出，即S=a1+n*(n-1)*b/2=0+n*(n-1)*1/2=n(n-1)/2。

④ 已知散列表長度為13，散列函數為H(key)=key % 11，處理沖突的方法為線性探測法

10%11=10 a[9]=10

8%11=8 a[7]=8

40%11=7 a[6]=40

27%11=5 a[4]=27

21%11=10

57%11=2 a[1]=57

46%11=2

23%11=1 a[0]=23

19%11=8

56%11=1

21和10沖突 且a[10]空 所以a[10]=21

46和57沖突 且a[2]空 所以 a[2]=46

19和8沖突 且a[8]空 所以 a[8]=19

56和23沖突 且a[1]、a[2]不空，a[3]空 a[3]=56

最後是23,57,46,56,27，空，40,8，19，10，21，空，空

查找成功的平均長度：6*1+3*2+1*3=15

查找不成功的平均長度：6+5+4+3+2+1+6+5+4+3+2+1=42

(4)散列表中解決沖突的兩種方法是擴展閱讀：

直接定址法

例如：有一個從1到100歲的人口數字統計表，其中，年齡作為關鍵字，哈希函數取關鍵字自身。

數字分析法

有學生的生日數據如下：

年.月.日

75.10.03

75.11.23

76.03.02

76.07.12

75.04.21

76.02.15

經分析，第一位，第二位，第三位重復的可能性大，取這三位造成沖突的機會增加，所以盡量不取前三位，取後三位比較好。

平方取中法

取關鍵字平方後的中間幾位為哈希地址。

折疊法

將關鍵字分割成位數相同的幾部分（最後一部分的位數可以不同），然後取這幾部分的疊加和（捨去進位）作為哈希地址，這方法稱為折疊法。

例如：每一種西文圖書都有一個國際標准圖書編號，它是一個10位的十進制數字，若要以它作關鍵字建立一個哈希表，當館藏書種類不到10,000時，可採用此法構造一個四位數的哈希函數。

除留余數法

取關鍵字被某個不大於哈希表表長m的數p除後所得余數為哈希地址。

H(key)=key MOD p (p<=m)

隨機數法

選擇一個隨機函數，取關鍵字的隨機函數值為它的哈希地址，即

H(key)=random(key），其中random為隨機函數。通常用於關鍵字長度不等時採用此法。

若已知哈希函數及沖突處理方法，哈希表的建立步驟如下：

Step1.取出一個數據元素的關鍵字key，計算其在哈希表中的存儲地址D=H(key）。若存儲地址為D的存儲空間還沒有被佔用，則將該數據元素存入；否則發生沖突，執行Step2。

Step2.根據規定的沖突處理方法，計算關鍵字為key的數據元素之下一個存儲地址。若該存儲地址的存儲空間沒有被佔用，則存入；否則繼續執行Step2，直到找出一個存儲空間沒有被佔用的存儲地址為止。

⑤ 散列表處理沖突的二次探測法，表長要求是滿足4j+3的質數。但我在做題過程中發現有的表長不滿足這一條

合理誤差

⑥ 哈希查找的解決沖突

影響哈希查找效率的一個重要因素是哈希函數本身。當兩個不同的數據元素的哈希值相同時，就會發生沖突。為減少發生沖突的可能性，哈希函數應該將數據盡可能分散地映射到哈希表的每一個表項中。解決沖突的方法有以下兩種：
(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;
}

⑦ 散列查找的處理沖突的方法

思路：從發生沖突的那個單元開始，按照一定次序，從散列表中查找出一個空閑的存儲單元，把發生沖突的待插入元素存入到該單元的一類處理沖突的方法。
在使用該方法處理沖突的散列表中，查找一個元素的過程是：先根據給定關鍵字K，利用與插入時使用的同一散列函數h(K)計算出散列地址(設下標為d),然後用K同d單元的關鍵字比較，若相等則查找成功，否則按插入時處理沖突的相同次序，依次用K同所查單元的關鍵字比較，直到查找成功或查找到一空單元(表明查找失敗)為止。
有三種常見的開放定址法
（1）線性探查法
是用開放定址法處理沖突的一種最簡單的探查方法。
從發生沖突的d單元起,依次探查下一個單元,直到碰到一個空閑單元或探查完所有單元為止探查時,當達到下標為m-1的表尾單元時,下一個探查的單元是下標為0的表首單元。
探查序列為d,d+1,d+2……，表示為(d+i)%m (0≤i≤m-1)。
例如：構取m=13,線性表為A=(18,75,60,43,54,90,46)，構造的散列表如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 H 54 43 18 46 60 75 90 現向表中再插入關鍵字為31和58的兩個元素,用線性探查法解決沖突。
先插入31，h(31)=31%13=5,因H[5]被佔用，探查下一個即下標為6的單元，空閑，插入31。 0 1 2 3 4 5 6 7 8 9 10 11 12 H 54 43 18 31 46 60 75 90 再插入58，h(58)=58%13=6,因H[6]被佔用，探查下一個即下標為7的單元，因H[7]仍不空閑，再接著向下探查，當探查到下標為9的單元時，空閑，插入58。 0 1 2 3 4 5 6 7 8 9 10 11 12 H 54 43 18 31 46 60 58 75 90 利用線性探查法處理沖突易造成元素的「堆積」(聚集) 0 1 2 3 4 5 6 7 8 9 10 11 12 H 54 43 18 46 60 75 90 向散列表中插入一個元素：
int Insert (hashlist1 HT,int m,ElemType item)
{
//向長度為m的散列表HT中插入一個元素
int d=H(item.key,m); //可選一種合適的構造散列函數的方法，計算散列地址
int temp=d;
while(HT[d].key != NullTag)
{
//當d單元不空時繼續向後查找空位置
d=(d+1)%m;
if(d==temp) return 0;
}
HT[d]=item; //將新元素插入到下標為d的位置
return 1;
}
從散列表中查找一個元素：
int Search (hashlist1 HT,int m, ElemType item)
{
//從長度為m的散列表HT中查找
int d=H(item.key, m);
int temp=d;
while(HT[d].key!=NullTag)
{
//當散列地址中的關鍵字域不為空則循環
if(HT[d].key==item.key) return d;
else d=(d+1)%m;
if(d==temp) return -1;
}
return -1;
}
（2）平方探查法
探查序列為d,d+1,d+2……,表示為(d+i2)%m(0≤i≤m-1)。遞推公式為：
優點：它是一種較好的處理沖突的方法，可以較好避免堆積現象
缺點：不能探查到散列表上所有單元。
例：當d0=5,m=17時，只能探查到下標依次為5、6、9、14、4、13、7、3、1的單元。
d0=5;
d1=(5 +2*1-1)%17=6; d2=(6 +2*2-1)%17=9;
d3=(9 +2*3-1)%17=14; d4=(14 +2*4-1)%17=4;
d5=(4 +2*5-1)%17=13; d6=(13 +2*6-1)%17=7;
d7=(7 +2*7-1)%17=3; d8=(3 +2*8-1)%17=1; d9=(1 +2*9-1)%17=1;
（3）雙散列函數探查法
思路：
該方法使用兩個散列函數h1和h2，其中h1和前面的h(K)一樣，以關鍵字為自變數，產生一個0～m-1之間的數作散列地址;h2也以關鍵字為自變數，產生一個1～m-1之間的、並和m互素的數作散列地址。它的探查序列為：
利用雙散列法，按一定的距離，跳躍式地尋找「下一個」桶，減少了「堆積」的機會，最多經過m-1次探查，它會遍歷表中所有位置，回到H0 位置。
例：給出一組表項關鍵碼{22,41,53,46,30,13,01,67}。散列表為HT[0..10]，m = 11。
散列函數為：
Hash(x)=(3x) % 11
再散列函數為：
ReHash(x) = (7x) % 10 +1
Hi = ( Hi-1 + (7x) % 10 +1 ) % 11, i = 1, 2,
H0(22) = 0 H0(41) = 2 H0(53) = 5 H0(46) = 6
H0(30) = 2 沖突H1 = (2+1) = 3 ,H0(13) = 6 沖突H1 = (6+2) = 8
H0(01) = 3 沖突H1 = (3+8) = 0 ,H2 = (0+8) = 8 H3 = (8+8) = 5
H4 =(5+8)=2 H5 =(2+8)=10,H0(67)=3 沖突, H1 = (3+10) = 2 H2 = (2+10) = 1
搜索成功的平均搜索長度：
鏈接法
思路：就是把發生沖突的同義詞元素(結點)用單鏈表鏈接起來的方法。
例：假定一個線性表B為：B=(18,75,60,43,54,90,46,31,58,73,15,34)。
設採用的散列函數為h(K)=K%13,採用鏈接法處理：
在該例中，查找成功時平均查找長度為：
ASL=(8×1+3×2+1×3)/12≈1.42
若線性探查法處理沖突進行散列存儲，得到：
查找成功時平均查找長度為：
ASL=(7×1+1×2+1×4+1×4+1×2+1×6)/12≈2.1
多種方法分析
在散列表的插入和查找演算法中，平均查找長度與表的大小m無關，只與選取的散列函數、α值和處理沖突的方法有關,若假定所選取的散列函數能夠使任一關鍵字等概率地映射到散列空間的任一地址上，理論上證明：
當採用線性探查法處理沖突時，ASL=
當採用鏈地址法處理沖突時，ASL=
當採用平方探查法、雙散列函數法處理沖突時，ASL=
散列存儲優缺點
插入與查找的速度相當快根據關鍵字計算散列地址需要開銷一定計算時間佔用存儲空間較多在散列表中只能按關鍵字查找元素線性表中元素的邏輯關系無法在散列表中體現。 鏈表地址法為散列表的每個表象建立一個單鏈表，用於鏈接同義詞表，為此需要給每個表項增加一個指針域。
關於同義詞表的建立，有兩種方法。一種方法是在散列表的基本存儲區域外開辟一個新的區域用於存儲同義詞表，這種方法稱為「分離的同義詞子表法」，或稱「獨立鏈表地址法」，這個分離的同義詞子表所在的區域稱為「溢出區」。另一種方法是不建立溢出區，而是將同義詞子表存儲在散列表所在的基本存儲區域里，例如，可以再基本存儲區域里從後向前探測空閑表項，找到後就將其鏈接到同義詞子表中，這個方法稱為「結合的同義詞子表法」，或稱為「公共鏈表地址法」。
獨立鏈表地址法是查找效率最好的解決沖突的方法，速度要快於開放地址法，因為獨立鏈表地址法在進行散列查找時僅需搜索同義詞表。開放地址法要求表長時固定的，而地理鏈表法中的表項則是動態分配的，其表長僅受內存空間的限制。鏈表法的主要缺點是需要為每個表項（包括分離的同義子表的每個節點）設立一個指針域。
總之，獨立鏈表地址法的動態結構使它成為散列法中解決沖突的首選方法。

⑧ 簡述閉散列表解決沖突的基本思想

動機沖突的基本類型：
勒溫按趨避行為將動機沖突分為四大基本類型：
1．雙趨沖突
指兩種對個體都具有吸引力的目標同時出現，形成強度相同的二個動機。由於條件限制，只能選其中的一個目標，此時個體往往會表現出難於取捨的矛盾心理，這就是雙趨沖突。「魚與熊掌不可兼得」就是雙趨沖突的真實寫照。
2．雙避沖突
指兩種對個體都具有威脅性的目標同時出現，使個體對這兩個目標均產生逃避動機，但由於條件和環境的限制，也只能選擇其中的一個目標，這種選擇時的心理沖突稱之為雙避沖突。「前遇大河，後有追兵」正是這種處境的表現。
3． 趨避沖突
指某一事物對個體具有利與弊的雙重意義時，會使人產生二種動機態度：一方面好而趨之，另一方面則惡而遠之。所謂「想吃魚又怕魚刺」就是這種沖突的表現。
動機沖突可以造成個體不平衡、不協調的心理狀態，嚴重的心理沖突或持續時間較長可以引起個體的心理障礙，對求美者更要注意一點。
4. 多重趨避
在實際生活中，人們的趨避沖突常常表現出一種更復雜的形式，即人們面對著兩個或兩個以上的目標，而每個目標又分別具有吸引和排斥兩方面的作用。人們無法簡單的選擇一個目標，而迴避或拒絕另一個目標，必須進行多重的選擇。由此引起的沖突叫作多重趨避沖突。