一、散列表基本概念
1、散列表(hash table) ,也叫哈希表,是根据关键码而直接进行访问的数据结构。也就是说,它通过把关键码映射到表中一个位置
来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
2、若结构中存在关键码为x的记录,则必定在hash(x)的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系hash
为散列函数(hash function),按这个思想建立的表为散列表。
举个例子:
影碟出租店维护一张表格,以电话号码作为关键码,为了提高查找速度,可以用选择哈希表进行存储
假设影碟出租店有一万张光碟,每天借出与归还均不超出500人次。因此哈希表维护500条记录即可。
我们发现真正要存储的记录比关键码总数(假设8位电话,则关键码总数2^8 个)要少得多。
散列地址冲突
3、散列函数是一个压缩映象函数。关键码集合比散列表地址集合大得多。因此有可能经过散列函数的计算,把不同的关键码映射到
同一个散列地址上,这就产生了冲突 (Collision)。即key1≠ key2,而hash(key1)=hash(key2),这种现象称冲突。我们将key1与key2称
做同义词。
4、由于关键码集合比地址集合大得多,冲突很难避免。所以对于散列方法,需要讨论以下两个问题:
对于给定的一个关键码集合,选择一个计算简单且地址分布比较均匀的散列函数,避免或尽量减少冲突;
拟订解决冲突的方案。
散列函数选取原则
5、散列函数的选择有两条标准:简单和均匀
简单指散列函数的计算简单快速,能在较短时间内计算出结果。
均匀指散列函数计算出来的地址能均匀分布在整 个地址空间。若key是从关键字码集合中随机抽取的一个关键码,散列函数能
以等概率均匀地分布在表的地址集{0,1,…,m-1}上,以使冲突最小化。
二、散列函数构造方法
(一)、直接定址法
此类函数取关键码的某个线性函数值作为散列地址:hash ( key ) = a * key + b { a, b为常数 }
这类散列函数是一对一的映射,一般不会产生冲突。但是,它要求散列地址空间的大小与关键码集合的大小相同。
(二)、数字分析法
构造:对关键字进行分析,取关键字的若干位或其组合作哈希地址。
适于关键字位数比哈希地址位数大,且可能出现的关键字事先知道的情况。
例: 有80个记录,关键字为8位十进制数,哈希地址为2位十进制数
(三)、平方取中法
取关键字平方后中间几位作哈希地址。适于关键字位数不定情况。
具体方法:先通过求关键字的平方值扩大相近数的差别,然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间
几位数和乘数的每一位都相关,所以由此产生的散列地址较为均匀。(ps:不理解内码的含义)
(四)、折叠法
此方法把关键码自左到右分成位数相等的几部分,每一部分的位数应与散列表地址位数相同,只有最后一部分的位数可以短一些。
把这些部分的数据叠加起来,就可以得到具有该关键码的记录的散列地址。有两种叠加方法:
移位法 — 把各部分的最后一位对齐相加;
分界法 — 各部分不折断,沿各部分的分界来回折叠,然后对齐相加,将相加的结果当做散列地址。
一般当关键码的位数很多,而且关键码每一位上数字的分布大致比较均匀时,可用这种方法得到散列地址。
示例:设给定的关键码为 key = 23938587841,若存储空间限定 3 位, 则划分结果为每段 3 位. 上述关键码可划分为 4段:
把超出地址位数的最高位删去, 仅保留最低的3位,做为可用的散列地址。
(五)、随机数法
选择一个随机函数,取关键字的随机函数值为它的散列地址,即hash(key) = random(key) ;其中random为伪随机函数,但要保证函
数值是在0到m-1之间。
(六)、除留余数法
设散列表中允许的地址数为 m, 散列函数为:
hash ( key ) = key % p p <= m
若p取100,则关键字159、259、359互为同义词。我们选取的p值应尽可能使散列函数计算得到的散列地址与各位相关,根据经
验,p最好取一个不大于 m,但最接近于或等于 m 的质数 p, 或选取一 个不小于 20 的质因数的合数作为除数(比如8 = 2*2*2,2 是
8 的质因数,8 是合数)
示例:有一个关键码 key = 962148,散列表大小 m = 25,即 HT[25]。取质数 p= 23。散列函数 hash ( key ) = key % p。则散列地址
为 hash ( 962148 ) = 962148 % 23 = 12
可以按计算出的地址存放记录。需要注意的是,使用上面的散列函数计算出来的地址范围是 0到 22,因此,从23到24这几个散列地
址实际上在一开始是不可能用散列函数计算出来的,只可能在处理溢出时达到这些地址。
(七)、乘余取整法
使用此方法时,先让关键码 key 乘上一个常数 A (0 < A < 1),提取乘积的小数部分。然后,再用整数 n 乘以这个值,对结果向下取
整,把它做为散列的地址。散列函数为:
三、常见字符串哈希函数
下面列出常见的8个字符串哈希函数,这些都是计算机科学家们研究出来的,计算出来的哈希地址比较平均,冲突较少,但还是会存
在冲突,另外在使用这些函数时,记得在return 的值后面再 % 地址总数,这样得出的地址才会在范围内。
C++ Code
<nobr>1<br>
2<br>
3<br>
4<br>
5<br>
6<br>
7<br>
8<br>
9<br>
10<br>
11<br>
12<br>
13<br>
14<br>
15<br>
16<br>
17<br>
18<br>
19<br>
20<br>
21<br>
22<br>
23<br>
24<br>
25<br>
26<br>
27<br>
28<br>
29<br>
30<br>
31<br>
32<br>
33<br>
34<br>
35<br>
36<br>
37<br>
38<br>
39<br>
40<br>
41<br>
42<br>
43<br>
44<br>
45<br>
46<br>
47<br>
48<br>
49<br>
50<br>
51<br>
52<br>
53<br>
54<br>
55<br>
56<br>
57<br>
58<br>
59<br>
60<br>
61<br>
62<br>
63<br>
64<br>
65<br>
66<br>
67<br>
68<br>
69<br>
70<br>
71<br>
72<br>
73<br>
74<br>
75<br>
76<br>
77<br>
78<br>
79<br>
80<br>
81<br>
82<br>
83<br>
84<br>
85<br>
86<br>
87<br>
88<br>
89<br>
90<br>
91<br>
92<br>
93<br>
94<br>
95<br>
96<br>
97<br>
98<br>
99<br>
100<br>
101<br>
102<br>
103<br>
104<br>
105<br>
106<br>
107<br>
108<br>
109<br>
110<br>
111<br>
112<br>
113<br>
114<br>
115<br>
116<br>
117<br>
118<br>
119<br>
120<br>
121<br>
122<br>
123<br></nobr>
|
|
unsignedintSDBMHash(char*str)
{ unsignedinthash=0;
while(*str)
{ //equivalentto:hash=65599*hash+(*str++); hash=(*str++)+(hash<<6)+(hash<<16)-hash;
}
return(hash&0x7FFFFFFF)%BUCKETS;
}
unsignedintRSHash(char*str)
{ unsignedintb=378551; unsignedinta=63689; unsignedinthash=0;
while(*str)
{
hash=hash*a+(*str++);
a*=b;
}
return(hash&0x7FFFFFFF);
}
unsignedintJSHash(char*str)
{ unsignedinthash=1315423911;
while(*str)
{
hash^=((hash<<5)+(*str++)+(hash>>2));
}
return(hash&0x7FFFFFFF);
}
unsignedintPJWHash(char*str)
{ unsignedintBitsInUnignedInt=(unsignedint)(sizeof(unsignedint)*8); unsignedintThreeQuarters=(unsignedint)((BitsInUnignedInt*3)/4); unsignedintOneEighth=(unsignedint)(BitsInUnignedInt/8); unsignedintHighBits=(unsignedint)(0xFFFFFFFF)<<(BitsInUnignedInt-OneEighth); unsignedinthash=0; unsignedinttest=0;
while(*str)
{
hash=(hash<<OneEighth)+(*str++); if((test=hash&HighBits)!=0)
{
hash=((hash^(test>>ThreeQuarters))&(~HighBits));
}
}
return(hash&0x7FFFFFFF);
}
unsignedintELFHash(char*str)
{ unsignedinthash=0; unsignedintx=0;
while(*str)
{
hash=(hash<<4)+(*str++); if((x=hash&0xF0000000L)!=0)
{
hash^=(x>>24);
hash&=~x;
}
}
return(hash&0x7FFFFFFF);
}
unsignedintBKDRHash(char*str)
{ unsignedintseed=131;//31131131313131131313etc.. unsignedinthash=0;
while(*str)
{
hash=hash*seed+(*str++);
}
return(hash&0x7FFFFFFF);
}
unsignedintDJBHash(char*str)
{ unsignedinthash=5381;
while(*str)
{
hash+=(hash<<5)+(*str++);
}
return(hash&0x7FFFFFFF);
}
unsignedintAPHash(char*str)
{ unsignedinthash=0; inti;
for(i=0;*str;i++)
{ if((i&1)==0)
{
hash^=((hash<<7)^(*str++)^(hash>>3));
} else
{
hash^=(~((hash<<11)^(*str++)^(hash>>5)));
}
}
return(hash&0x7FFFFFFF);
}
|
下面使用第一个哈希函数,写个小程序测试一下是否会产生冲突:
C++ Code
<nobr>1<br>
2<br>
3<br>
4<br>
5<br>
6<br>
7<br>
8<br>
9<br>
10<br>
11<br>
12<br>
13<br>
14<br>
15<br>
16<br>
17<br>
18<br>
19<br>
20<br>
21<br>
22<br>
23<br>
24<br>
25<br>
26<br>
27<br>
28<br>
29<br>
30<br>
31<br>
32<br>
33<br>
34<br>
35<br>
36<br>
37<br>
38<br>
39<br>
40<br>
41<br>
42<br>
43<br>
44<br>
45<br>
46<br>
47<br>
48<br>
49<br>
50<br></nobr>
|
|
#include<stdio.h>
#defineBUCKETS101
unsignedintSDBMHash(char*str)
{ unsignedinthash=0;
while(*str)
{ //equivalentto:hash=65599*hash+(*str++); hash=(*str++)+(hash<<6)+(hash<<16)-hash;
}
return(hash&0x7FFFFFFF)%BUCKETS;
}
intmain(void)
{ char*keywords[]=
{ "auto","break","case","char","const","continue","default","do", "double","else","enum","extern","float","for","goto","if", "int","long","register","return","short","signed","sizeof","static", "struct","switch","typedef","union","unsigned","void","volatile","while"
};
//哈希表每个地址的映射次数 //0地址的映射次数用count[0]表示 intcount[BUCKETS]={0}; inti; intsize=sizeof(keywords)/sizeof(keywords[0]); for(i=0;i<size;i++)
{
intpos=SDBMHash(keywords[i]);
count[pos]++;
}
for(i=0;i<size;i++)
{
intpos=SDBMHash(keywords[i]);
printf("%-10s%d%d\n",keywords[i],pos,count[pos]);
}
return0;
}
|
可以看出,确实会产生冲突,比如有3个词语 default、extern、for 都映射到了地址16上。
分享到:
相关推荐
哈希函数的构造方法:1)直接定地址法 2)数字分析法 3)平方取中法 4)折叠法 5)除留余数法 6)随机数法 处理冲突的方法:1)开放定址法(线性探测再散列,二次探测再散列,伪随机探测再散列) 2)再哈希法 ...
public成员包括构造函数、析构函数和复制构造函数以及=重载函数,其它成员函数主要有:traver(遍历散列表)、show()(打印出哈希表所存的元素)返回值为bool类型的函数search\insert\Delete。search函数(查询关键字为...
选取哈西函数h(k)=k%11,用线性探测在散列方法处理冲突。是在0-10的散列地址中,对关键序列(22,41,53,46,30,01,67)构造哈希表并求等概率情 况下查找成功与不成功过的平均查找长度
针对某个集体中人名设计一个哈希表,使得平均查找长度不超过R,并完成相应的建表和查表程序。假设人名为中国人姓名的汉语拼音形式。...哈希函数用除留余数法构造,用线性探测再散列法或链地址法处理冲突。
(4)哈希函数用除留余数法构造,采用二次探测再散列法解决冲突; (5)查找并显示给定电话号码的记录; (6)通讯录信息保存。 测试数据 取周围熟悉的30个人的姓名及相关信息。 实现提示 人名长度均不超过19个...
(1) 从教科书上介绍的集中哈希函数构造方法中选出适用者并设计几个不同的哈希函数,比较他们的地址冲突率(可以用更大的名字集合作实验)。 (2) 研究这30个人名的特点,努力找一个哈希函数,使得对于不同的拼音...
散列表的经常使用构造方法有:(1)直接定址法(2)数字分析法(3)平方取中法(4)折叠法(5)随机数法(6)除留余数法散列表函数设计好的情况下,能够降低冲突,可是无法全然避免冲突。常见有冲突处理方法有:
构造合适的哈希函数。 (1)记录由外部输入。 (2)生成的哈希表结果以图形示意形式输出。 (3)分别采用线性法、随机法、溢出法解决冲突,比较不同方法的冲突率,计算不同方法的平均查找长度。 (4)查找并显示给定...
构造合适的哈希函数。 1) 记录由外部输入。 2) 将生成的哈希表结果输出。 3) 分别采用线性法、随机法、溢出法解决冲突,比较不同方法的冲突率,计算不同方法的平均查找长度。 4) 查找并显示给定图书编码的记录。
在程序中我们对关键字key应用散列函数H(key)来判断关键字key是否在散列表中,即计算H(key)的值,H(key)值确定所存数据在散列表中的位置。这样一个数据元素的地址是通过函数来计算的,所以数据元素并不需要按照特定的...
又称为哈希表、散列表、或是杂凑表,它是一种十分实用的查找技术,具有极高的查找效率。 Hash函数的构造方法 对于Hash函数的构造,没有特定的要求,所以方法很多,只是我们需要了解,什么样的哈希函数,才叫好的Hash...
使用一组自定义的初始化选项将散列表工厂定义为全局或本地定义函数的方法。 请参阅下面的define-hash-factory , make-hash-factory和*hash-factory-defaults* 。 可读取的安装程序,用于定义与哈希表工厂的便携式...
设计一个构造函数,当对象结束时,要释放整个二叉搜索树所占的内存空间(提示,通过后序遍历算法找到叶结点,并删除叶结点,不断重复此过程,直到整科树为空); 2、实现1所要求的代码后,运行设计好的代码,将...