文章目录

  • 一、简介
  • 二、存储方式
    • 1.开发寻址法
    • 2.拉链法
  • 三、哈希函数——宏函数
    • 1.处理句柄
    • 2.查找结点
      • int类型
      • 字符串
    • 3.添加结点
      • int类型
      • str类型
    • 4.删除一个结点
    • 5.删除所有结点
    • 6.HASH_ADD
      • ①整形
      • ②字符串
    • 7.HASH_FIND
      • ①整形
      • ②字符串
  • 总结

一、简介

hash table音译过来就叫哈希表,也叫做散列表,是一种利用数组下标索引的特性,延伸出来的一种数据结构。

 我们都知道通过数组下标索引得到目标值的时间复杂度是O(1),而哈希表赋予了下标一些特殊的意义。
比如:再开一个数组将下标换成目标值,将目标值改为下标,进行存储
如果要想知道目标值的下标,直接用目标值进行索引即可,而且这样的时间复杂度也是O(1),但是 由于开辟了空间进行存储信息,因此空间复杂度是O(N)
于是索引值称之为Key,通过Key索引的值就叫做val

说明:由于本篇是索引篇,只对C语言的接口做了详细说明,而实现原理较为粗略,因此如果想对实现原理进行探究的话,下面贴有详细文章:

  • 哈希表(详)

这里列举了一下目前位置博主所碰见的哈希用途~

  1. 消除字符顺序带来的时间复杂度的提高——变位词(可能需要结合双指针进行使用)
  2. 通过指定的值,查找其位置——下标(数组) / 地址(单链表之类的数据结构)(插入、删除和随机访问都是 O(1) 的容器)
  3. 记录指定值出现的次数——求一段连续且不相同的XX(可以是字符也可以是整形)的长度
  4. 将某种数据类型当做哈希表进行参与运算——单词长度的最大乘积

当然,如果对这几道题有兴趣的小伙伴,可以查看我的专栏:剑指offer专项突破版

这里为了方便查找,再多说几句,第4道——在整数篇第1道——字符串篇,第2道——哈希表篇。

二、存储方式

 为什么要谈存储方式呢?主要是为了解决哈希表中冲突的问题,那什么时候会产生冲突呢?主要与哈希函数的实现有关。

比如:我们要存储【10,1】这里10在原数组是目标值,1是下标。而在哈希表中位置互换,10是索引值,1是目标值,那如何进行索引存储呢?一般我们都会映射到一个位置,比如这里的10%10就是0,存储到哈希表0下标的位置处。

接着存【0, 1】这样的值呢?0%10还是0, 还存储到哈希表下标为0的位置处吗?

原来的位置已经存有值了。像这样发生存储位置冲突的情况,我们一般就称之为哈希冲突,当然我们这里的例子比较简单。那怎么解决呢?就回到正题了。

下面我们以这个例子具体说明

typedef struct Hash{int key;int val;}HNode;

1.开发寻址法

假设:开始哈希表存储数据个数为0。用上面冲突的例子,另外补充一点,我们这里多存储了一个key ~ 产生冲突时,我们会寻找直到有没有存放值的位置。举个例子,假如你在很想上厕所,你会从靠门的位置开始一个挨着一个位置进行找坑位,如果幸运,第一个位置就没人(无冲突),如果运气不好,可能找不到坑位(空间不够)。

类比一下哈希表就像一个大型厕所(必有空余坑位),你去指定位置上厕所,如果没有人,你把shift放进去(key和val),如果有人,就往下直到找到没有人的坑位,再把shift放进去(key和val)。

有同学要问了,这里为什么要存key,能不存吗?

举个例子:用哈希表查找上面的【10,1】时,我们还是会先算 0%10的结果——0,用此结果在哈希表中查找,是不准确的,可能会查找到与之冲突的值,我们还要确认是不是里面的key是不是10,这样才能保证查对了

2.拉链法

  同样我们这里也用上面的例子,哈希表的下标处,其实是一条链表的结构,当产生冲突时,我们就在下标处再开辟一个结点,用于存储产生冲突的值,这样冲突值的下标相同,我们只要在这条链表中查找即可。

还有同学,就要问了——链表不会过长吗?这样时间复杂度就不是O(1)了吧?博主认为,哈希函数的实现跟冲突的产生才有实际联系,只要哈希函数取得好,就不怕冲突。因此,即使冲突我们也认为是链表上的结点是常数个,时间复杂度还是O(1)。

三、哈希函数——宏函数

这里我们介绍一下大佬实现的哈希表,我们可以在力扣上直接用!不过需要我们自己写函数,以便于符合我们的实际需要。

这里我们主要介绍几个宏函数和一个处理句柄,一般情况下就够用了~

1.处理句柄

UT_hash_handle hh;

定义结构体时,我们把这句代码添上即可。同时不用给这个处理句柄赋值。

那为啥叫处理句柄,我们要通过这个变量,把某个结点在哈希表中删除,添加,查找,改值,那这个处理数据工作,就交给它了,因此可以理解为啥叫处理句柄了吧。

比如:

typedef struct Hash{int key;int val;UT_hash_handle hh;}HNode;

