2. 首页 > 经验  > 正文

哈希查找

哈希查找

哈希查找是通过计算数据元素的存储地址进行查找的一种方法。

基本介绍

中文名：哈希查找解释：计算数据元素的存储地址进行查找操作步骤个数：3步解决冲突方法：开放地址法、链地址法

定义

哈希查找的操作步骤：
⑴用给定的哈希函式构造哈希表；
⑵根据选择的冲突处理方法解决地址冲突；
⑶在哈希表的基础上执行哈希查找。

操作步骤

step1 取数据元素的关键字key，计算其哈希
函式值。若该地址对应的存储
空间还没有被占用，则将该元素存入；
否则执行step2解决冲突。
step2 根据选择的冲突处理方法，计算关键字
key的下一个存储地址。若下一个存储地
址仍被占用，则继续执行step2，直到找
到能用的存储地址为止。
哈希查找步骤为：
设哈希表为HST[0~M-1]，哈希函式取H（key），解决冲突的方法为R（x）；
Step1 对给定k值，计算哈希地址 Di=H（k）；若HST为空，则查找失败；
若HST=k，则查找成功；否则，执行step2（处理冲突）。
Step2 重複计算处理冲突的下一个存储地址 Dk=R（Dk-1），直到HST[Dk]为
空，或HST[Dk]=k为止。若HST[Dk]=K，则查找成功，否则查找失败。
哈希查找的本质是先将数据映射成它的哈希值。哈希查找的核心是构造一个哈希函式，它将原来直观、整洁的数据映射为看上去似乎是随机的一些整数。
哈希查找的产生有这样一种背景——有些数据本身是无法排序的(如图像)，有些数据是很难比较的(如图像)。如果数据本身是无法排序的，就不能对它们进行比较查找。如果数据是很难比较的，即使採用折半查找，要比较的次数也是非常多的。因此，哈希查找并不查找数据本身，而是先将数据映射为一个整数(它的哈希值)，并将哈希值相同的数据存放在同一个位置一即以哈希值为索引构造一个数组。
在哈希查找的过程中，只需先将要查找的数据映射为它的哈希值，然后查找具有这个哈希值的数据，这就大大减少了查找次数。如果构造哈希函式的参数经过精心设计，记忆体空间也足以存放哈希表，查找一个数据元素所需的比较次数基本上就接近于一次。

解决冲突

