频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
哈希表的C++实现
2016-07-11 09:09:00         来源:uestc_summer  
收藏   我要投稿

哈希表的几个概念:

映像:由哈希函数得到的哈希表是一个映像。

冲突:如果两个关键字的哈希函数值相等,这种现象称为冲突。

处理冲突的几个方法:

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<<"表中已有关键字为"<
点击复制链接 与好友分享!回本站首页
相关TAG标签 哈希 C++
上一篇:C++内存模型
下一篇:关于c#调用c/c++ dll遇到的问题总结
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站