数据结构散列表哈希表

前言

让我们想一下，若在手机通信录中查找一个人，那我们应该不会从第 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

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

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

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;
	}
	else
		printf("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;
		}
	}

这篇好文章是转载于：学新通技术网