哈希表的概念
哈希表又称散列表,是一种线性的存储结构。是根据关键码值(Key Value)而直接进行访问的数据结构。它通过把关键码值映射到哈希表中的一个位置来访问记录,以加快查找的速度。这个映射函数就做散列函数,存放记录的数组叫做散列表。
哈希表存储思路
以数据中每个元素的关键字K为自变量,通过散列函数h(k)计算出函数值,以该函数值作为一块连续存储空间的的单元地址,将该元素存储到函数值对应的单元中。但是存在这样的问题,对于两个关键字K1和k2,可能k1!=k2,但是h(k1)==h(k2),此时就发生了冲突,这种叫做哈希冲突。
哈希函数的构造方法
构造哈希函数的目标是使得到的哈希地址尽可能均匀地分布在n个连续内存单元地址,同时使计算过程尽可能简单,以达到尽可能高的时间效率。根据关键字的结构和分布的不同,可构造出许多不同的哈希函数。
1.直接定址法
直接定址法是以关键字k本身或关键字加上某个数字常量c作为哈希地址的方法。哈希函数为
h(k)=k+c
这种哈希函数计算简单,并且不可能发生冲突。若关键字分布不连续将造成内存单元的大量浪费。
2.数字分析法
分 析一组数据,比如一组员工的出生年月,这时我们发现出生年月的前几位数字一般都相同,因此,出现冲突的概率就会很大,但是我们发现年月日的后几位表示月 份和具体日期的数字差别很大,如果利用后面的几位数字来构造散列地址,则冲突的几率则会明显降低.因此数字分析法就是找出数字的规律,尽可能利用这些数据 来构造冲突几率较低的散列地址
3.除留余数法
除留余数法是用关键字k除以某个不大于哈希表长度m的数p所得的余数作为哈希地址方法,哈希函数为:
h(k)=k %p(取余)
其中,p<=m;
除留余数法是最经常使用的一种哈希函数。这种方法关键是选好p,研究表明,p应该选取不大于m的素数时效果最好
哈希表冲突处理
1.开放定址法
当 关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址 p2,…,直到找出一个不冲突的哈希地址pi ,将相应元素存入其中。这种方法有一个通用的再散列函数形式:Hi=(H(key)+di)%m i=1,2,…,n,其中H(key)为哈希函数,m 为表长,di称为增量序列。增量序列的取值方式不同,相应的再散列方式也不同。主要有以下两种:
(1)线性探索法
线性探索法是从发生冲突的地址d开始,一次探索d的下一个地址(当到达表尾时,下一个地址就是表头),直到找到空闲单元为止。线性探索的数学表达式为:
d0=h(k);
di=(d0+i )% m(取向下一个地址单元)
线性探索容易产生堆积问题。
(2)平方探测法
设发生冲突的地址为d,则平方探测法的探测序列为d+1^2;d+2^2;d+3^2,......其数学表达式为:
d0=h(k);
di=(d0+i^2)%m
平方探测法是一种比较好的处理冲突方法,可以避免出现堆积问题。缺点是不能探索到哈希表上的所有单元。
下面使用除留余数法加线性探索法来建立查找哈希表
设哈希表长度为13,插入数据为:{16,74,60,43,54,90,46,31,29,88,77};
根据除留余数法应取不大于哈希表长度的素数,所有取p=13;
定义哈希表结构:
#define MAX 13//哈希表长度 #define p 13 //不大于哈希表长度的素数 #define NULLKEY -1 //空关键字 #define DELKEY -2 //删除关键字 //除留余数法加线性探索法建立哈希表 struct node { int key;//关键字 string data;//数据域 int num;//探测次数 //初始化探索次数为0,关键字为空关键字 node() { num=0; key=NULLKEY; } };
建立哈希表的代码为:
//建立哈希表 void Create(node hash[]) { int data[11]={16,74,60,43,54,90,46,31,29,88,77};//生成哈希表数据 for(int i=0;i<11;i++) { int count=0; int temp=data[i]; //关键字插入 while(true) { if(hash[temp%p].key==NULLKEY||hash[temp%p].key==DELKEY)//没冲突 { count++; hash[temp%p].key=data[i];//关键字插入 hash[temp%p].num=count;//探索次数 break; } else { temp=(temp+1)%p;//线性探查法 count++;//探测次数加一 } } } for(int i=0;i<13;i++) cout<<"下标: "<<i<<" key : "<<hash[i].key<<" 探索次数: "<<hash[i].num<<endl; }
哈希表查询
//哈希表查找 int Search(node hash[],int key) { int adr=key%p; while(hash[adr].key!=NULLKEY&&hash[adr].key!=key) { adr=(adr+1)%p; } if(hash[adr].key==key) //查找成功返回地址 return adr; else //查找失败 return -1; }
调用main函数为:
int main() { node hash[MAX];//哈希表数组 Create(hash); int result=Search(hash,88); cout<<result<<endl; return 0; }
最后运行结果为:
2.拉链法
拉链法是把所有同义词用链表连接起来的方法,这样,哈希表每个单元中存放的不再是记录本身,而是相应同义词单链表的头指针。拉链法需要额外的空间来存放指针
拉链法的优点与开放定址法相比,拉链法有如下几个优点:
(1)拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短;
(2)由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况;
(3)开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取 α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间;
(4) 在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表,删除结点不能简单地 将被删结点的空间置为空,否则将截断在它之后填入散列表的同义词结点的查找路径。这是因为各种开放地址法中,空地址单元(即开放地址)都是查找失败的条 件。 因此在用开放地址法处理冲突的散列表上执行删除操作,只能在被删结点上做删除标记,而不能真正删除结点。
拉链法的缺点
拉链法的缺点是:指针需要额外的空间,故当结点规模较小时,开放定址法较为节省空间,而若将节省的指针空间用来扩大散列表的规模,可使装填因子变小,这又减少了开放定址法中的冲突,从而提高平均查找速度。
拉链法的实现使用链表实现,实现过程比较简单,这里就不再编写拉链法实现的代码了。
相关推荐
输入:待哈希数据序列 功能要求:输出哈希方法和解决冲突的方法(文字输出),输出哈希表
建立哈希表查找c++中32个关键字,其中哈希表长为M=101 32个关键字为auto break case char const continue default do double else enum extern float for goto if int long register return short signed sizeof ...
程序先调用自己写的Create函数创建一个长度为13的哈希表,原始数据是:{10,9,8,7,5,4,6,3,2,1,95},长度为11,这个程序使用的是除留余数法,构建的哈希表为:{0,1,2,3,4,5,6,7,8,9,10,95,0}. 然后再调用Haxi_Sou...
数据结构课程设计-综合查找算法(顺序查找、折半查找、二叉排序树、哈希表) 可以在Microsoft Visual C++ 上运行没有错误 包括论文word文档,答辩的ppt等
哈希表算法实现的C语言源程序 数据结构课程设计用
Python版数据结构与算法-查找算法源代码,含顺序搜索、二分查找、哈希表搜索、树(图)数据查找源代码
石家庄铁道大学 刘立嘉 算法与数据结构 实验五 哈希表设计
强调使用masm6.15或以上编译器编译 用masm5会跳转越界 the 20 keywords is: 7,13,12,37,44,56,68,32,58,35,19,21,23,47,27 -',0dh,0ah db '49,22,66,5,63.The mod data p is 17 . the listnum is 20....
合工大数据结构C++实验报告拉链法哈希表查找算法
1.1 针对某个集体中的人名设计一个哈希表,使得平均查找长度不超过R,完成相应的建立和查表程序. 1.2 人名为汉语拼音形式,最长不超过18个字符(如:庄双双 zhuangshuangshuang). 1.3 假设待填入哈希表的人名有30个,...
静态查找表技术 依据顺序查找算法和折半查找算法的特点,对下面的两个查找表选择一个合适的算法 ,设计出完整的C源程序。并完成问题: 查找表1 : { 8 ,15 ,19 ,26 ,33 ,41 ,47 ,52 ,64 ,90 } ,查找key =...
一 实践目的与要求 - 4 - 1.1实践目的 - 4 - 1.2实践要求 - 4 - 二 顺序查找的分析、程序、及运行结果 - 4 - ...5.3哈希查找算法描述 - 13 - 5.4运行结果 - 15 - 六 致谢 - 15 - 七 附录: - 16 - 八 参考文献 - 19 -
哈希表及其查找算法.doc
10.s8算法2-4 链表 哈希表 11.s8算法2-5 算法题 12.S8设计模式-1 设计模式简介 13.S8设计模式-2 创建型模式 14.S8设计模式-3 结构型模式 15.S8设计模式-4 行为型模式 16.5 设计模式总结 17.6 二叉树 18.7 算法进阶 2...
任务:针对某个集体(比如你所在的班级)中的“姓名”设计一个哈希表,使得平均查找长度不超过R,完成相应的建表和查表程序。 要求:假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的...
笔者在广东电信公用电话管理中心从事的”签约分销商售卡话务”统计中,巧用哈希表来实现大量数据在众多签约分销商售卡记录中的数据查找,将整个查找的总长度较折半查找降低了一个数量级,大大提高了数据查找的效率。...
几种常用查找算法的比较,内含顺序查找、二分查找、二叉树查找、哈希表查找。
从头到尾解析hash表算法,讲得很详细,包括哈希表的建立以及冲突解决,还有更加深层的结构
国外经典教材 数据结构与算法----面向对象的C++模式 ...8 散列,哈希表与分散表 9树 10查找树, 11堆和优先队列 12集合,多重集和分区 13动态存储分配 14 算法模式和问题求解 15 排序算法和排序器 16 图和图算法
针对已有模式匹配技术的不足进行研究,提出了THT-MSMA多模式匹配算法,该算法采用双哈希表来减少尝试比较的次数。当模式串没有公共前缀,则只需在第一个哈希表中查找;若模式串有公共前缀,则需要在两个哈希表中依次...