摘自：编程中国
http://www.bc-cn.net/Article/kfyy/sjjg/200411/260.html哈希表（一）
教学目的： 掌握哈希表的概念作用及意义，哈希表的构造方法
教学重点： 哈希表的构造方法
教学难点： 哈希表的构造方法
授课内容：
一、哈希表的概念及作用
一般的线性表，树中，记录在结构中的相对位置是随机的，即和记录的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上，查找的效率依赖于查找过程中所进行的比较次数。
理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。
哈希表最常见的例子是以学生学号为关键字的成绩表，１号学生的记录位置在第一条，１０号学生的记录位置在第１０条...
如果我们以学生姓名为关键字，如何建立查找表，使得根据姓名可以直接找到相应记录呢？
| 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 |
... |
| 用所有首字母编号值相加求和 |
24 |
46 |
33 |
72 |
42 |
26 |
... |
|
最小值可能为3 最大值可能为78 可放75个学生
|
用上述得到的数值作为对应记录在表中的位置，得到下表：
| |
|
成绩一 |
成绩二... |
| 3 |
... |
|
|
| ... |
... |
|
|
| 24 |
刘丽 |
82 |
95 |
| 25 |
... |
|
|
| 26 |
陈伟 |
|
|
| ... |
... |
|
|
| 33 |
吴军 |
|
|
| ... |
... |
|
|
| 42 |
李秋梅 |
|
|
| ... |
... |
|
|
| 46 |
刘宏英 |
|
|
| ... |
... |
|
|
| 72 |
吴小艳 |
|
|
| ... |
... |
|
|
| 78 |
... |
|
|
上面这张表即哈希表。
如果将来要查李秋梅的成绩，可以用上述方法求出该记录所在位置：
李秋梅:lqm 12+17+13=42 取表中第42条记录即可。
问题：如果两个同学分别叫 刘丽 刘兰 该如何处理这两条记录？
这个问题是哈希表不可避免的，即冲突现象：对不同的关键字可能得到同一哈希地址。
二、哈希表的构造方法
１、直接定址法
例如：有一个从1到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。
| 地址 |
01 |
02 |
... |
25 |
26 |
27 |
... |
100 |
| 年龄 |
1 |
2 |
... |
25 |
26 |
27 |
... |
... |
| 人数 |
3000 |
2000 |
... |
1050 |
... |
... |
... |
... |
| ... |
|
|
|
|
|
|
|
|
２、数字分析法
有学生的生日数据如下：
年.月.日
75.10.03
75.11.23
76.03.02
76.07.12
75.04.21
76.02.15
...
经分析,第一位，第二位，第三位重复的可能性大，取这三位造成冲突的机会增加，所以尽量不取前三位，取后三位比较好。
３、平方取中法
取关键字平方后的中间几位为哈希地址。
４、折叠法
将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址，这方法称为折叠法。
例如：每一种西文图书都有一个国际标准图书编号，它是一个10位的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类不到10,000时，可采用此法构造一个四位数的哈希函数。如果一本书的编号为0-442-20586-4,则：
|
|
5864
|
|
5864
|
|
|
4220
|
|
0224
|
|
+)
|
04
|
+)
|
04
|
|
|
-----------
|
|
-----------
|
|
|
10088
|
|
6092
|
|
|
H(key)=0088
|
|
H(key)=6092
|
| |
|
|
|
|
|
(a)移位叠加
|
|
(b)间界叠加
|
５、除留余数法
取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。
H(key)=key MOD p (p<=m)
６、随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即
H(key)=random(key) ,其中random为随机函数。通常用于关键字长度不等时采用此法。
三、总结
哈希表的优缺点
四、作业
预习如何处理冲突及哈希表的查找。
http://www.bc-cn.net/Article/kfyy/sjjg/200411/261.html
哈希表（二）
教学目的： 掌握哈希表处理冲突的方法及哈希表的查找算法
教学重点： 哈希表处理冲突的方法
教学难点： 开放定址法
授课内容：
一、复习上次课内容
什么是哈希表？如何构造哈希表？
提出问题：如何处理冲突？
二、处理冲突的方法
| |
|
成绩一 |
成绩二... |
| 3 |
... |
|
|
| ... |
... |
|
|
| 24 |
刘丽 |
82 |
95 |
| 25 |
... |
|
|
| 26 |
陈伟 |
|
|
| ... |
... |
|
|
| 33 |
吴军 |
|
|
| ... |
... |
|
|
| 42 |
李秋梅 |
|
|
| ... |
... |
|
|
| 46 |
刘宏英 |
|
|
| ... |
... |
|
|
| 72 |
吴小艳 |
|
|
| ... |
... |
|
|
| 78 |
... |
|
|
如果两个同学分别叫 刘丽 刘兰，当加入刘兰时，地址24发生了冲突，我们可以以某种规律使用其它的存储位置，如果选择的一个其它位置仍有冲突，则再选下一个，直到找到没有冲突的位置。选择其它位置的方法有：
１、开放定址法
Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1)
其中m为表长，di为增量序列
如果di值可能为1,2,3,...m-1，称线性探测再散列。
如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2)
称二次探测再散列。
如果di取值可能为伪随机数列。称伪随机探测再散列。
例：在长度为11的哈希表中已填有关键字分别为17,60,29的记录，现有第四个记录，其关键字为38，由哈希函数得到地址为5，若用线性探测再散列，如下：
| 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)线性探测再散列
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
| |
|
|
|
|
60 |
17 |
29 |
|
|
|
(c)二次探测再散列
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
| |
|
|
38 |
|
60 |
17 |
29 |
|
|
|
(d)伪随机探测再散列
伪随机数列为9,5,3,8,1...
２、再哈希法
当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。
３、链地址法
将所有关键字为同义词的记录存储在同一线性链表中。
４、建立一个公共溢出区
假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。
三、哈希表的查找
//开放定址哈希表的存储结构
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);
}
四、总结
处理冲突的要求是什么？