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

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

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

哈希表

哈希表的基本思想

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

哈希表的一些基本概念

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

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

散列函数的构造方法

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

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

哈希表的定址方法

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

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

哈希表解决冲突的方法

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

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

增量序列 $d_{i}$ 通常有4种取法：

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

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

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

散列过程如下图所示：

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

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

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

最终结果如下图所示：

散列查找及性能分析

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

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

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

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

将字符串的所有的字符的ASCII码值进行相加，将所得和作为元素的关键字
假设关键字至少有三个字母构成，散列函数只是取前三个字母进行散列
借助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-indexed) 存储数据的结构，只要输入待查找的值即key，即可查找到其对应的索引值（地址）。

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

算法流程

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

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

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

算法实现
这边找了一个除留余数法加线性开放定址法的代码实例，来源于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那点事儿
 七大查找算法