【数据结构/查找】哈希表

﹏ヽ暗。殇╰゛Y 2022-10-18 01:50 218阅读 0赞

# 哈希函数 #

有一种函数，根据这个函数和查找关键字key，可以直接确定查找值所在位置，而不需要一个个比较。这样就“预先知道”key所在的位置，直接找到数据，提升效率。  
即  
**地址index=Hash（key）**  
说白了，hash函数就是根据key计算出存储地址的位置，而哈希表是基于哈希函数建立的一种查找表。

# 哈希表（散列表） #

此处大部分内容来自[简书][Link 1]

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

我们必须在记录的存储位置和它的关键字之间建立一个确定的**对应关系 f**，使每个关键字和结构中一个唯一的存储位置相对应。  
**(关键字就是所要存储的数据，存储位置相当于数组的索引)**

对应关系f称为**散列函数**，又称为哈希（Hash函数），采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为**散列表或哈希表（Hash table）。**

> eg1. 将26个小写字母存储到数组 int \[26\] a。  
> a对应a\[0\]，b对应a\[1\]，c对应a\[3\]……以此类推。  
> 那么，数组 int \[26\] a 就是一个哈希表！

例1中，关键字(小写字母)是如何得到自己对应的索引(存储位置)的呢？  
**关键字的ASCII值减去a的ASCII值**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center]  
上面说过，关键字通过哈希函数得到索引，所以，f(ch)就是本例题的哈希函数。

这样，我们就在关键字和数字(存储位置)之间建立了一个确定的对应关系f。

关键字与数字是一一对应的，由于数组本身支持随机访问，所以，当查找关键字时，只需要 **O(1)** 的查找操作，也就是实现了不经过任何比较，一次便能得到所查记录。

# 哈希函数构造方法 #

也叫散列函数构造方法  
考虑因素：  
1.散列表长度  
2.关键字长度  
3.关键字分布情况  
4.计算散列函数需要的时间  
5.记录的查找频率

**构造散列表几种常用方法**  
1.数字分析法  
2.平方取中法  
3.折叠法  
4.除留余数法

# 哈希冲突 #

通过哈希函数计算出的索引，即使关键字不同，索引也会有可能相同。这就是哈希冲突。  
如何解决哈希冲突，是我们建哈希表的另一个关键问题。

# 哈希冲突的解决方案 #

## 开放地址法 ##

首先有一个H（key）的哈希函数  
如果H（key1）=H（key i）此时i=1  
那么 **H i=(H(key)+d i ) MOD m**，m为表长  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 1]  
最后一种不做介绍了。

### 线性探测再散列 ###

线性探测方法就是线性探测空白单元。  
当数据通过哈希函数计算应该放在700这个位置，但是700这个位置已经有数据了，那么接下来就应该查看701位置是否空闲，再查看702位置，依次类推。

线性探测就是使用**算术取余**的方法计算余数，当产生冲突时就通过线性递增的方法进行探测，一直到数组的位置为空，插入数据项即可。

举例说明

> 有一组数据  
> 19 01 23 14 55 68 11 86 37要存储在表长11的数组中  
> 其中H（key）=key MOD 11

我们取di=1，即冲突后存储在冲突后一个位置，如果仍然冲突继续向后  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 2]

### 平方探测再散列 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 3]

## 链地址法 ##

产生hash冲突后在存储数据后面加一个指针，指向后面冲突的数据  
上面的例子，用链地址法则是下面这样：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 4]

# 哈希表的查找 #

哈希表查找的平均查找长度实际上并不等于0.

**决定哈希表查找的ASL的因素：**  
1.选用的哈希函数  
2.选用的处理冲突的方法  
3.哈希表饱和的程度：**装填因子**=表中填入的记录数 / 散列表的长度 的大小

要注意的是，装填因子的值越小，发生冲突的可能性就越小。

查找代码：  
[参考][Link 2]

#include "stdio.h"    
    #include "stdlib.h"   
     
    #define HASHSIZE 10 // 定义散列表长度 
    #define NULLKEY -32768 
     
    typedef struct
    {
        
    	int *elem; // 数据元素存储地址，动态分配数组 
    	int count; //  当前数据元素个数 
    }HashTable;
     
    int m = 0; 
    		  
    int Init(HashTable *H)
    {
        
    	int i;
     
    	m = HASHSIZE;
    	H->elem = (int *)malloc(m * sizeof(int)); //分配内存
    	H->count = m;
    	for (i = 0; i<m; i++)
    	{
        
    		H->elem[i] = NULLKEY;
    	}
    	return 1;
    }
     
     
    int Hash(int k)
    {
        
    	return k % m;//除留余数法
    }
     
     
    void Insert(HashTable *H, int k)
    {
        
    	int addr = Hash(k); 					 
    	while (H->elem[addr] != NULLKEY)
    	{
        
    		addr = (addr+1) % m;//开放定址法
    	}
    	H->elem[addr] = k;
    }
     
    int Search(HashTable *H, int k)
    {
        
    	int addr = Hash(k); //求哈希地址
     
    							
    	while (H->elem[addr] != k)//开放定址法解决冲突
    	{
        
    		addr = (addr+1) % m;
     
    		if (H->elem[addr] == NULLKEY || addr == Hash(k))
    			return -1;
    	}
    	return addr;
    }
     
    void Result(HashTable *H)//散列表元素显示
    {
        
    	int i;
    	for (i = 0; i<H->count; i++)
    	{
        
    		printf("%d ", H->elem[i]);
    	}
    	printf("\n");
    }
     
    void main()
    {
        
    	int i, j, addr;
    	HashTable H;
    	int arr[HASHSIZE] = {
         NULL };
     
    	Init(&H);
     
    	printf("输入关键字集合:");
    	for (i = 0; i<HASHSIZE; i++)
    	{
        
    		scanf_s("%d", &arr[i]);
    		Insert(&H, arr[i]);
    	}
    	Result(&H);
     
    	printf("输入需要查找的元素：");
    	scanf_s("%d", &j);
    	addr = Search(&H, j);
    	if (addr == -1)
    		printf("元素不存在\n");
    	else
    		printf("%d元素在表中的位置是:%d\n", j,addr);
     
    }

[Link 1]: https://www.jianshu.com/p/4e64fce04a38
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221014/e3e16007d7324ce391aa11434f13f009.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221014/c8599c7c463741a8ba78267e11b84e00.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221014/3c62b0d8c2b54b7d938fdca75c8f31cf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221014/0004ea27094742d08f0ff82991285746.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221014/92dda47ce0a0470dbd07f46b3eaaa0be.png
[Link 2]: https://blog.csdn.net/weixin_40567229/article/details/81137993