热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

【数据结构与算法】HashTable相关操作实现(附完整源码)

转载请注明出处:http:blog.csdn.netns_codearticledetails20763801前言学过Java的人肯定对Hash这个词非常之熟悉,HashTable

转载请注明出处:http://blog.csdn.net/ns_code/article/details/20763801


前言

    学过Java的人肯定对Hash这个词非常之熟悉,HashTable、HashSet、HashMap等都是对哈希表的封装或改进。这次我们来看下哈希表用C语言表示的封装实现。


哈希表

    哈希表又叫散列表,是实现字典操作的一种有效数据结构。哈希表的查询效率极高,在没有冲突(后面会介绍)的情况下不需经过任何比较,一次存取便能得到所查记录,因此理想情况下,查找一个元素的平均时间为O(1)。

    哈希表就是描述key—value对的映射问题的数据结构,这在Java中大家都知道,更详细的描述是:在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字与哈希表中唯一一个存储位置相对应。我们称这个对应关系f为哈希函数,这个存储结构即为哈希表。

    直接寻址表

    当关键字的全域U比较小时,直接寻址是一种简单而有效的技术,它的哈希函数很简单:f(key) = key,即关键字大小直接与元素所在的位置序号相等。另外,如果关键字不是自然数,我们需要通过某种手段将其转换为自然数,比如可以将字符关键字转化为其在字母表中的序号作为关键字。直接寻址法不会出现两个关键字对应到同一个地址的情况,既不会出现f(key1) = f(key2)的情况,因此不用处理冲突,这便是其优点所在。

    散列表

    直接寻址的缺点非常明显,如果全域U很大,则在一台标准的计算机可用内存容量中,要存储大小为U的一张表也许不太实际,而且,实际需要存储的关键字集合K可能相对U来说很小,这时散列表需要的存储空间要比直接表少很多。散列表通过散列函数f计算出关键字key在槽的位置。散列函数f将关键字域U映射到散列表T[0...m-1]的槽位上。但是这里会存在一个问题:若干个关键字可能映射到了表的同一个位置处(算法导论上名其曰“”),我们称这种情形为冲突。当然理想的方法是尽量避免冲突,我们可以尽可能第将关键字通过f随即地映射到散列表的每个位置上。


哈希函数

    哈希函数的构造方法很多,最好的情况是:对于关键字结合中的任一个关键字,经哈希函数映射到地址集合中任何一个地址的概率相等,也就是说,关键字经过哈希函数得到一个随机的地址,以便使一组关键字的哈希地址均匀分布在整个地址空间中,从而减少冲突。同样,由于多数哈希函数都是假定关键字的全域为自然数集N={0、1、2....},因此所给关键字如果不是自然数,就要先想办法将其转换为自然数。下面我们就来看常用的哈希函数。

    直接定址法

    对应前面的直接寻址表,关键字与哈希表中的地址有着一一对应关系,因此不需要处理冲突。

    除法散列法

    哈希函数如下:

