哈希查找

讲哈希查找之前我们先了解什么是哈希表。哈希表又称散列表，是根据关键码值而直接进行访问的数据结构。

哈希表把所有的数据存放在一段内存中，再给每一个数据一个独有的索引（又称为键），这也是哈希查找效率高的原因，使用哈希查找时，不需要遍历整个数组，只要将目标值和哈希表中元素对应的索引比较就可以找到了。我们知道数组可以用来存储数据，数组中的每个元素都有一个下标（索引），那下面就给大家展示一个普通的数组和它的索引。

图表 1数组

在哈希查找中，每个元素的存储位置并不是依次存储，而是按照设计好的函数计算出存储的位置，我们把这种函数就叫做哈希函数。那这次我们设计的哈希函数就是y=x/10，其中x表示存储的数值，y表示存储数值的索引。下面就将数据{10，20，30，40，50}存入哈希表中。

图表 2哈希表

在图表2的基础上，假如现在需要查找30，只需将目标值带入哈希函数中，计算得到目标值的索引是5，就可以在数组中找到目标值。

如果需存放的数据是{1，11，5，15，25}这样的数据，此时需要重新设计一个哈希函数y=x%10，

图表 3哈希表

如果这样存储的话，在查找的时候就不能马上找到目标值，那有什么解决方法呢？

此时就可以用到线性解决法。

1和11代入函数中结果都是1，那么元素1就放在索引1的位置，元素11放在索引2的位置。元素5、15、25分别应放在索引5、6、0的位置，最终存放好的顺序如图表4所示

图表 4

以元素11为例，在查找时，代入哈希函数，11%10 = 1，可以得出元素11的索引为1，将索引1里面的元素和目标值比较，如果比较不成功，就在此索引值的基础上往后移动一位比较，直到对比成功。

代码如下：

#include <stdio.h>

#define N 10   //指定哈希表的长度

//自定义哈希函数

int hash(int value) {

    return value % 10;

}

//创建哈希表

void creatHash(int arr[5], int hashArr[N]) {

    int i,index;

    //将序列中每个元素存储到哈希表

    for (i = 0; i < 5; i++) {

        index = hash(arr[i]);

        while(hashArr[index % N] != 0) {

            index++;

        }

        hashArr[index] = arr[i];

    }

}

//实现哈希查找算法，hashArr 表示哈希表，value 为要查找的目标元素

int hash_search(int* hashArr, int value) {

    int hashAdd = hash(value);             //查找目标元素所在的索引

    while (hashArr[hashAdd] != value) {    // 如果索引位置不是目标元素，则发生了碰撞

        hashAdd = (hashAdd + 1) % N;       // 根据线性探测法，从索引位置依次向后探测

        //如果探测位置为空，或者重新回到了探测开始的位置（即探测了一圈），则查找失败

        if (hashArr[hashAdd] == 0 || hashAdd == hash(value)) {

            return -1;

        }

    }

    //返回目标元素所在的数组下标

    return  hashAdd;

}

int main()

{

    int hashAdd;

    int hashArr[N] = {0};

    int arr[5] = {10,20,30,40,50};

    creatHash(arr, hashArr);

    hashAdd = hash_search(hashArr, 50);

    //如果返回值为 -1，表明查找失败，反之则返回目标元素所在的位置

    if (hashAdd == -1) {

        printf("查找失败 ");

    }

    else {

        printf("查找成功，目标元素所在哈希表中的下标为：%d", hashAdd);

    }

    return 0;

}