哈希查找算法图文详解

哈希查找算法又称散列查找算法，是一种在哈希表中查找目标元素的算法。

哈希表

哈希表又称散列表，是一种以关联方式存储数据的存储结构。所谓关联方式，哈希表将所有数据集中存储在一整块内存空间中，同时会为每个元素配备一个独一无二的索引（又称键）。

大多数编程语言都支持用数组（或称序列、列表）来存储多个元素，我们可以将所有数据存储在数组中，同时用数组的下标作为各个元素的索引（键），例如：

图 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