f(key)= key%m 

    即对所给关键字key取余,这里m必须不能大于哈希表的长度len,通常m取一个不太接近2的整数次幂的素数是一个较好的选择。

    乘法散列法

    用关键字key先乘上A(0

f(key)= floor(m*(key*A%1))

    通常,A=(sqrt(5)-1)/2 = 0.6180339877...(黄金分割点)是个比较理想的值。

    其他还有一些,诸如数字分析法、折叠法、全域散列法等,这里不再一一介绍,有兴趣了解的可以参考相关书籍(其实我们一般用的比较多的可能也就是除法散列法和乘法散列法)。


冲突处理

    但我们前面提到,为了节省空间,表中槽的数目应该是小于关键字的数目的,因此完全避免冲突是不可能的。下面介绍两种解决冲突的方法:链接法和开放定址法。

    链接法

    链接法的思路很简单:如果多个关键字映射到了哈希表的同一个位置处,则将这些关键字记录在同一个线性链表中,挂在该位置处,如下图所示:


    图中,关键字k1和k4映射到了哈希表的同一个位置处,k5、k2和k7映射到了哈希表的同一个位置处。另外,为了更快地删除某个元素,可以将链表设计为双向链表。后面的代码中我们采用的是单向链表。

    开放定址法

    在开放定址法中,所有的元素都存放在散列表中,也即是说,每个表项或包含动态集合的一个元素,或为空。该方法采用如下公式记性再散列:

F(key,i) = (f(key) + i)%len

    其中,f(key)为哈希函数,len为哈希表长,i为增量序列,它可能有如下三种情况:

    1)i = 1,2,3...m-1

    2)i = 1,-1,4,-4,9,-9...k^2,-k^2

    3)i为伪随机序列

    采用第一种序列的叫做线性探测再散列,采用第二种序列的叫做二次探测再散列,采用第三种序列的叫做随机探测再散列。说白了,就是在发生冲突时,将关键字应该放入的位置向前或向后移动若干位置,比如采取第一种序列时,如果遇到冲突,就向后移动一个位置来检测,如果还发生冲突,继续向后移动,直到遇到一个空槽,则将该关键字插入到该位置处。

    线性探测比较容易实现,但是它存在一个问题,称为一次群集。随着连续被占用的槽不断增加,平均查找时间也随之不断增加,群集现象很容易出现,这是因为当一个空槽前有i个满槽时,该空槽为下一个将被占用的概率为(i+1)len。

    同样采用二次探测的方法,会产生二次群集,因为每次遇到冲突时,寻找插入位置时都是在跳跃性前进或后退,因此这个相对于一次群集来说,比较轻度。


代码实现

    下面我们要来看下代码的实现了,我们这里采用链接法来处理冲突,因此描述数据结构的h文件的代码如下:

#define M 7//哈希函数中的除数,必须小于等于表长typedef int ElemType;

/*
该哈希表采用链接法解决冲突问题
*/
typedef struct Node
{//Node为链表节点的数据结构
ElemType data;
struct Node *next;
}Node,*pNode;

typedef struct HashNode
{//HashNode为哈希表的每个槽的数据结构
pNode first;//first指向链表的第一个节点
}HashNode,*HashTable;

//创建哈希表
HashTable create_HashTable(int);

//在哈希表中查找数据
pNode search_HashTable(HashTable, ElemType);

//插入数据到哈希表
bool insert_HashTable(HashTable,ElemType);

//从哈希表中删除数据
bool delete_HashTable(HashTable,ElemType);

//销毁哈希表
void destroy_HashTable(HashTable,int);
    我们需要先建立一个空哈希表,而后可能要执行插入、删除、查询等相关操作,最后要销毁哈希表,因此相关函数的实现代码如下:

