摘自：編程中國(guó)
http://www.bc-cn.net/Article/kfyy/sjjg/200411/260.html哈希表（一）
教學(xué)目的： 掌握哈希表的概念作用及意義，哈希表的構(gòu)造方法
教學(xué)重點(diǎn)： 哈希表的構(gòu)造方法
教學(xué)難點(diǎn)： 哈希表的構(gòu)造方法
授課內(nèi)容：
一、哈希表的概念及作用
一般的線性表，樹(shù)中，記錄在結(jié)構(gòu)中的相對(duì)位置是隨機(jī)的，即和記錄的關(guān)鍵字之間不存在確定的關(guān)系，因此，在結(jié)構(gòu)中查找記錄時(shí)需進(jìn)行一系列和關(guān)鍵字的比較。這一類查找方法建立在“比較“的基礎(chǔ)上，查找的效率依賴于查找過(guò)程中所進(jìn)行的比較次數(shù)。
理想的情況是能直接找到需要的記錄，因此必須在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系f，使每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)。
哈希表最常見(jiàn)的例子是以學(xué)生學(xué)號(hào)為關(guān)鍵字的成績(jī)表，１號(hào)學(xué)生的記錄位置在第一條，１０號(hào)學(xué)生的記錄位置在第１０條...
如果我們以學(xué)生姓名為關(guān)鍵字，如何建立查找表，使得根據(jù)姓名可以直接找到相應(yīng)記錄呢？
| a |
b |
c |
d |
e |
f |
g |
h |
i |
j |
k |
l |
m |
n |
o |
p |
q |
r |
s |
t |
u |
v |
w |
x |
y |
z |
| 1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
| |
劉麗 |
劉宏英 |
吳軍 |
吳小艷 |
李秋梅 |
陳偉 |
... |
| 姓名中各字拼音首字母 |
ll |
lhy |
wj |
wxy |
lqm |
cw |
... |
| 用所有首字母編號(hào)值相加求和 |
24 |
46 |
33 |
72 |
42 |
26 |
... |
|
最小值可能為3 最大值可能為78 可放75個(gè)學(xué)生
|
用上述得到的數(shù)值作為對(duì)應(yīng)記錄在表中的位置，得到下表：
| |
|
成績(jī)一 |
成績(jī)二... |
| 3 |
... |
|
|
| ... |
... |
|
|
| 24 |
劉麗 |
82 |
95 |
| 25 |
... |
|
|
| 26 |
陳偉 |
|
|
| ... |
... |
|
|
| 33 |
吳軍 |
|
|
| ... |
... |
|
|
| 42 |
李秋梅 |
|
|
| ... |
... |
|
|
| 46 |
劉宏英 |
|
|
| ... |
... |
|
|
| 72 |
吳小艷 |
|
|
| ... |
... |
|
|
| 78 |
... |
|
|
上面這張表即哈希表。
如果將來(lái)要查李秋梅的成績(jī)，可以用上述方法求出該記錄所在位置：
李秋梅:lqm 12+17+13=42 取表中第42條記錄即可。
問(wèn)題：如果兩個(gè)同學(xué)分別叫 劉麗 劉蘭 該如何處理這兩條記錄？
這個(gè)問(wèn)題是哈希表不可避免的，即沖突現(xiàn)象：對(duì)不同的關(guān)鍵字可能得到同一哈希地址。
二、哈希表的構(gòu)造方法
１、直接定址法
例如：有一個(gè)從1到100歲的人口數(shù)字統(tǒng)計(jì)表，其中，年齡作為關(guān)鍵字，哈希函數(shù)取關(guān)鍵字自身。
| 地址 |
01 |
02 |
... |
25 |
26 |
27 |
... |
100 |
| 年齡 |
1 |
2 |
... |
25 |
26 |
27 |
... |
... |
| 人數(shù) |
3000 |
2000 |
... |
1050 |
... |
... |
... |
... |
| ... |
|
|
|
|
|
|
|
|
２、數(shù)字分析法
有學(xué)生的生日數(shù)據(jù)如下：
年.月.日
75.10.03
75.11.23
76.03.02
76.07.12
75.04.21
76.02.15
...
經(jīng)分析,第一位，第二位，第三位重復(fù)的可能性大，取這三位造成沖突的機(jī)會(huì)增加，所以盡量不取前三位，取后三位比較好。
３、平方取中法
取關(guān)鍵字平方后的中間幾位為哈希地址。
４、折疊法
將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同），然后取這幾部分的疊加和（舍去進(jìn)位）作為哈希地址，這方法稱為折疊法。
例如：每一種西文圖書(shū)都有一個(gè)國(guó)際標(biāo)準(zhǔn)圖書(shū)編號(hào)，它是一個(gè)10位的十進(jìn)制數(shù)字，若要以它作關(guān)鍵字建立一個(gè)哈希表，當(dāng)館藏書(shū)種類不到10,000時(shí)，可采用此法構(gòu)造一個(gè)四位數(shù)的哈希函數(shù)。如果一本書(shū)的編號(hào)為0-442-20586-4,則：
|
|
5864
|
|
5864
|
|
|
4220
|
|
0224
|
|
+)
|
04
|
+)
|
04
|
|
|
-----------
|
|
-----------
|
|
|
10088
|
|
6092
|
|
|
H(key)=0088
|
|
H(key)=6092
|
| |
|
|
|
|
|
(a)移位疊加
|
|
(b)間界疊加
|
５、除留余數(shù)法
取關(guān)鍵字被某個(gè)不大于哈希表表長(zhǎng)m的數(shù)p除后所得余數(shù)為哈希地址。
H(key)=key MOD p (p<=m)
６、隨機(jī)數(shù)法
選擇一個(gè)隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的哈希地址，即
H(key)=random(key) ,其中random為隨機(jī)函數(shù)。通常用于關(guān)鍵字長(zhǎng)度不等時(shí)采用此法。
三、總結(jié)
哈希表的優(yōu)缺點(diǎn)
四、作業(yè)
預(yù)習(xí)如何處理沖突及哈希表的查找。
http://www.bc-cn.net/Article/kfyy/sjjg/200411/261.html
哈希表（二）
教學(xué)目的： 掌握哈希表處理沖突的方法及哈希表的查找算法
教學(xué)重點(diǎn)： 哈希表處理沖突的方法
教學(xué)難點(diǎn)： 開(kāi)放定址法
授課內(nèi)容：
一、復(fù)習(xí)上次課內(nèi)容
什么是哈希表？如何構(gòu)造哈希表？
提出問(wèn)題：如何處理沖突？
二、處理沖突的方法
| |
|
成績(jī)一 |
成績(jī)二... |
| 3 |
... |
|
|
| ... |
... |
|
|
| 24 |
劉麗 |
82 |
95 |
| 25 |
... |
|
|
| 26 |
陳偉 |
|
|
| ... |
... |
|
|
| 33 |
吳軍 |
|
|
| ... |
... |
|
|
| 42 |
李秋梅 |
|
|
| ... |
... |
|
|
| 46 |
劉宏英 |
|
|
| ... |
... |
|
|
| 72 |
吳小艷 |
|
|
| ... |
... |
|
|
| 78 |
... |
|
|
如果兩個(gè)同學(xué)分別叫 劉麗 劉蘭，當(dāng)加入劉蘭時(shí)，地址24發(fā)生了沖突，我們可以以某種規(guī)律使用其它的存儲(chǔ)位置，如果選擇的一個(gè)其它位置仍有沖突，則再選下一個(gè)，直到找到?jīng)]有沖突的位置。選擇其它位置的方法有：
１、開(kāi)放定址法
Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1)
其中m為表長(zhǎng)，di為增量序列
如果di值可能為1,2,3,...m-1，稱線性探測(cè)再散列。
如果di取值可能為1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2)
稱二次探測(cè)再散列。
如果di取值可能為偽隨機(jī)數(shù)列。稱偽隨機(jī)探測(cè)再散列。
例：在長(zhǎng)度為11的哈希表中已填有關(guān)鍵字分別為17,60,29的記錄，現(xiàn)有第四個(gè)記錄，其關(guān)鍵字為38，由哈希函數(shù)得到地址為5，若用線性探測(cè)再散列，如下：
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
| |
|
|
|
|
60 |
17 |
29 |
|
|
|
(a)插入前
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
| |
|
|
|
|
60 |
17 |
29 |
38 |
|
|
(b)線性探測(cè)再散列
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
| |
|
|
|
|
60 |
17 |
29 |
|
|
|
(c)二次探測(cè)再散列
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
| |
|
|
38 |
|
60 |
17 |
29 |
|
|
|
(d)偽隨機(jī)探測(cè)再散列
偽隨機(jī)數(shù)列為9,5,3,8,1...
２、再哈希法
當(dāng)發(fā)生沖突時(shí)，使用第二個(gè)、第三個(gè)、哈希函數(shù)計(jì)算地址，直到無(wú)沖突時(shí)。缺點(diǎn)：計(jì)算時(shí)間增加。
３、鏈地址法
將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在同一線性鏈表中。
４、建立一個(gè)公共溢出區(qū)
假設(shè)哈希函數(shù)的值域?yàn)閇0,m-1],則設(shè)向量HashTable[0..m-1]為基本表，另外設(shè)立存儲(chǔ)空間向量OverTable[0..v]用以存儲(chǔ)發(fā)生沖突的記錄。
三、哈希表的查找
//開(kāi)放定址哈希表的存儲(chǔ)結(jié)構(gòu)
int hashsize[]={997,...};
typedef struct{
ElemType *elem;
int count;
int sizeindex;
}HashTable;
#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1
Status SearchHash(HashTable H,KeyType K,int &p,int &c){
p=Hash(K);
while(H.elem[p].key!=NULLKEY && !EQ(K,H.elem[p].key))
collision(p,++c);
if(EQ(K,H.elem[p].key)
return SUCCESS;
else return UNSUCCESS;
}
Status InsertHash(HashTable &H,EleType e){
c=0;
if(SearchHash(H,e.key,p,c))
return DUPLICATE;
else if(c<hashsize[H.sizeindex]/2){
H.elem[p]=e; ++H.count; return OK;
}
else RecreateHashTable(H);
}
四、總結(jié)
處理沖突的要求是什么？