前些天胡哥给讲哈希表,悔恨自己没提前看下书,导致后来小伙伴们登台讨论的热火朝天时自己只能充当观众,那酸爽,唉...
当天回家恶补数据结构,发现哈希表其实还是挺容易理解的,就是在实现上面会感觉无从下手,因为自己还没有真正处理过大数据(虽然最近在研究大数据~~),只好自己敲个小程序cos下。
当天在胡哥课上除了哈希表基本思想外,印象最深的就是哈希表的冲突问题,当时听的时候感觉挺高大上,不理解冲突是个什么东东,为什么会发生?后来想了下,我去,不就是初中学过的抽屉原理吗,忘记了的小伙伴请回校复读,哈哈。
额,顺便插一句,推荐大家看一下下面这个视频http://v.163.com/movie/2010/12/R/E/M6UTT5U0I_M6V2TG4RE.html,
麻省理工关于哈希算法的公开课,那光头讲的很细致,通俗易懂吧,楼主耐着性子看完后觉得这4664秒还是挺值得的,想感受下的同学不妨看下。
<!--EndFragment-->好了,言归正传,下面主要说一下自己堆哈希表理解最深的构造方法与解决冲突法方法。
<!--EndFragment--> 哈希表的基本构造方法
构造哈希表的方法是:设要存储的数据元素个数为n,设置一个长度为m(m≥n)的连续内存单元(即数组),分别以每个数据元素的关键字Ki(0≤i≤n-1)为自变量,以哈希函数h(Ki)值为该数据元素在数组中的下标值存储该数据元素。
把构造哈希表时Ki≠Kj(i≠j),但h(Ki)=h(Kj)的现象称作哈希冲突。
哈希表的构造方法百科上介绍了许多,比如:数字分析,平方取中,伪随机,折叠啊,取余啊。
这里说一下楼主理解最深的折叠法与平方取中法。
折叠法是按哈希表地址位数将关键字分成位数相等的几部分(最后一部分可以较短),然后将这几部分相加,舍弃最高进位后的结果就是该关键字的哈希地址。折叠法是从一端向另一端沿分割界来回折叠(奇数段为正序,偶数段为倒序),然后将各段相加。
例如:key=123 603 247 112 020 65,哈希表长度为1000,则应把关键字分成3位一段,在此舍去最低的两位65,分别进行移位叠加和折叠叠加,求得哈希地址为907。
1 2 3
3 0 6
2 4 7
2 1 1
+)0 2 0
——————
9 0 7
平方取中
如果是以字符串形式出现该怎么办呢?
例:我们把英文字母在字母表中的位置序号作为该英文字母的内部编码。例如K的内部编码为11,E的内部编码为05,Y的内部编码为25,A的内部编码为01, B的内部编码为02。由此组成关键字“KEYA”的内部代码为11052501,同理我们可以得到关键字“KYAB”、“AKEY”、“BKEY”的内部编码。之后对关键字进行平方运算后,取出第7到第9位作为该关键字哈希地址。
关键字 |
内部编码 |
内部编码的平方值 |
H(k)关键字的哈希地址 |
KEYA |
11050201 |
122157778355001 |
778 |
KYAB |
11250102 |
126564795010404 |
795 |
AKEY |
01110525 |
001233265775625 |
265 |
BKEY |
02110525 |
004454315775625 |
315 |
<!--EndFragment-->
冲突问题
通过构造性能良好的哈希函数,可以减少冲突,但一般不可能完全避免,因此解决冲突是哈希表的另一个关键问题。常用的解决办法有;开放地址法,再哈希法,链地址法以及建立公共溢出区。
开放地址法的基本思想是:当关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,…,直到找出一个不冲突的哈希地址pi ,将相应元素存入其中。这种方法有一个通用的再散列函数形式:
Hi=(H(key)+di)% m i=1,2,…,n
其中H(key)为哈希函数,m 为表长,di称为增量序列。增量序列的取值方式不同,相应的再散列方式也不同。
这里说一下线性探测再散列:(后文代码中会体现)
dii=1,2,3,…,m-1
特点:冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表。
再哈希法(Rehash)是同时构造多个不同的哈希函数:
Hi=RH1(key) i=1,2,…,k
当哈希地址Hi=RH1(key)发生冲突时,再计算Hi=RH2(key)……,直到冲突不再产生。比较费时。
关于布隆过滤器,像了解的同学可以到下面网址学习,楼主也只是简单了解下,就不再啰嗦
http://www.cnblogs.com/dolphin0520/archive/2012/11/10/2755089.html
下面是关于哈希表的简单代码
#include<iostream> using namespace std; typedef int KeyType; //设关键字域为整形,需要修改类型时,只需修改这里就可以 const int NULLKEY=0; //NULLKEY表示该位置无值 int c=0; //用来统计冲突次数 struct Elemtype //数据元素类型 { KeyType key; int ord; }; int hashsize[]={11,19,29,37,47}; //hash表容量递增表 int Hash_length=0;//hash表表长 class HashTable { private: Elemtype *elem; //数据元素数组,动态申请 int count;// 当前数据元素个数 int size; //决定hash表的容量为第几个,hashsize[size]为当前hash容量 public: int Init_HashTable() //初始化哈希表 { int i; count=0; size=0; //初始化容量为hashsize[0]=11 Hash_length=hashsize[0]; elem=new Elemtype[Hash_length]; if(!elem) { cout<<"内存申请失败"<<endl; exit(0); } for(i=0;i<Hash_length;i++) elem[i].key=NULLKEY; return 1; } void Destroy_HashTable() { delete[]elem; elem=NULL; count=0; size=0; } unsigned Hash(KeyType k) //hash函数的一种(取模法) { return k%Hash_length; } void Collision(int &p,int d) //解决冲突 { p=(p+d)%Hash_length; //采用开放地址法里的线性探测 } bool Search_Hash(KeyType k,int &p) //查找 { //在开放地址hash表中查找关键字等于k的元素 //若找到用p表示待查数据,查找不成功时,p指向的是可插入地址 c=0; p=Hash(k); //求hash地址 while(elem[p].key!=NULLKEY && elem[p].key!=k) { c++; if(c<Hash_length) Collision(p,c); else return 0; //表示查找不成功 } if(elem[p].key==k) return 1; else return 0; } int Insert_Hash(Elemtype e) //插入 { //在查找不成功的情况下将k插入到hash表中 int p; if(Search_Hash(e.key,p)) return -1; //表示该元素已在hash表中 else if(c<hashsize[size]/2) //冲突次数未达到上限 { //插入e elem[p]=e; count++; return 1; } else ReCreate_HashTable(); // 重建hash表 return 0; //插入失败 } void ReCreate_HashTable() //重建hash表 { int i,count2=count; Elemtype *p,*elem2=new Elemtype[count]; p=elem2; cout<<"____重建hash表_____"<<endl; for(i=0;i<Hash_length;i++) //将原有元素暂存到elem2中 if(elem[i].key!=NULLKEY) *p++=*(elem+i); count=0; size++; //hash容量增大 Hash_length=hashsize[size]; p=new Elemtype[Hash_length]; if(!p) { cout<<"空间申请失败"<<endl; exit(0); } elem=p; for(i=0;i<Hash_length;i++) elem[i].key=NULLKEY; for(p=elem2;p<elem2+count2;p++) //将原有元素放回新表 Insert_Hash(*p); } void Traverse_HashTable() { cout<<"哈希地址0->"<<Hash_length-1<<endl; for(int i=0;i<Hash_length;i++) if(elem[i].key!=NULLKEY) cout<<"元素的关键字值和它的标志分别是:"<<elem[i].key<<" "<<elem[i].ord<<endl; } void Get_Data(int p) { cout<<"元素的关键字值和它的标志分别是:"<<elem[p].key<<" "<<elem[p].ord<<endl; } }; int main() { Elemtype r[12]={{17,1},{60,2},{29,3},{38,4},{1,5},{2,6},{3,7},{4,8},{5,9},{6,10},{7,11},{8,12}}; HashTable H; int i,p,j; KeyType k; H.Init_HashTable(); for(i=0;i<11;i++) //插入前11个记录 { j=H.Insert_Hash(r[i]); if(j==-1) cout<<"表中已有关键字为"<<r[i].key<<" "<<r[i].ord<<"的记录"<<endl; } cout<<"按哈希地址顺序遍历哈希表"<<endl; H.Traverse_HashTable(); cout<<endl; cout<<"输入要查找的记录的关键字:"; cin>>k; j=H.Search_Hash(k,p); if(j==1) H.Get_Data(p); else cout<<"无此记录"<<endl; j=H.Insert_Hash(r[11]); //插入最后一个元素 if(j==0) { cout<<"插入失败"<<endl; cout<<"需要重建哈希表才可以插入"<<endl; cout<<"____重建哈希表____"<<endl; H.Insert_Hash(r[i]); //重建后重新插入 } cout<<"遍历重建后的哈希表"<<endl; H.Traverse_HashTable(); cout<<endl; cout<<"输入要查找的记录的关键字:"; cin>>k; j=H.Search_Hash(k,p); if(j==1) H.Get_Data(p); else cout<<"该记录不存在"<<endl; cout<<"____销毁哈希表____"<<endl; H.Destroy_HashTable(); return 0; }
<!--EndFragment--><!--EndFragment--><!--EndFragment--><!--EndFragment--><!--EndFragment-->
相关推荐
哈希表的建立和查找哈希表的建立和查找哈希表的建立和查找哈希表的建立和查找
对一批关键字集合采用开放定址哈希表的存储结构来建立相应的哈希表和完成查找过程。 (1) 熟练掌握哈希表的构造方法 (2) 理解哈希表与其他结构表的实质性差别。
/为班级30个人的姓名设计一个哈希表,假设姓名用汉语拼音表示。要求用除留余数法 构造哈希函数,用线性探测再散列法处理冲突,平均查找长度的上限为2。 编写数据结构和算法来实现。要求:将哈希函数和处理冲突方法...
////采用除留余数法定义哈希表,哈希表长度为10,哈希函数为H(key)=key%13。产生冲突时采用线性探测法实现下面要求的功能。 ////(1)初始化哈希表,置空哈希表 ////(2)在哈希表中查找元素 ////(3)在哈希表中...
哈希表设计程序设计+数据结构实验报告 1.1 针对某个集体中的人名设计一个哈希表,使得平均查找长度不超过R,完成相应的建立和查表程序. 1.2 人名为汉语拼音形式,最长不超过18个字符(如:庄双双 zhuangshuangshuang)...
哈希表课程设计数据结构实验报告——哈希表设计 针对某个集体中的人名设计一个哈希表,使得平均查找长度不超过R,完成相应的建立和查表程序. 1.2 人名为汉语拼音形式,最长不超过18个字符(如:庄双双 ...
哈希表应用 设计哈希表实现图书查找系统,完成相应的建表和查表程序。从键盘输入各图书相关信息,分别以图书编号为关键字建立散列表。待填入哈希表的书号至少30个;构造合适的哈希函数。 (1)记录由外部输入。 (2...
哈希表的概念作用及意义,哈希表的构造方法
哈希表的设计与实现课程设计 问题描述:针对某个单位电话号码簿,设计一个哈希表,并完成相应的建表和查表程序。 基本要求:设每个记录有下列数据项:电话号码、用户名、住址。从键盘输入各记录,以用户名为关键字...
用C语言实现的哈希表设计,内有姓名列表,只要输入姓名就可得到查到在哈希表中的相应位置
问题描述:针对某个单位电话号码簿,设计一个哈希表,并完成相应的建表和查表程序。 基本要求:设每个记录有下列数据项:电话号码、用户名、住址。从键盘输入各记录,以用户名为关键字建立哈希表,哈希函数用除留取...
简单哈希表模型。可以助你更好的完成哈希表相关的编程。
哈希表的设计与实现——链地址法 问题描述: 设计哈希表实现电话号码查找系统。 基本要求: (1)设每个记录有下列数据项:电话号码、用户名、地址; (2)从文件中读取各记录,分别以电话号码和用户名为关键字建立...
假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数用除留余数法构造,用线性探测再散列法或链地址法处理冲突。
哈希表的设计与实现哈希表的设计与实现哈希表的设计与实现
针对某个集体(比如你所在的班级)中的“人名”设计一个哈希表,使得平均查找长度不超过R,完成相应的建表和查表程序。 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2...
初始化哈希表 清空哈希表 哈希函数 在哈希表中查找元素 在哈希表中插入一个元素 输出哈希表中所有元素
哈希表的设计与实现。设计哈希表实现电话号码查询系统。基本要求:(1)设每个记录有一列数据项:电话号码、用户名、地址(2)从键盘输入各记录,分别以电话号码和用户名为关键字建立哈希表;(3)采用再哈希法解决...
哈希表--链表 哈希表--链表 哈希表--链表 哈希表--链表哈希表--链表 哈希表--链表哈希表--链表 哈希表--链表哈希表--链表 哈希表--链表哈希表--链表 哈希表--链表
哈希表相关操作实现。对应讲解的博客地址:http://blog.csdn.net/ns_code/article/details/20763801