C语言实现七大查找算法（二）

比眉伴天荒 2022-02-24 11:12 463阅读 0赞

在前面的博文中，我们介绍了5种查找算法，本文主要介绍哈希表及哈希查找算法。

在介绍哈希查找算法之前，我们需要详细了解什么是哈希表及其构造实现方法。

## 哈希表 ##

### 哈希表的基本思想 ###

我们知道，数组的最大特点就是：**寻址容易，插入和删除困难**；而链表正好相反，寻址困难，而插入和删除操作容易。那么如果能够结合两者的优点，做出一种寻址、插入和删除操作同样快速容易的数据结构。这就是哈希表创建的基本思想，**哈希表就是这样一个集查找、插入和删除**操作于一身的数据结构。

### 哈希表的一些基本概念 ###

1.  哈希表（Hash Table）：也叫散列表，是根据关键码值（Key-Value）而直接进行访问的数据结构，也就是我们常用到的map。
2.  哈希函数：也称散列函数，是**Hash表的映射函数**，它可以把查找表中的关键字映射成该关键字对应的地址函数，表示如下：  
     H a s h ( k e y ) = A d d r , （ 地 址 可 以 是 数 组 下 标 、 索 引 、 内 存 地 址 等 ） Hash(key) = Addr,（地址可以是数组下标、索引、内存地址等） Hash(key)=Addr,（地址可以是数组下标、索引、内存地址等）  
    哈希函数能使对一个数据序列的访问过程变得更加迅速有效，通过哈希函数数据元素能够被很快的进行定位。
3.  **冲突：两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞**。

>  *  尽量减少冲突
>  *  冲突不可避免，要设计好处理冲突的方法

### 散列函数的构造方法 ###

1.  定义域必须包含全部需要存储的关键字
2.  地址等概率，均匀的分布在整个地址空间
3.  函数尽量简单，较短时间内能算出任一关键字地址

**哈希表有很多种不同的实现方法，为了实现哈希表的创建，这些所有的方法都离不开两个问题——**“定址”和“解决冲突”

### 哈希表的定址方法 ###

1.  直接定址法：直接取关键字的某个线性函数值作为散列地址，例如：  
     H ( k e y ) = a × k e y + b , ( a 和 b 均 为 常 数 ) H(key) = a \\times key + b,(a和b均为常数) H(key)=a×key\+b,(a和b均为常数)  
    适合关键字分布基本连续的情况，否则容易造成存储空间浪费。
2.  除留余数法：(最常用) 假定表长为m，**取一个不大于m但最接近或者等于m的质数P**，例如：  
     H ( k e y ) = k e y % P H(key) = key\\%P H(key)=key%P
3.  数字分析法：比如有一组 v a l u e 1 = 112233 ， v a l u e 2 = 112633 ， v a l u e 3 = 119033 value1=112233，value2=112633，value3=119033 value1=112233，value2=112633，value3=119033，针对这样的数我们分析数中间两个数比较波动，其他数不变。那么我们取key的值就可以是 k e y 1 = 22 , k e y 2 = 26 , k e y 3 = 90 key1=22,key2=26,key3=90 key1=22,key2=26,key3=90。  
    适合于已知关键字的集合分布，关键字位数较大的情况。
4.  平方取中法：取关键字的平法值的中间几位作为散列地址。  
    适合于不是道关键字分布，且关键字每一位取值不均匀或均小于散列地址所需的位数。
5.  折叠法：举个例子，比如 v a l u e = 135790 value=135790 value=135790，要求key是2位数的散列值。那么我们将 v a l u e value value变为 13 + 57 + 90 = 160 13+57+90=160 13\+57\+90=160，然后去掉高位 “ 1 ” “1” “1”,此时 k e y = 60 key=60 key=60，这就是他们的哈希关系。这样做的目的就是key与每一位value都相关，来**达到“散列地址”尽可能分散**的目的。

适合于不需要知道关键字分布，关键字位数较多的情况。

### 哈希表解决冲突的方法 ###

1.  **开放定址法：**  
    如果两个数据元素的哈希值相同，则在哈希表中为后插入的数据元素另外选择一个表项。当程序查找哈希表时，如果没有在第一个对应的哈希表项中找到符合查找要求的数据元素，程序就会继续往后查找，直到找到一个符合查找要求的数据元素，或者遇到一个空的表项。

