文章目录

  • 前言
  • 一、实现哈希表的主要思路
  • 二、解决哈希冲突的方法
  • 三、代码实现
    • 1.简单哈希表的实现
      • 结果展示
    • 2.线性探查法
      • 结果展示
  • 四、总结
  • 五、随便聊聊

前言

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。百度百科-哈希表

一、实现哈希表的主要思路

1、哈希表分为两个过程，一是将数据存入哈希表中，二是在哈希表中查找数据(这也是哈希表要实现的主要功能——哈希查找)
2、首先我们拥有一组数据(value)，需要通过计算找出相应的key值，计算的方法称作哈希函数。在数组中key对应的是数组的下标，value是下标中的数据。
3、此时我们能通过哈希函数计算出value对应的key，也能通过key在数组中找到value，哈希表基本的存储和查找就可以实现了。
4、当两个value通过哈希函数计算出相同的key，在数组中一个下标无法同时存储两个数据，这就产生了冲突也就是哈希冲突

二、解决哈希冲突的方法

解决哈希冲突的方法有很多，在本文中笔者只实现一种简单的解决方法——线性探查法。该方法的思路也很简单，就是当产生哈希冲突时，顺序的查找下一个空的位置，但是该方法也存在一定的缺陷。

三、代码实现

1.简单哈希表的实现

#include#include#include//哈希函数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//哈系函数，关系为key=value%13int 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);elseprintf("没找到！\n");}

结果展示

四、总结

1、哈希表中，哈希函数好坏往往起着很重要的作用，一个好的哈希函数，在特定的情境下，可能很少甚至不会出现哈希冲突。
2、哈希冲突的解决方法也有很多，至于我为什么只写一种，那肯定是因为第二种的代码我还没写，哈哈！

五、随便聊聊

1、虽然我写的可能没人看，但是每写完一篇都是对学过的知识进行一次总结，对我来说效果还是不错的。
2、当然这只是一部分原因，还有就是在书本上学的数据结构，只感觉他是固定的，死的知识，但是当你真正去实现代码的时候，却发现他其实是灵活的，随心所欲的，当然基本的原理还是一个，但是它却有着你自己的风格，哈哈，想想还觉得有点酷。
3、最最主要的原因还是觉得，在查找算法的资料时，总觉得它很高大上，说的不是很通俗，就更别提易懂了，当然我是小白肯定占绝大部分原因。可是我还是觉得，虽然我处于一只脚入门的阶段，但是还是想给准备学习算法的同学一个更加简单，接地气的算法实现过程。避免出现我的情况，下定决心想学学，结果看的一脸懵！
4、emmm 今天就说到这……