哈希查找算法之线性探测法(开放地址法)
哈希查找是一种时间复杂度为O(1)的一种效率极高的查找方法,与常见的遍历查找不同,哈希算法是通过数组元素数值与哈希表下标构建的一种查找方法,因此我们不需要遍历整个数组,即可对其进行访问。...
目录
1、什么是哈希算法
哈希查找是一种时间复杂度为O(1)的一种效率极高的查找方法,与常见的遍历查找不同,哈希算法是通过数组元素数值与哈希表下标构建的一种查找方法,因此我们不需要遍历整个数组,即可对其进行访问。
2、哈希算法的特点
1、哈希算法具有特殊的哈希表
2、哈希算法不用遍历即可查找访问目的元素
3、哈希算法基于一个特殊的哈希函数所构建
4、哈希表存在哈希碰撞(哈希冲突)
3、什么是哈希表
哈希表又称散列表,是一种存储结构,通常用来存储多个元素。和其它存储结构(线性表、树等)相比,哈希表查找目标元素的效率非常高。每个存储到哈希表中的元素,都配有一个唯一的标识(又称“索引”或者“键”),用户想查找哪个元素,凭借该元素对应的标识就可以直接找到它,无需遍历整个哈希表。
通过将原数组数据代入hash函数得到对应的下标,并将元素存放到哈希表对应下标的位置,比如我们的hash函数为:
y=x%7
此时假设我需要存放37这个数到我的hash表中,y=37%7=2,那么我的37就存放到哈希表中下标为2的位置。
4、哈希碰撞
从上述描述中我们可以看出,如果有两个数的余数相等,那么我的存储位置就会是在哈希表中的同一个下标之下,我们称这种情况为哈希碰撞。
假设我此时原数组中存在以下数据:
35 74 2 31 39 98 67 56 58 87
按照我们的哈希函数 y=37%7=2 推导可知,我们的哈希表存储应该如图所示:
通过上面这个实例可以看出,选择一个合适的哈希函数可以极大地减少碰撞的发生,此处我们选择这个hash函数主要摸底在于分析如何利用线性探测法(开放地址法)来解决碰撞的问题。
5、线性探测法(开放地址法)
如图所示,我们在给98和56建立索引是发现,他们余数所在位置此时都已经存放了元素,因此,我们此时就需要查询余数之后的位置是否有空的位置,这其实就和停车的原理相同,从头开始,看下一个是否为空,为空就存放数据。
理论上我们最后的结果如下图所示:
6、代码实现
1、计算原数组元素个数
//计算数组元素个数
int arr_len(int* arr)
{
int* p = arr;
int len = 0;
while (*p != 0) {
printf("%d ", *p);
len++;
p++;
}
printf("\n");
return len;
}
2、查找质数。(对质数取余可以减少碰撞的发生)
//查找小于num并且和num最相近的质数
int prime_number(int num)
{
int p_number = 0;
int i, j;
int quantity = 0;
while (num--) {
j = 0;
for (i = 2; i < num; i++) {
if (num % i == 0) {
j++;
}
}
if (j == 0) {
p_number = num;
break;
}
}
return p_number;
}
3、哈希查找
//哈希表创建
int *Hash(int *arr)
{
int len = arr_len(arr);
int p_num = prime_number(len);
int pos = 0;
static int hash[N] = {0};
for (int i = 0; i < len; i++) {//初始化hash表
hash[i] = -1;
}
for (int i = 0; i < len; i++) {
pos = arr[i] % p_num;
if (hash[pos] == -1) {
hash[pos] = arr[i];
}
else {
int j = 1;
while (hash[pos + j] != -1) {
j++;
}
hash[pos + j] = arr[i];
}
}
return hash;
}
4、主函数调用
int main()
{
int arr[N] = {35, 74, 2, 31, 39, 98, 67, 56, 58, 87};
int *p = Hash(arr);
for (int i = 0; i < 10; i++) {
printf("%d ", p[i]);
}
printf("\n");
return 0;
}
7、结果展示
通过和之前的理论结果对比,我们的hash表此时排列正确!!!
以上即为本次内容,还望大家多多关注,若有错误,还望指正!!!
更多推荐
所有评论(0)