**假设已经选定散列函数为 H ( k e y ) H(key) H(key)，下面用 H i H\_i Hi表示发生冲突后第 i i i次探测的散列地址**。  
 H i = ( H ( k e y ) + d i ) % m H\_\{i\} = (H(key)+d\_\{i\})\\%m Hi=(H(key)\+di)%m  
其中， i = 1 , 2 , . . . , k ( k < = 1 ) i=1, 2, ...,k (k<=1) i=1,2,...,k(k<=1)； m m m表示散列长度， d i d\_i di表示增量序列。

**增量序列 d i d\_i di通常有4种取法：**

*  线性探测法： d i = 1 , 2 , . . . , m − 1 d\_i=1,2,..., m-1 di=1,2,...,m−1，可能造成大量元素在相邻地址聚集，降低查找效率。
 *  平方探测法： d i = 1 2 , − 1 2 , 2 2 , − 2 2 , . . . , − k 2 , ( k < = m / 2 ) d\_i=1^2,-1^2,2^2,-2^2,...,-k^2,(k<=m/2) di=12,−12,22,−22,...,−k2,(k<=m/2)，**m必须是一个可表示为 4 k + 3 4k+3 4k\+3的质数**。避免出现“堆积问题”，但是不能探测全部单元（至少一半）。
 *  再散列法： d i = H a s h 2 ( k e y ) d\_i=Hash\_\{2\}(key) di=Hash2(key)，使用2个散列函数。
 *  伪随机序列法： d i = d\_i= di=伪随机序列

\*\*注意：\*\*开放定址情形下，不能随便物理删除表中已有的元素，这样会截断其他具有相同散列地址元素查找地址；应做删除标记，逻辑删除。

以线性探测为例（定址法选择取余法），举例如下：

![1.png][]

散列过程如下图所示：

![2.png][]

我们可以发现，冲突次数还是比较多的，这是因为P的取值没选好，前面讲过：假定表长为m，**取一个不大于m但最接近或者等于m的质数P**，这里表长m=10，P最好取7，而图中取了10。

1.  **拉链法：**  
    将哈希值相同的数据元素存放在一个链表中，在查找哈希表的过程中，当查找到这个链表时，必须采用线性查找方法。**适用于经常进行插入、删除的情况**。

定址法选择取余法，举例如下：  
设有一组关键字为(26，36，41，38，44，15，68，12，6，51)，初始情况如下图所示：

![4.png][]

最终结果如下图所示：

![3.png][]

### 散列查找及性能分析 ###

**查找过程与构造过程基本一致**

查找效率三因素：散列函数、处理冲突的方法、哈希表装填因子 ( α ) (\\alpha) (α)  
 α = 表 中 记 录 数 散 列 表 长 度 = n m \\alpha = \\frac\{表中记录数\}\{散列表长度\} = \\frac\{n\}\{m\} α=散列表长度表中记录数=mn  
**平均查找长度依赖于 α \\alpha α**， α \\alpha α越大，记录越“满”，发生冲突的可能性越大。

**下面贴一张哈希表中查找失败和成功时，平均查找程度的计算例子**

![5.png][]

**拓展：如果关键字是字符串怎么办？** （详见参考资料）

1.  将字符串的所有的字符的ASCII码值进行相加，将所得和作为元素的关键字
2.  假设关键字至少有三个字母构成，散列函数只是取前三个字母进行散列
3.  借助Horner’s 规则，构造一个质数（通常是37）的多项式，（非常的巧妙，不知道为何是37）。计算公式为: k e y \[ k e y s i z e − i − 1 \] ∗ 3 7 i , 0 < = i < k e y s i z e key\[keysize-i-1\]\*37^i, 0<=i<keysize key\[keysize−i−1\]∗37i,0<=i<keysize求和。

## 哈希查找 ##

介绍完如何构造哈希表后，我们来看一下哈希查找算法。

**算法简介**  
哈希表就是一种以**键-值(key-indexed)** 存储数据的结构，只要输入待查找的值即key，即可查找到其对应的索引值（地址）。

**算法思想**  
哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。

**算法流程**

