哈希表的C++实现
程序员文章站
2022-04-02 08:02:16
哈希表的几个概念:
映像:由哈希函数得到的哈希表是一个映像。
冲突:如果两个关键字的哈希函数值相等,这种现象称为冲突。
处理冲突的几个方法:
1、开放地址法:用开放地址处理...
哈希表的几个概念:
映像:由哈希函数得到的哈希表是一个映像。
冲突:如果两个关键字的哈希函数值相等,这种现象称为冲突。
处理冲突的几个方法:
1、开放地址法:用开放地址处理冲突就是当冲突发生时,形成一个地址序列,沿着这个序列逐个深测,直到找到一个“空”的开放地址,将发生冲突的关键字值存放到该地址中去。
例如:hash(i)=(hash(key)+d(i)) MOD m (i=1,2,3,......,k(k
根据增量序列的取法不同,可以得到不同的开放地址处理冲突探测方法。
有线性探测法、二次方探测法、伪随机探测法。
2、链地址法:把所有关键字为同义词的记录存储在一个线性链表中,这个链表成为同义词链表,即把具有相同哈希地址的关键字值存放在同义链表中。
3、再哈希表:费时间的一种方法
下面是代码:
文件"myhash.h"
#include 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() //构造一个空hash表 { int i; count=0; size=0; //初始化容量为hashsize[0]=11 Hash_length=hashsize[0]; elem=new Elemtype[Hash_length]; if(!elem) { cout<<"内存申请失败"<测试函数"main.cpp"
#include"myhash.h" 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<<"表中已有关键字为"<;>
上一篇: 首销5分钟破30万!Redmi K40系列今日再次开售:1999元起
下一篇: 做皮蛋为什么要用石灰