影响哈希查找效率的一个重要因素是哈希函式本身。当两个不同的数据元素的哈希值相同时，就会发生冲突。为减少发生冲突的可能性，哈希函式应该将数据儘可能分散地映射到哈希表的每一个表项中。解决冲突的方法有以下两种：
(1) 开放地址法
如果两个数据元素的哈希值相同，则在哈希表中为后插入的数据元素另外选择一个表项。
当程式查找哈希表时，如果没有在第一个对应的哈希表项中找到符合查找要求的数据元素，程式就会继续往后查找，直到找到一个符合查找要求的数据元素，或者遇到一个空的表项。
(2) 链地址法
将哈希值相同的数据元素存放在一个鍊表中，在查找哈希表的过程中，当查找到这个鍊表时，必须採用线性查找方法。
例3. 6是一个简单的哈希查找算法程式，你可以将它和本章结尾的有关代码一起编译连线成一个可执行程式。
例3．6一个简单的哈希查找算法程式
1: #include<stdlib.h>
2: #include<string.h>
3: #include "list.h"
4: #include "hash.h"
5:
6: #define HASH_SIZE 1024
7:
8: static listnode_t *hashTable[HASH_SIZE];
9:
10: void insert(const char * s)
11: {
12: listnode_t *ele = newNode((void * ) s)
13: unsigned int h = hash(s) % HASH_SIZE;
14:
15: ele->next = hashTable[h]
16: hashTable[h] = ele;
17: }
18:
19: void print (void)
20: {
21: int h;
22:
23: for (h = 0; h < HASH_SIZE; h++)
24: {
25: listnode_t * lp = hashTalbe[h];
26:
27: if(lp == NULL)
28:continue;
29: prinTF.htm target=_blank class=infotextkey>TF("[%d]" , h);
30: while (lp)
31: {
32:printf("\t'%s'" , lp->u.str)
33:lp = ip->next;
34: }
35: putchar ('\n');
36: }
37: }
38:
39: const char *search(const char *s)
40: {
39: unsigned int h = hash(s) % HASH_SIZE;
42: listnode_t * lp = hashTable[h];
43:
44: while (lp)
45: {
46: if (! strcmp (s, lp->u.str))
47:return lp->u.str;
48: lp = lp->next;
49: }
50: return NULL;
51: }
请参见：
3. 4 哪一种查找方法最方便?
3．5 哪一种查找方法最快?
3．8 怎样查找鍊表中的数据?
_____________________________________________
以下是一个简单示例：
#include<iostream>
#include<string>
using namespace std;
#define m 5 //人数
#define n 10 //哈希表长度
#define q 7 //随机数
struct name{
char *py;
int k;
};
name namelist[n];
struct hash{
char *py;
int k;
int s;
};
hash hashlist[n];
void listname()
{
char *f;
int s0,r,i;
namelist[0].py="as";
namelist[1].py="sa";
namelist[2].py="d";
namelist[3].py="f";
namelist[4].py="g";
for(i=0;i<m;i++)
{
s0=0;
f=namelist[i].py;
for(r=0;*(f+r)!='\0';r++)
s0+=*(f+r);
namelist[i].k=s0;
}
}
void creathash()
{
int i;
for(i=0;i<n;i++)
{
hashlist[i].py="";
hashlist[i].k=0;
hashlist[i].s=0;
}
for(i=0;i<m;i++)
{
int sum=0;
int adr=(namelist[i].k)%q;
int d=adr;
if(hashlist[adr].s==0)
{
hashlist[adr].py=namelist[i].py;
hashlist[adr].k=namelist[i].k;
hashlist[adr].s=1;
}
else
{
while(hashlist[d].k!=0)
{
d=(d+namelist[i].k%5+1)%q;
sum+=1;
}
hashlist[d].py=namelist[i].py;
hashlist[d].k=namelist[i].k;
hashlist[d].s=sum+1;
}
}
}
void find()
{
string nam;
int s0=0,r,sum=1,adr,d;
cout<<"请输入姓名的拼音："<<endl;
cin>>nam;;
for(r=0;r<20;r++)
s0+=nam[r];
adr=s0%q;
d=adr;
if(hashlist[adr].k==s0)
cout<<"姓名:"<<hashlist[d].py<<" "<<"关键字:"<<s0<<" "<<"查找长度为: 1"<<endl;
else if(hashlist[adr].k==0)
cout<<"无此记录！"<<endl;
else
{
int g=0;
while(g==0)
{
d=(d+s0%5+1)%q;
sum+=1;
if(hashlist[d].k==0)
{
cout<<"无此记录！"<<endl;
g=1;
}
if(hashlist[d].k==s0)
{
cout<<"姓名:"<<hashlist[d].py<<" "<<"关键字:"<<s0<<" "<<"查找长度为: 1"<<endl;
g=1;
}
}
}
}
void display()
{
int i;
float av=0;
for(i=0;i<n;i++)
{
cout<<"姓名:"<<hashlist[i].py<<" "<<"关键字:"<<hashlist[i].k<<"搜寻长度："<<hashlist[i].s<<endl;
}
for(i=0;i<7;i++)
{
av+=hashlist[i].s;
}
av/=m;
cout<<"平均查找长度：="<<av<<endl;
}
int main()
{
char x;
listname();
creathash();
cout<<"d. 显示哈希表 f. 查找 任意键退出 请选择："<<endl;
while(cin>>x){
if(x=='d'){display(); cout<<endl;}
else if(x=='f'){find();cout<<endl;}
else break;
}
return 0;
}

本文由'姒凌蝶'发布，不代表演示站立场，转载/删除联系作者，如需删除请-> 关于侵权处理说明。

哈希查找地址元素数据冲突

