散列函數(shù)：一個把查找表中的關(guān)鍵字映射稱對應(yīng)的地址的函數(shù)，記為Hash(key)=Addr(這里的地址也可以看作數(shù)組下標(biāo)，索引或內(nèi)存地址等)

散列函數(shù)把兩個或兩個以上的不同關(guān)鍵字映射到同一地址，稱為“沖突”。（key1!=key2,但是f(key1)=f(key2)）

散列表：根據(jù)設(shè)定的散列函數(shù)和所選中的處理沖突的方法，將一組關(guān)鍵字映像到一個有限的、地址連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“象”作為相應(yīng)記錄在表中的存儲位置，如此構(gòu)造所得的查找表稱之為“散列表”

構(gòu)造散列函數(shù)的方法

對數(shù)字的關(guān)鍵字有一下方法：直接定址法、數(shù)字分析法、平方取中法、折疊法、除留余數(shù)法

若關(guān)鍵字是非數(shù)字的，則需先對其進(jìn)行數(shù)字化處理

1.直接定址法(僅適用于地址集合的大小==關(guān)鍵字集合的大小)

H(key)=a*key+b

2.數(shù)字分析法(僅適合已知關(guān)鍵字的集合)

假設(shè)關(guān)鍵字集合中的每個關(guān)鍵字都是由s位數(shù)字組成(u1,u2,...,us)，分析關(guān)鍵字集合中的全體，并從中提取分布均勻的若干位（或他們的組合）組成地址

3.平方取中法（適用于關(guān)鍵字的每一位取值都不夠均勻的情況）

以關(guān)鍵字的平防止的中間幾位作為存儲地址。求“關(guān)鍵字的平方值”的目的是為了擴(kuò)大差別，同時平方值的中間各位又能受到整個關(guān)鍵字中各位的影響

4.折疊法（適用于關(guān)鍵字的數(shù)字位比較多的情況）

將關(guān)鍵字分割成若干部分，然后取他們的疊加和為散列地址（又分移位疊加和間界疊加）

5.除留余數(shù)法

H(key)=key%p

其中，p是不大于m但最接近或等于m的質(zhì)數(shù)

為什么要對p進(jìn)行限制？因為若是沒有這個限制，沖突會比較多

處理沖突的實際含義就是為產(chǎn)生沖突的地址尋找下一個散列地址

1.開放定址法

H0=H(key)

Hi=(H(key)+di) MOD m

具體細(xì)分有4種方法

1.線性探測再散列

Di=c*i（i為查找的次數(shù)，c=1）

2.平方探測再散列

Di=12，-12，22，-22，...

3.隨機(jī)探測再散列

Di是一組偽隨機(jī)數(shù)列

4.雙散列

Di=i*H2(key)

聚集現(xiàn)象：當(dāng)我們使用處理沖突的方法后，占用了另一個本應(yīng)存放在那里的元素的地址，就會產(chǎn)生聚集現(xiàn)象

2.鏈地址法

在所有本應(yīng)存放數(shù)據(jù)的地方改換成指針，指向一個鏈表，鏈表中存放各同義詞

散列表的查找

對于給定值K，計算散列地址i=H(K)

若r[i]==NULL,則查找不成功

若r[i].key=K,則查找成功

否則“求下一地址Hi”

直至r[hi]==NULL(查找不成功)

或r[Hi].key=K(查找成功)為止

決定散列表查找的ASL的因素

1.選用的散列函數(shù)（一般情況下，我們?nèi)蝿?wù)選用的散列函數(shù)是均勻的，所有在討論ASL時，可以不考慮這個因素）

2.選用的處理沖突的方法

3.散列表飽和的程度：裝填因子值的大?。╪-記錄數(shù)，m-表的長度）