【数据结构】哈希表——C语言

文章目录

• 一、简介
• 二、存储方式
• • 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友有所帮助! 我们下篇文章再见咯！