小韦嘎嘎
哈希查找算法又称散列查找算法，是一种在哈希表中查找目标元素的算法。
哈希表
哈希表又称散列表，是一种以关联方式存储数据的存储结构。所谓关联方式，哈希表将所有数据集中存储在一整块内存空间中，同时会为每个元素配备一个独一无二的索引（又称键）。
大多数编程语言都支持用数组（或称序列、列表）来存储多个元素，我们可以将所有数据存储在数组中，同时用数组的下标作为各个元素的索引（键），例如：
图 1 哈希表
图 1 所示，所有元素都集中存储在一整块内存空间中，每个元素都配有唯一的、独一无二的索引，这样的存储结构就称为哈希表存储结构。
哈希表存储结构最大的优点是：如果想读取某个元素，不需要遍历整个序列，直接通过该元素的索引就可以找到它，大大提高了查找效率。
哈希函数
哈希表中，元素和索引之间的关联是通过哈希函数来维持的。哈希函数的构造方式有多种，例如直接定址法、折叠法、除留余数法等等，这里我们给您介绍直接定址法。
所谓直接定址法，就是以数学中一次函数（y = A*x+B，x 为未知数）的形式来构造哈希函数。例如上图中，各个元素和索引之间使用的哈希函数为：
H(value) = value % 11
其中，11 为整个存储空间所能存储的元素个数；value 指的是各个元素的值，H(value) 表示各个元素对应的索引值。
通过哈希函数，我们可以获取目标元素对应的索引值，从而在哈希表中直接找到该元素。比如在图 1 的哈希表中查找元素 77，通过哈希函数可以求出 77 对应的索引值为 0（77%11），因此目标元素存储在下标为 0 的位置上。
注意，通过哈希函数求得的索引值并不一定准确，因为不同的元素通过哈希函数求得的索引值可能相同。比如在图 1 所示的哈希表中再存储元素 44，通过哈希函数得出的哈希地址也为 0（44%11），和元素 77 冲突。哈希表中，不同元素对应索引值相同的现象称为碰撞（或者冲突）。
碰撞
使用哈希表存储数据时，碰撞是在所难免的，即便设计一个好的哈希函数，也只能减小碰撞发生的次数。因此我们需要制定相应的解决方案，使发生碰撞的元素也能成功存储到哈希表中。
碰撞的解决方案有多种，比如再哈希法、链地址法等等，这里给您介绍一种简单的方案，称为线性探测法。仍以图 1 的哈希表为例，当我们再存储元素 44 时，就会发生碰撞。这种情况下可以从碰撞的哈希地址开始，向后查找出一个空闲的存储位，然后将 44 存储起来。
在图 1 的基础上，从下标为 0 的位置向后遍历，下标为 1 的位置处于空闲状态，因此可以将 44 存储起来（如图 2 所示）。
图 2 哈希表添加元素 44
受到碰撞因素的影响，当我们在哈希表中查找某个元素时，直接通过哈希函数找到的索引值可能并不是目标元素真正的索引值。因此，当根据哈希函数找到索引值后，我们需要将索引值对应的元素同目标元素进行比对，如果比对失败，就需要进一步根据使用的碰撞方案查找目标元素真正的存储位置。
如图 2 所示，如果我们想查找元素 44，整个查找过程为：
根据哈希函数，元素 44 对应的索引值为 0；
找到数组（序列）中下标为 0 的元素 77，显然 77 != 44，因此继续查找；
根据线性探测法，从下标为 0 的位置依次向后查找；
取下标为 1 的元素 44，和目标元素相等，查找成功。
向上面描述的这样，在哈希表中查找目标元素的方法称为哈希查找算法。
如下为实现哈希查找算法的伪代码：
输入 hashArr[N] // 输入 N 个元素，并存储到哈希表 hasharr 中
hash(value): // 自定义哈希函数
return value%N // 返回 value 元素对应的索引值
hash_serch(hashArr[] , value): // 实现哈希查找算法，value 为要查找的目标元素
hashAdd = hash(value) // 根据哈希函数，找到对应的索引值
while hashArr[hashAdd] != value: // 如果哈希表中对应位置不是要查找的目标元（即发生了碰撞）
hashAdd = (hashAdd + 1) % N // 获取下一个索引值
if hashArr[hashAdd] == -1 || hashAdd = hash(value): // 如果索引值对应的存储位置为空（这里用 -1 表示），或者已经查找了一圈，仍为找到目标元素
return -1 // 查找失败（返回 -1 表示查找失败）
return hashAdd // 返回目标元素所在的索引
哈希查找算法的具体实现
如下为实现哈希查找算法的 C 语言程序：
#include <stdio.h>
#define N 11 //指定哈希表的长度
//自定义哈希函数
int hash(int value) {
return value % N;
}
//实现哈希查找算法，hashArr 表示哈希表，value 为要查找的目标元素
int hash_search(int * hashArr, int value) {
int hashAdd = hash(value); //查找目标元素所在的索引
while (hashArr[hashAdd] != value) { // 如果索引位置不是目标元素，则发生了碰撞
hashAdd = (hashAdd + 1) % N; // 根据线性探测法，从索引位置依次向后探测
//如果探测位置为空，或者重新回到了探测开始的位置（即探测了一圈），则查找失败
if (hashArr[hashAdd] == -1 || hashAdd == hash(value)) {
return -1;
}
}
//返回目标元素所在的数组下标
return hashAdd;
}
int main()
{
//创建哈希表，其中数组下标为各个元素对应的索引值，-1 表示该位置处于空闲状态
int arr[N] = { 77,44,-1,-1,26,93,17,-1,-1,31,54 };
//查找元素 44 的位置
int hashAdd = hash_search(arr, 44);
//如果返回值为 -1，表明查找失败，反之则返回目标元素所在的位置
if (hashAdd == -1) {
printf("查找失败\n");
}
else {
printf("查找成功，目标元素所在哈希表中的下标为：%d", hashAdd);
}
return 0;
}
如下为实现哈希查找算法的 Java 程序：
public class Demo {
public static int hash(int arrLeng,int value) {
return value % arrLeng;
}
public static int hash_serach(int [] hashArr,int value) {
//统计哈希表的长度
int length = hashArr.length;
//查找目标元素对应的索引值
int hashAdd = hash(length,value);
while (hashArr[hashAdd] != value) { // 如果索引位置不是目标元素，则发生了碰撞
hashAdd = (hashAdd + 1) % length; // 根据线性探测法，从索引位置依次向后探测
//如果探测位置为空，或者重新回到了探测开始的位置（即探测了一圈），则查找失败
if (hashArr[hashAdd] == -1 || hashAdd == hash(length,value)) {
return -1;
}
}
//返回目标元素所在的数组下标
return hashAdd;
}
public static void main(String[] args) {
int[] hashArr = new int[] { 77,44,-1,-1,26,93,17,-1,-1,31,54 };
// 输出目标元素 31 所在位置的下标
int hashAdd = hash_serach(hashArr,44);
if(hashAdd == -1) {
System.out.print("查找失败");
}else {
System.out.print("查找成功，目标元素所在哈希表中的下标为：" + hashAdd);
}
}
}
如下为实现哈希查找算法的 Python 程序：
# 创建哈希表，其中数组下标为各个元素对应的索引值，-1 表示该位置处于空闲状态
hashArr=[77,44,-1,-1,26,93,17,-1,-1,31,54]
# 自定义哈希函数
def hash(value):
return value % len(hashArr)
# 实现哈希查找算法，hashArr 表示哈希表，value 为要查找的目标元素
def hash_search(value):
global hashArr
hashAdd = hash(value) # 查找目标元素所在的索引
while hashArr[hashAdd] != value: # 如果索引位置不是目标元素，则发生了碰撞
hashAdd = (hashAdd + 1) % len(hashArr) # 根据线性探测法，从索引位置依次向后探测
#如果探测位置为空，或者重新回到了探测开始的位置（即探测了一圈），则查找失败
if (hashArr[hashAdd] == -1) or (hashAdd == hash(value)):
return -1
return hashAdd # 返回目标元素所在的数组下标
# 查找元素 44 的位置
hashAdd = hash_search(44)
if hashAdd == -1:
print("查找失败\n")
else:
print("查找成功，目标元素所在哈希表中的下标为 %d" % (hashAdd))
以上程序的输出结果均为：
查找成功，目标元素所在哈希表中的下标为 1
