文章目录
- 前言
- 一、实现哈希表的主要思路
- 二、解决哈希冲突的方法
- 三、代码实现
- 1.简单哈希表的实现
- 结果展示
- 2.线性探查法
- 结果展示
- 四、总结
- 五、随便聊聊
前言
散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。百度百科-哈希表
一、实现哈希表的主要思路
1、哈希表分为两个过程,一是将数据存入哈希表中,二是在哈希表中查找数据(这也是哈希表要实现的主要功能——哈希查找)
2、首先我们拥有一组数据(value),需要通过计算找出相应的key值,计算的方法称作哈希函数。在数组中key对应的是数组的下标,value是下标中的数据。
3、此时我们能通过哈希函数计算出value对应的key,也能通过key在数组中找到value,哈希表基本的存储和查找就可以实现了。
4、当两个value通过哈希函数计算出相同的key,在数组中一个下标无法同时存储两个数据,这就产生了冲突也就是哈希冲突
二、解决哈希冲突的方法
解决哈希冲突的方法有很多,在本文中笔者只实现一种简单的解决方法——线性探查法。该方法的思路也很简单,就是当产生哈希冲突时,顺序的查找下一个空的位置,但是该方法也存在一定的缺陷。
三、代码实现
1.简单哈希表的实现
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//哈希函数
int hash_fun(int age)
{
return age-1;
}
//保存数据到哈希表
void save_by_hash(int *a,int age,int n)
{
a[hash_fun(age)]=n;
return ;
}
//在哈希表中查找
int find_by_hash(int *a,int age)
{
return a[hash_fun(age)];
}
//保存年龄和人口数,查找年龄输出人口
int main()
{
int a[100]={0},i,age,n;
for(i=0;i<5;i++)
{
printf("请输入年龄和相应的人口:");
scanf("%d%d",&age,&n);
save_by_hash(a,age,n);
}
printf("请输入要查找的年龄:");
scanf("%d",&age);
n=find_by_hash(a,age);
printf("人口数是:%d\n",n);
}
结果展示
2.线性探查法
输入一组数据,返回数据在数组中的位置,数据经哈希函数计算会出现哈希冲突。
#include<stdio.h>
//哈系函数,关系为key=value%13
int hash_fun(int *b,int n)
{
int temp=n%13;
while(b[temp]!=0)
{
temp++;
}
return temp;
}
//将数据保存到哈希表中
void save_by_hash(int *b,int n)
{
b[hash_fun(b,n)]=n;
}
//在哈希表找到数据
int find_by_hash(int *b,int n)
{
int temp=n%13;
while(b[temp]!=0)
{
if(b[temp]==n)
return temp;
temp++;
}
return -1;
}
int main()
{
int n,i,a[]={23,34,14,38,46,16,68,15,7,31,26};
int b[15]={0};
for(i=0;i<11;i++)
{
save_by_hash(b,a[i]);
}
for(i=0;i<15;i++)
{
printf("%-5d",b[i]);
}
printf("\n");
printf("请输入要查找的数字:");
scanf("%d",&n);
int x=find_by_hash(b,n);
if(x>=0)
printf("找到了,在数组的第%d位!\n",x);
else
printf("没找到!\n");
}
结果展示
四、总结
1、哈希表中,哈希函数好坏往往起着很重要的作用,一个好的哈希函数,在特定的情境下,可能很少甚至不会出现哈希冲突。
2、哈希冲突的解决方法也有很多,至于我为什么只写一种,那肯定是因为第二种的代码我还没写,哈哈!
五、随便聊聊
1、虽然我写的可能没人看,但是每写完一篇都是对学过的知识进行一次总结,对我来说效果还是不错的。
2、当然这只是一部分原因,还有就是在书本上学的数据结构,只感觉他是固定的,死的知识,但是当你真正去实现代码的时候,却发现他其实是灵活的,随心所欲的,当然基本的原理还是一个,但是它却有着你自己的风格,哈哈,想想还觉得有点酷。
3、最最主要的原因还是觉得,在查找算法的资料时,总觉得它很高大上,说的不是很通俗,就更别提易懂了,当然我是小白肯定占绝大部分原因。可是我还是觉得,虽然我处于一只脚入门的阶段,但是还是想给准备学习算法的同学一个更加简单,接地气的算法实现过程。避免出现我的情况,下定决心想学学,结果看的一脸懵!
4、emmm 今天就说到这……
更多推荐
C语言算法基础——哈希表的实现
发布评论