欢迎来到军工软件开发人才培养基地——学到牛牛

哈希查找

时间:2024-05-06 07:01:10 来源:学到牛牛

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

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

图表 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("查找失败\n");

    }

    else {

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

    }

    return 0;

}