#include#include#include "data_structure.h"/*创建一个槽数为n的哈希表*/HashTable create_HashTable(int n){int i;HashTable hashtable = (HashTable)malloc(n*sizeof(HashNode));if(!hashtable){printf("hashtable malloc faild,program exit...");exit(-1);}//将哈希表置空for(i=0;idata != data)pCur = pCur->next;return pCur;}/*向哈希表中插入数据data,如果data已存在,则返回fasle,否则,插入对应链表的最后并返回true,其中哈希函数为H(key)=key%M*/bool insert_HashTable(HashTable hashtable,ElemType data){//如果已经存在,返回falseif(search_HashTable(hashtable,data))return false;//否则为data分配空间pNode pNew = (pNode)malloc(sizeof(Node));if(!pNew){printf("pNew malloc faild,program exit...");exit(-1);}pNew->data = data;pNew->next = NULL;//将节点插入到对应链表的最后pNode pCur = hashtable[data%M].first;if(!pCur)//插入位置为链表第一个节点的情况hashtable[data%M].first = pNew;else//插入位置不是链表第一个节点的情况{//只有用pCur->next才可以将pNew节点连到链表上,//用pCur连不到链表上,而是连到了pCur上//pCur虽然最终指向链表中的某个节点,但是它并不在链表中while(pCur->next)pCur = pCur->next;pCur->next = pNew;}return true;}/*从哈希表中删除数据data,如果data不存在,则返回fasle,否则,删除之并返回true,其中哈希函数为H(key)=key%M*/bool delete_HashTable(HashTable hashtable,ElemType data){//如果没查找到,返回falseif(!search_HashTable(hashtable,data))return false;//否则,一定存在,找到删除之pNode pCur = hashtable[data%M].first;pNode pPre = pCur;//被删节点的前一个节点,初始值与pCur相同if(pCur->data == data)//被删节点是链表的第一个节点的情况hashtable[data%M].first = pCur->next;else{//被删节点不是第一个节点的情况while(pCur && pCur->data != data){pPre = pCur;pCur = pCur->next;}pPre->next = pCur->next;}free(pCur);pCur = 0;return true;}/*销毁槽数为n的哈希表*/void destroy_HashTable(HashTable hashtable,int n){int i;//先逐个链表释放for(i=0;inext;free(pDel);pDel = 0;}}//最后释放哈希表free(hashtable);hashtable = 0;}
    我们采用如下代码来测试:

/*******************************哈希表Author:兰亭风雨 Date:2014-03-07Email:zyb_maodun@163.com*******************************/#include#include "data_structure.h"int main(){int len = 15;//哈希表长,亦即表中槽的数目printf("We set the length of hashtable %d\n",len);//创建哈希表并插入数据HashTable hashtable = create_HashTable(len);if(insert_HashTable(hashtable,1))printf("insert 1 success\n");else printf("insert 1 fail,it is already existed in the hashtable\n");if(insert_HashTable(hashtable,8))printf("insert 8 success\n");else printf("insert 8 fail,it is already existed in the hashtable\n");if(insert_HashTable(hashtable,3))printf("insert 3 success\n");else printf("insert 3 fail,it is already existed in the hashtable\n");if(insert_HashTable(hashtable,10))printf("insert 10 success\n");else printf("insert 10 fail,it is already existed in the hashtable\n");if(insert_HashTable(hashtable,8))printf("insert 8 success\n");else printf("insert 8 fail,it is already existed in the hashtable\n");//查找数据pNode pFind1 = search_HashTable(hashtable,10);if(pFind1)printf("find %d in the hashtable\n",pFind1->data);else printf("not find 10 in the hashtable\n");pNode pFind2 = search_HashTable(hashtable,4);if(pFind2)printf("find %d in the hashtable\n",pFind2->data);else printf("not find 4 in the hashtable\n");//删除数据if(delete_HashTable(hashtable,1))printf("delete 1 success\n");else printf("delete 1 fail");pNode pFind3 = search_HashTable(hashtable,1);if(pFind3)printf("find %d in the hashtable\n",pFind3->data);else printf("not find 1 in the hashtable,it has been deleted\n");//销毁哈希表destroy_HashTable(hashtable,len);return 0;}
    输出结果如下:



完整源码下载

    完整源码下载地址:http://download.csdn.net/detail/mmc_maodun/7008669



