【数据结构】散列表（哈希表）

前言

让我们想一下，若在手机通信录中查找一个人，那我们应该不会从第 1 个人一直找下去，因为这样实在是太慢了。我们其实是这样做的：首先看这个人的名字的首字母是什么，比如姓张，那么我们一定会滑到最后，因为“Z”姓的名字都在最后。

还有在查字典时，要查找一个单词，肯定不会从头翻到尾，而是首先通过这个单词的首字母，找到对应的那一页；再找第 2 个字母、第 3 个字母……这样可以快速跳到那个单词所在的页。

其实这里就用到了散列表的思想。

一、什么是散列表

散列表（hash table），我们平时叫它哈希表或者Hash 表，你肯定经常听到它。

散列表是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

由定义我们可以知道，散列表用的是数组支持下标访问数据的特性，所以散列表是数组的一种扩展，有数组演化而来。

二、什么是哈希函数

哈希函数就是将键转化为数组索引的过程,这个函数应该易于计算且能够均与分布所有的键。

三、下面简单介绍几种哈希函数

• 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。
• 数字分析法：通过对数据的分析，发现数据中冲突较少的部分，并构造散列地址。例如同学们的学号，通常同一届学生的学号，其中前面的部分差别不太大，所以用后面的部分来构造散列地址。
• 平方取中法：当无法确定关键字里哪几位的分布相对比较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为散列地址。这是因为：计算平方之后的中间几位和关键字中的每一位都相关，所以不同的关键字会以较高的概率产生不同的散列地址。
• 取随机数法：使用一个随机函数，取关键字的随机值作为散列地址，这种方式通常用于关键字长度不同的场合。
• 除留取余法：取关键字被某个不大于散列表的表长 n 的数 m 除后所得的余数 p 为散列地址。这种方式也可以在用过其他方法后再使用。该函数对 m 的选择很重要，一般取素数或者直接用 n。

以上方法是对数字类型的操作，对字符串类型的数据，可以选择通过相加或者进位转化成数字后，再执行上面的计算方法。

四、冲突

冲突就是，两个不同的关键字，但是通过散列函数得出来的地址是一样的。
key1 ≠ key2，但是f（key1）= f（key2）

同义词
此时的key1 和key2就被称为这个散列函数的同义词

那可不行啊，一件单人间怎么可以住两个人呢？

别担心，这个问题自然已经被神通广大的大佬们解决了。

处理散列冲突的方法

开放定址法

开发定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只需要散列表足够大，空的散列地址总能找到，并将记录存入

例子：
19 01 23 14 55 68 11 86 37
要存储在表长11的数组中，其中H（key）=key MOD 11

1. 线性探测法
   公式

f1(key) = (f(key)+d1) MOD m(di=1,2,3,....,m-1)

我们取di等于1

index	0	1	2	3	4	5	6	7	8	9	10
key	55	1		14					19	86
		23冲突	23
			68冲突	68冲突	68
	11冲突	11冲突	11冲突	11冲突	11冲突	11
					37冲突	37冲突	37
最终存储结果	55	1	23	14	68	11	37		19	86

2. 二次探测法
   增加平方运算的目的是为了不让关键字都聚再某一块区域，我们称这种方法为二次探测法
   公式：

f1(key) = (f(key)+d1) MOD m(di=1^2,-1^2,2^2,-2^2,...,q^2,-q^2,q<=m/2)

index	0	1	2	3	4	5	6	7	8	9	10
key	55	1	14						19	86
		23冲突	f(23)+1
		f(68)-1冲突	68冲突	f(68)+1冲突			f(68)+4
	11冲突	f(11)+1冲突									f(11)-1
最终存储结果	55	1	23	14			68		19	86	11

3. 随机探测法
   在冲突时，对于位移量di采用随机函数计算得到，我们称之为随机探测法
   公式

f1(key) = (f(key)+d1) MOD m(di是一个随机数列)

具体方法和上面一样
就不多赘述了

再散列函数法

对于我们的散列表来说，我们事先需要准备多个散列函数

f(key)=RHi(key) (i=1,2...,3)

这里的RHi就是不同的散列函数，每当发生冲突时，就换一个散列函数进行计算，总有一个函数可以将冲突解决

公共溢出区法

在原先基础表的基础上再添加一个溢出表
当发生冲突时，就将该数据放到溢出表中
在查找时，对给定值通过散列函数计算出散列地址后，先与基本表的相应位置进行对比，如果相等就查找成功，如果不相等，则到溢出表进行顺序查找

链地址法

就时用链表将发生冲突的数据链起来，在查找时，只需要遍历链表即可
如下图

此方法也是我们最长用处理哈希冲突的方法

五、代码实现

1.哈希函数

//哈希函数
int Hash(int key, int TableSize)
{return key % TableSize;
}

2.链表和哈希表的创建

#define DEFAULT_SIZE 16
typedef int type;
//结点
typedef struct ListNode
{struct ListNode* next;int key;  //线索type* data; //数据
}ListNode;
//提高可读性
typedef ListNode* List;
typedef ListNode* Element;
//哈希表
typedef struct HashTable
{int TableSize;List* Thelists;
}HashTable;

3.哈希表初始化

HashTable* InitHash(int TableSize)
{int i = 0;HashTable* htable = NULL;if (TableSize <= 0){TableSize = DEFAULT_SIZE;}htable = (HashTable*)malloc(sizeof(HashTable));if (htable == NULL){printf("初始化失败\n");return NULL;}//为桶分配内存空间，其为一个指针数组htable->Thelists = (List*)malloc(sizeof(List) * TableSize);if (htable->Thelists == NULL){printf("初始化失败\n");free(htable);return NULL;}//为Hash桶对应的指针数组初始化链表结点for (i = 0; i < TableSize; i++){htable->Thelists[i] = (ListNode*)malloc(sizeof(ListNode));if (htable->Thelists[i] == NULL){printf("初始化失败\n");free(htable->Thelists);free(htable);return NULL;}}
}

3.从哈希表中根据key查找元素

Element Find(HashTable* HashTable, int key)
{int i = 0;List L = NULL;Element e = NULL;i = Hash(key, HashTable->TableSize);L = HashTable->Thelists[i];e = L->next;while (e != NULL && e->key != key)e = e->next;return e;
}

4.哈希表插入元素

void Insert(HashTable* HashTable, int key, type* value)
{Element e = NULL, temp = NULL;List L = NULL;e = Find(HashTable, key);if (e == NULL){temp = (Element)malloc(sizeof(ListNode));if (temp == NULL){printf("malloc error\n");return;}L = HashTable->Thelists[Hash(key, HashTable->TableSize)];temp->data = value;temp->key = key;L->next = temp;}elseprintf("the key already exist\n");
}

5.元素删除

void Delete(HashTable* HashTable, int key)
{Element e = NULL, last = NULL;List L = NULL;int i = Hash(key, HashTable->TableSize);L = HashTable->Thelists[i];last = L;e = L->next;while (e != NULL && e->key != key){last = e;e = e->next;}if (e){last->next = e->next;free(e); }else{printf("该元素不存在\n");}
}

6.哈希表销毁

void Destory(HashTable* HashTable)
{int i = 0;List L = NULL;Element cur = NULL, next = NULL;for (i = 0; i < HashTable->TableSize; i++){L = HashTable->Thelists[i];cur = L->next;while (cur->next != NULL){next = cur->next;free(cur);cur = next;}}