相关推荐

  • 2升是多少毫升

    2升是多少毫升

    毫升,方法,单位,是多少,计量单位，2000毫升毫升是体积单位，相当于立方厘米。体积的主要单位是升。1升=1000毫升，1毫升=1立方厘米。民间也有一种以“升”为计量单位的方法，一升是一斗的十分之一，一升米就是4000克，也就是8市斤（16两=1斤）。过去人在没有标准度量衡的基础上，发明了这种以容量来测量稻谷的方法，还是很好用的。有很多文学作品中揭露了地主放高利贷采取了小升（斗）出，大升（斗）进的手段欺诈农民。反映了封建社会的剥削制度。mL...

  • 微信支付可以注销吗?怎么注销?

    微信支付可以注销吗?怎么注销?

    微信支付注销,微信支付可以注销吗，注销,微信支付,金额,支付,方法,零钱,想用,您好,width,style，不想用微信支付，可以注销微信支付吗？怎么注销?您好，微信支付是可以注销的，以下是注销方法：微信→钱包→支付管理→注销微信支付注意：当零钱和零钱通里有金额时，是无法注销的！...

  • 一厘米等于几毫米

    一厘米等于几毫米

    地址,主存储器,几毫米,单位,存取速度，10毫米厘米是一个长度计量单位，等于一米的百分之一。长度单位，英语符号即缩写为：cm.，1厘米=1/100米。1cm（厘米）=10mm（毫米）=0.1dm（分米）=0.01m（米）。毫米（millimeter），又称公厘（或公釐），是长度单位和降雨量单位，英文缩写mm。10毫米相当于1厘米，100毫米相当于1分米，1000毫米相当于1米（此即为毫的字义）。英文缩写mm（或　毫米，又称公厘（或公釐），是...

  • 41开头的身份证是哪里的

    41开头的身份证是哪里的

    地址,计算,数字,校验码,县级市，河南省41开头的身份证是河南省的。河南省地势呈望北向南、承东启西之势，地势西高东低，由平原和盆地、山地、丘陵、水面构成；地跨海河、黄河、淮河、长江四大流域。大部分地处暖温带，南部跨亚热带，属北亚热带向暖温带过渡的大陆性季风气候；河南地处沿海开放地区与中西部地区的结合部，是中国经济由东向西梯次推进发展的中间地带。河南省下辖17个地级市，1个省直辖县级市，21个县级市，83个县，53个市辖区。居民身份证结构和形...

  • gta5怎么拖车

    gta5怎么拖车

    拖车,位置,红色,尾部,驾驶，软件/系统品牌型号：联想小新Air-14 2020系统版本：Windows 10软件版本：GTA5版本1.53步骤/方法1/7 首先进入gta5游戏中按ESC打开地图，红色箭头所指处就是废车场的位置； 2/7 来到红色箭头所指处处就能找到拖车； 3/7 按下【F】键，可以进入到拖车驾驶位； 4/7 把拖车的尾部对准其它车的头部或者尾部就可以把它勾住了；...

  • 支付宝乘车码在哪里？支付宝乘车码开

    支付宝乘车码在哪里？支付宝乘车码开

    支付宝乘车码,支付宝乘车码在哪里,支付宝乘车码开通使用方法，乘车,支付宝,开通,提示,公交车,使用方法,屏幕,账户,支付,扣款，支付宝乘车码在哪里？支付宝乘车码开通使用方法介绍，探其财经网支付宝乘车码相关知识问答。打开支付宝，点击首页上面的【付钱】——点击下方【乘车码】——选择你需要开通的城市开通即可。使用时，只要打开【乘车码】对着公交车刷码的地方即可。在公交车的二维码机具上刷码：机具&ld...

  • 250mg等于多少g

    250mg等于多少g

    克拉,进制,药物,250mg,单位，0.25g毫克一种国际通用的质量单位，通常用来测量液体和药物成分，中文释义是千克的百万分之一，克的千分之一。克是质量单位，一克是12原子的质量，重量大约相当于一立方厘米水在室温中的重量。换算方法是1克等于1000毫克，因此250毫克等于0.25克。克与毫克都不是中国古代的重量单位，一克等于1000毫克。克与毫克这些重量单位之间逐级的换算是千进制。1千克等于1000克，一克等于1000毫克，1毫克等于100...

  • 一弧度等于多少度

    一弧度等于多少度

    度量,缩写,多少度,单位,平面，57.29578度在数学和物理中，弧度是角的度量单位。它是由国际单位制导出的单位，单位缩写是rad。定义：弧长等于半径的弧，其所对的圆心角为1弧度。即两条射线从圆心向圆周射出，形成一个夹角和夹角正对的一段弧。当这段弧长正好等于圆的半径时，两条射线的夹角的弧度为1。弧度制顾名思义，就是用弧的长度来度量角的大小的方法。单位弧度定义为圆周上长度等于半径的圆弧与圆心构成的角。由于圆弧长短与圆半径之比，不因为圆的大小而...

  • 征信不良记录怎么消除？多久消除？

    征信不良记录怎么消除？多久消除？

    征信不良记录消除,征信不良记录多长时间消除,征信不良记录怎么消除，贷款,银行,信用,执行,方法,报告,机构,财产,修改,义务，征信不良记录多长时间消除？征信不良记录怎么消除？征信不良记录可以消除吗？有什么影响？探其财经为您解答个人征信记录知识。贷款已经结清，或者信用卡已经注销，之前的不良信息还会在信用报告上展示多久? 答：根据《征信业管理条例》的规定，不良信息自不良行为或者事件终止之日起展示5年。如果有不良记录，征信中心是否能够修...

  • 扑克牌背面认牌公式

    扑克牌背面认牌公式

    数字,方法,编程,联想,训练，知牌奥秘无论谁的新旧牌,不管别人怎样倒洗,由别人发牌(自己不发牌)不看牌面,就知道别人发出来的每张是什么牌扑克牌背面认牌公式1、洗牌绝技无论谁的新旧纸牌,任意洗叠,都能随心所欲的发给自己想要的好牌。2、发牌绝技无论谁的新旧纸牌,任人洗叠,均可发给自己想要的好牌,并且发给别人大牌而自己的牌更大,如别人三个K自己三个A。3、变牌绝技无论谁的新旧纸牌、由谁洗叠、把发给自己的小牌瞬间变成自己想要的大牌,如2、4、6变三...

红色 疼痛 操作 水具 平滑 精神 蜜蜂 神仙水 手表 中文 有什么区别 肌肉 位置 治疗 貔貅 寓意 等待 有什么 是什么意思 祛痘 自制 效果 鞘氨醇 牌子 刺激性 黄瓜 调整 分泌 导致 幻影 品牌 价格 步骤 牛奶 缓解 部位 过敏 分离 有很多 银手镯 价位 功效 发现 碘酒 成分 档次 公司 作用 吉利 回弹 使用方法 免税店 混合 脸部 裤子 指腹 右手 保湿 情况 中国 清洗 恢复 是什么 口红 性能 力度