推荐阅读
  • ALTERTABLE通过更改、添加、除去列和约束,或者通过启用或禁用约束和触发器来更改表的定义。语法ALTERTABLEtable{[ALTERCOLUMNcolu ... [详细]
  • 模板引擎StringTemplate的使用方法和特点
    本文介绍了模板引擎StringTemplate的使用方法和特点,包括强制Model和View的分离、Lazy-Evaluation、Recursive enable等。同时,还介绍了StringTemplate语法中的属性和普通字符的使用方法,并提供了向模板填充属性的示例代码。 ... [详细]
  • 本文介绍了一个适用于PHP应用快速接入TRX和TRC20数字资产的开发包,该开发包支持使用自有Tron区块链节点的应用场景,也支持基于Tron官方公共API服务的轻量级部署场景。提供的功能包括生成地址、验证地址、查询余额、交易转账、查询最新区块和查询交易信息等。详细信息可参考tron-php的Github地址:https://github.com/Fenguoz/tron-php。 ... [详细]
  • 本文介绍了在CentOS 6.4系统中更新源地址的方法,包括备份现有源文件、下载163源、修改文件名、更新列表和系统,并提供了相应的命令。 ... [详细]
  • 本文介绍了如何在使用emacs时去掉ubuntu的alt键默认功能,并提供了相应的操作步骤和注意事项。 ... [详细]
  • 本文为Codeforces 1294A题目的解析,主要讨论了Collecting Coins整除+不整除问题。文章详细介绍了题目的背景和要求,并给出了解题思路和代码实现。同时提供了在线测评地址和相关参考链接。 ... [详细]
  • 如何自行分析定位SAP BSP错误
    The“BSPtag”Imentionedintheblogtitlemeansforexamplethetagchtmlb:configCelleratorbelowwhichi ... [详细]
  • Monkey《大话移动——Android与iOS应用测试指南》的预购信息发布啦!
    Monkey《大话移动——Android与iOS应用测试指南》的预购信息已经发布,可以在京东和当当网进行预购。感谢几位大牛给出的书评,并呼吁大家的支持。明天京东的链接也将发布。 ... [详细]
  • 本文介绍了使用kotlin实现动画效果的方法,包括上下移动、放大缩小、旋转等功能。通过代码示例演示了如何使用ObjectAnimator和AnimatorSet来实现动画效果,并提供了实现抖动效果的代码。同时还介绍了如何使用translationY和translationX来实现上下和左右移动的效果。最后还提供了一个anim_small.xml文件的代码示例,可以用来实现放大缩小的效果。 ... [详细]
  • Nginx使用(server参数配置)
    本文介绍了Nginx的使用,重点讲解了server参数配置,包括端口号、主机名、根目录等内容。同时,还介绍了Nginx的反向代理功能。 ... [详细]
  • 云原生边缘计算之KubeEdge简介及功能特点
    本文介绍了云原生边缘计算中的KubeEdge系统,该系统是一个开源系统,用于将容器化应用程序编排功能扩展到Edge的主机。它基于Kubernetes构建,并为网络应用程序提供基础架构支持。同时,KubeEdge具有离线模式、基于Kubernetes的节点、群集、应用程序和设备管理、资源优化等特点。此外,KubeEdge还支持跨平台工作,在私有、公共和混合云中都可以运行。同时,KubeEdge还提供数据管理和数据分析管道引擎的支持。最后,本文还介绍了KubeEdge系统生成证书的方法。 ... [详细]
  • 本文介绍了数据库的存储结构及其重要性,强调了关系数据库范例中将逻辑存储与物理存储分开的必要性。通过逻辑结构和物理结构的分离,可以实现对物理存储的重新组织和数据库的迁移,而应用程序不会察觉到任何更改。文章还展示了Oracle数据库的逻辑结构和物理结构,并介绍了表空间的概念和作用。 ... [详细]
  • 阿,里,云,物,联网,net,core,客户端,czgl,aliiotclient, ... [详细]
  • 合并列值-合并为一列问题需求:createtabletab(Aint,Bint,Cint)inserttabselect1,2,3unionallsel ... [详细]
  • 本文介绍了在使用Laravel和sqlsrv连接到SQL Server 2016时,如何在插入查询中使用输出子句,并返回所需的值。同时讨论了使用CreatedOn字段返回最近创建的行的解决方法以及使用Eloquent模型创建后,值正确插入数据库但没有返回uniqueidentifier字段的问题。最后给出了一个示例代码。 ... [详细]
author-avatar
t53457078
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有