下面我们也会用到这个结构体~

2.查找结点

int类型

HNode* hash = NULL;HNode* ret = NULL;int key = 10;HASH_FIND_INT(hash,&key,ret);//转换小写一看便知,hash_find_int,名字上我们大概就是查找一个int的变量。

这里的三个参数:
①:通过HNode*(指针),查找哈希表。
②:通过key,查找哈希表中,有没有这个值。至于为啥是指针,博主认为宏函数么,本质上是一些语句的替换,你要定义变量的话,不太现实,指针的可操作性更高。单从函数的角度来看,指针的空间利用效率也更高。
③:接收值,将最终结果,放在ret中,宏函数可没有返回值哦!这里这个参数充当的是返回值的作用

那返回结果是什么呢?
有两种情况:找到/找不到

  1. 找到,ret指向的是查找到的结点。 这里就可以多一个改的操作
  2. 找不到,ret指向为空。

因此我们可以通过ret是否为空来判断找到没有。

字符串

这里我们就要换一个结构体类型了~

typedef struct Hash{char key[10];int val;UT_hash_handle hh;}HNode;HNode* hash = NULL;HNode* ret = NULL;char key[10] = "shun_hua"; HASH_FIND_STR(hash,key,ret);//同样,大小写一转换,str不就是字符串的意思么

参数的用途跟上面一样,不过这里需要注意的是,key本身就是指针,不需要再传key的地址了!

3.添加结点

int类型

//这里我们用的是上面key类型为int的结构体,别搞混了哦~HNode* hash = NULL;HNode* ret = (HNode*)malloc(sizeof(HNode));int key = 10;int val = 1;ret->key = key;ret->val = val; HASH_ADD_INT(hash,key,ret);

至于这里的key为啥不是指针,我们可以简单理解为,计算哈希值,我们是直接用值计算的,因此传的是key。

第三个参数:这里是将ret所指向的结点,放在哈希表中。

str类型

说明:在C语言中,并没有字符串类型,这里说的字符串类型只是为了方便理解,指的是char类型的数组

HNode* hash = NULL;HNode* ret = (HNode*)malloc(sizeof(HNode));char key[10] = "shun_hua"//这里如果说,为了提升效率,建议用指针类型,比如char *key = "shun_hua"//当然如果这里指针是可以当做字符串进行查找的,但是添加是作为指针进行添加的。int val = 1;//字符串我们就要用到这个函数进行字符串的拷贝strcpy(ret->key,key);//这里会将'\0'也拷贝过去!//当然,memcpy也可以ret->val = val; HASH_ADD_STR(hash,key,ret);

4.删除一个结点

这里我们需要用一下前面的查找节点的函数,毕竟,你要删除结点,也得有结点给你删除吧~

HNode* hash = NULL;HNode* ret = NULL;int key = 10;HASH_FIND_INT(hash,&key,ret);if(ret!=NULL){HASH_DEL(hash,ret);free(ret);}

当然我们这里添加了一个free操作,说明我们只是将节点从哈希表中移除,并没有将节点的空间进行释放,因此需要free函数释放其空间。

说明:字符串的删除与之雷同,就不列举了。

5.删除所有结点

HNode* hash = NULL;HNode* cur, *next;HASH_ITER(hh,hash,cur,next)//这里的hh就是处理句柄{HASH_DEL(hash,cur);free(cur);}

这里我们可以看做链表的删除操作,至于这里的宏有点奇怪是因为,其实现原理是for循环,这段代码的意思,从hash表中获取一个元素,同时保留下一个元素,将此元素从哈希表中移除,同时释放其空间,直到哈希表无数据为止!

除此之外,我们再介绍两个通用宏。

6.HASH_ADD

①整形

HNode* hash = NULL;HNode* ret = (HNode*)malloc(sizeof(HNode));int key = 10;int val = 1;ret->key = key;ret->val = val; HASH_ADD(hh,hash,key,sizeof(key),ret);

第四个参数使用的是sizeof

②字符串

HNode* hash = NULL;HNode* ret = (HNode*)malloc(sizeof(HNode));char key[10] = "key";int val = 1;strcpy(ret->key,key);ret->val = val; HASH_ADD(hh,hash,key,strlen(key),ret);

第四个参数使用的是strlen

7.HASH_FIND

①整形

HNode* hash = NULL;HNode* ret = NULL;int key = 10;HASH_FIND_INT(hh,hash,&key,sizeof(key),ret);

第四个参数使用的是sizeof

②字符串

HNode* hash = NULL;HNode* ret = NULL;char key[10] = "shun_hua"; HASH_FIND_STR(hh,hash,key,strlen(key),ret);//这里key就是字符串的地址。

第四个参数使用的是strlen


补充:如果觉得不详细可以看这篇文章c开源hash项目 uthash的用法总结,指针如何添加的例子就在此文末

总结

到这里我们的文章就分享完了,都说一万个人眼里有一万个哈姆雷特,不知道看到这的你从这篇文章中收获了多少呢?总之,希望这篇文章对C友有所帮助! 我们下篇文章再见咯!