1.  用给定的哈希函数构造哈希表；
2.  根据选择的冲突处理方法解决地址冲突；
3.  在哈希表的基础上执行哈希查找。

哈希表（**空间换时间**）是一个在**时间和空间上做出权衡**的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。

\*\*复杂度分析：\*\*单纯论查找复杂度：对于无冲突的Hash表而言，查找复杂度为O(1)（注意，在查找之前我们需要构建相应的Hash表）。

**算法实现**  
这边找了一个**除留余数法加线性开放定址法**的代码实例，来源于[c实现哈希查找][c]

//采用除数取留法确定地址，利用线性开放地址法处理冲突问题，2016.5.28
    #include <stdio.h>
    #include <stdlib.h>
    #include <io.h>
    #include <math.h>
    #include<time.h>
     
    #define HASHSIZE 15
    #define NULLKEY -32768
     
    typedef struct
    {
        
    	int *elem; //数据元素存储地址
    	int count;//当前元素个数
    }HashTable;
    int L = 0; //表的长度
     
    bool init(HashTable *hashTable)//哈希表的初始化
    {
        
    	int i;
    	L = HASHSIZE;
    	hashTable->elem = (int*)malloc(L*sizeof(int));//申请内存
    	hashTable->count = L;
    	for (i = 0; i < L; i++)
    	{
        
    		hashTable->elem[i]=NULLKEY;
    	}
    	return true;
    }
     
    //哈希函数，除留余数法，最常用的哈希函数，还有其它的。
    int Hash(int data)
    {
        
    	return data%L;
    }
     
    void insert( HashTable *hashTable, int data)
    {
        
    	int Addr = Hash(data);//求哈希地址
    	while (hashTable->elem[Addr] != NULLKEY)//求得地址不是初始化时的空，则表示有元素已经插入，会有冲突
    	{
        
    		Addr = (Addr + 1) % L;//开放地址线性探测，还可以二次探测
    	}
    	hashTable->elem[Addr] = data;
    }
     
    int  find(HashTable *hashTable, int data)
    {
        
    	int Addr = Hash(data);                  //求哈希地址
    	while (hashTable->elem[Addr] != data)   //线性开放定址法解决冲突
    	{
        
    		Addr = (Addr + 1) % L;
    		if (hashTable->elem[Addr] == NULLKEY || Addr == Hash(data))
    			return 0;
    	}
    	return Addr;
    }
     
    void display(HashTable *hashTable)           //散列元素显示
    {
        
    	int i;
    	printf(".........结果展示.........\n");
    	for (i = 0; i < hashTable->count; i++)
    	{
        
    		printf("%d\n", hashTable->elem[i]);
    	}
    }
     
    void main()
    {
        
    	int i, j, result, x;
    	HashTable hashTable;
    	int arr[HASHSIZE];
    	printf("请输入少于15个，初始化哈希表的元素：\n");
    	for (j = 0; j < HASHSIZE; j++)
    	{
        
    		scanf("%d", &arr[j]);
    	}
    	init(&hashTable);
    	for (i = 0; i < HASHSIZE; i++)
    	{
        
    		insert(&hashTable, arr[i]);
    	}
    	display(&hashTable);
    	printf("请输入你要查找的元素：\n");
    	scanf("%d", &x);
    	result = find(&hashTable, x);
    	if (result)
    		printf("查找元素%d在哈希表中的位置为%d\n",x,result);
    	else 
    		printf("没找到！\n");
    	system("pause");
    }

**参考资料：**  
[Hash那点事儿][Hash]  
[七大查找算法][Link 1]

[1.png]: /images/20220224/a177fc5b2b5746ddb38a1f4d9a94d853.png
[2.png]: /images/20220224/bf200c1dd15642569e61bad996a4d72a.png
[4.png]: /images/20220224/e302fe8c4d594584ad6e1c6b58b110df.png
[3.png]: /images/20220224/bd6e3243303445c9b0bd63aa8a03df37.png
[5.png]: /images/20220224/f4c9ed10704843f3bc13adda3fb1a8b5.png
[c]: https://blog.csdn.net/jx232515/article/details/51525377
[Hash]: https://www.cnblogs.com/maybe2030/p/4719267.html
[Link 1]: https://www.cnblogs.com/lsqin/p/9342929.html