- 浏览: 1584350 次
- 性别:
文章分类
- 全部博客 (2929)
- 非技术 (18)
- Eclipse (11)
- JAVA (31)
- 正则表达式 (0)
- J2EE (4)
- DOS命令 (2)
- WEB前端 (52)
- JavaScript (69)
- 数据库 (8)
- 设计模式 (0)
- JFreechart (1)
- 操作系统 (1)
- 互联网 (10)
- EasyMock (1)
- jQuery (5)
- Struts2 (12)
- Spring (24)
- 浏览器 (16)
- OGNL (1)
- WebService (12)
- OSGi (14)
- 软件 (10)
- Tomcat (2)
- Ext (3)
- SiteMesh (2)
- 开源软件 (2)
- Hibernate (2)
- Quartz (6)
- iBatis (2)
最新评论
哈希表 精讲
一、哈希表的概念及作用
一般的线性表,树中,记录在结构中的相对位置是随机的,即和记录的关键字之间不存在确定的关系,因此,在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上,查找的效率依赖于查找过程中所进行的比较次数。
理想的情况是能直接找到需要的记录,因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和结构中一个唯一的存储位置相对应。
哈希表最常见的例子是以学生学号为关键字的成绩表,1号学生的记录位置在第一条,10号学生的记录位置在第10条...
如果我们以学生姓名为关键字,如何建立查找表,使得根据姓名可以直接找到相应记录呢?
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、直接定址法
例如:有一个从1到100岁的人口数字统计表,其中,年龄作为关键字,哈希函数取关键字自身。
地址 |
01 |
02 |
... |
25 |
26 |
27 |
... |
100 |
年龄 |
1 |
2 |
... |
25 |
26 |
27 |
... |
... |
人数 |
3000 |
2000 |
... |
1050 |
... |
... |
... |
... |
... |
|
|
|
|
|
|
|
|
2、数字分析法
有学生的生日数据如下:
年.月.日
75.10.03
75.11.23
76.03.02
76.07.12
75.04.21
76.02.15
...
经分析,第一位,第二位,第三位重复的可能性大,取这三位造成冲突的机会增加,所以尽量不取前三位,取后三位比较好。
3、平方取中法
取关键字平方后的中间几位为哈希地址。
4、折叠法
将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址,这方法称为折叠法。
例如:每一种西文图书都有一个国际标准图书编号,它是一个10位的十进制数字,若要以它作关键字建立一个哈希表,当馆藏书种类不到10,000时,可采用此法构造一个四位数的哈希函数。如果一本书的编号为0-442-20586-4,则:
|
5864 |
|
5864 |
|
4220 |
|
0224 |
+) |
04 |
+) |
04 |
|
----------- |
|
----------- |
|
10088 |
|
6092 |
|
H(key)=0088 |
|
H(key)=6092 |
|
|
|
|
|
(a)移位叠加 |
|
(b)间界叠加 |
5、除留余数法
取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。
H(key)=key MOD p (p<=m)
6、随机数法
选择一个随机函数,取关键字的随机函数值为它的哈希地址,即
H(key)=random(key) ,其中random为随机函数。通常用于关键字长度不等时采用此法。
三、处理冲突的方法
|
|
成绩一 |
成绩二... |
3 |
... |
|
|
... |
... |
|
|
24 |
刘丽 |
82 |
95 |
25 |
... |
|
|
26 |
陈伟 |
|
|
... |
... |
|
|
33 |
吴军 |
|
|
... |
... |
|
|
42 |
李秋梅 |
|
|
... |
... |
|
|
46 |
刘宏英 |
|
|
... |
... |
|
|
72 |
吴小艳 |
|
|
... |
... |
|
|
78 |
... |
|
|
如果两个同学分别叫 刘丽 刘兰,当加入刘兰时,地址24发生了冲突,我们可以以某种规律使用其它的存储位置,如果选择的一个其它位置仍有冲突,则再选下一个,直到找到没有冲突的位置。选择其它位置的方法有:
1、开放定址法
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...
2、再哈希法
当发生冲突时,使用第二个、第三个、哈希函数计算地址,直到无冲突时。缺点:计算时间增加。
3、链地址法
将所有关键字为同义词的记录存储在同一线性链表中。
<shapetype id="_x0000_t75" stroked="f" filled="f" path="m@4@5l@4@11@9@11@9@5xe" o:preferrelative="t" o:spt="75" coordsize="21600,21600"><stroke joinstyle="miter"></stroke><formulas><f eqn="if lineDrawn pixelLineWidth 0"></f><f eqn="sum @0 1 0"></f><f eqn="sum 0 0 @1"></f><f eqn="prod @2 1 2"></f><f eqn="prod @3 21600 pixelWidth"></f><f eqn="prod @3 21600 pixelHeight"></f><f eqn="sum @0 0 1"></f><f eqn="prod @6 1 2"></f><f eqn="prod @7 21600 pixelWidth"></f><f eqn="sum @8 21600 0"></f><f eqn="prod @7 21600 pixelHeight"></f><f eqn="sum @10 21600 0"></f></formulas><path o:connecttype="rect" gradientshapeok="t" o:extrusionok="f"></path><lock aspectratio="t" v:ext="edit"></lock></shapetype><shape id="_x0000_i1025" style="WIDTH: 235.5pt; HEIGHT: 220.5pt" alt="" type="#_x0000_t75"><imagedata o:href="http://www.bc-cn.net/Article/UploadFDL05/200411/20041112073744336.jpg" src="file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/msohtml1/01/clip_image001.jpg"></imagedata></shape>
4、建立一个公共溢出区
假设哈希函数的值域为[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);
}
相关推荐
哈希表的建立和查找哈希表的建立和查找哈希表的建立和查找哈希表的建立和查找
对一批关键字集合采用开放定址哈希表的存储结构来建立相应的哈希表和完成查找过程。 (1) 熟练掌握哈希表的构造方法 (2) 理解哈希表与其他结构表的实质性差别。
/为班级30个人的姓名设计一个哈希表,假设姓名用汉语拼音表示。要求用除留余数法 构造哈希函数,用线性探测再散列法处理冲突,平均查找长度的上限为2。 编写数据结构和算法来实现。要求:将哈希函数和处理冲突方法...
哈希表应用 设计哈希表实现图书查找系统,完成相应的建表和查表程序。从键盘输入各图书相关信息,分别以图书编号为关键字建立散列表。待填入哈希表的书号至少30个;构造合适的哈希函数。 (1)记录由外部输入。 (2...
哈希表设计程序设计+数据结构实验报告 1.1 针对某个集体中的人名设计一个哈希表,使得平均查找长度不超过R,完成相应的建立和查表程序. 1.2 人名为汉语拼音形式,最长不超过18个字符(如:庄双双 zhuangshuangshuang)...
////采用除留余数法定义哈希表,哈希表长度为10,哈希函数为H(key)=key%13。产生冲突时采用线性探测法实现下面要求的功能。 ////(1)初始化哈希表,置空哈希表 ////(2)在哈希表中查找元素 ////(3)在哈希表中...
哈希表课程设计数据结构实验报告——哈希表设计 针对某个集体中的人名设计一个哈希表,使得平均查找长度不超过R,完成相应的建立和查表程序. 1.2 人名为汉语拼音形式,最长不超过18个字符(如:庄双双 ...
哈希表的概念作用及意义,哈希表的构造方法
哈希表的设计与实现课程设计 问题描述:针对某个单位电话号码簿,设计一个哈希表,并完成相应的建表和查表程序。 基本要求:设每个记录有下列数据项:电话号码、用户名、住址。从键盘输入各记录,以用户名为关键字...
哈希表的设计与实现——链地址法 问题描述: 设计哈希表实现电话号码查找系统。 基本要求: (1)设每个记录有下列数据项:电话号码、用户名、地址; (2)从文件中读取各记录,分别以电话号码和用户名为关键字建立...
问题描述:针对某个单位电话号码簿,设计一个哈希表,并完成相应的建表和查表程序。 基本要求:设每个记录有下列数据项:电话号码、用户名、住址。从键盘输入各记录,以用户名为关键字建立哈希表,哈希函数用除留取...
用C语言实现的哈希表设计,内有姓名列表,只要输入姓名就可得到查到在哈希表中的相应位置
假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数用除留余数法构造,用线性探测再散列法或链地址法处理冲突。
哈希表的设计与实现。设计哈希表实现电话号码查询系统。基本要求:(1)设每个记录有一列数据项:电话号码、用户名、地址(2)从键盘输入各记录,分别以电话号码和用户名为关键字建立哈希表;(3)采用再哈希法解决...
简单哈希表模型。可以助你更好的完成哈希表相关的编程。
哈希表的设计与实现哈希表的设计与实现哈希表的设计与实现
针对某个集体(比如你所在的班级)中的“人名”设计一个哈希表,使得平均查找长度不超过R,完成相应的建表和查表程序。 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2...
哈希表的建立与运用C语言实现哈希表的建立与运用C语言实现哈希表的建立与运用C语言实现哈希表的建立与运用C语言实现哈希表的建立与运用C语言实现
初始化哈希表 清空哈希表 哈希函数 在哈希表中查找元素 在哈希表中插入一个元素 输出哈希表中所有元素
哈希表相关操作实现。对应讲解的博客地址:http://blog.csdn.net/ns_code/article/details/20763801