文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 文学 > 哈希表快速查找
侵权投诉

哈希表快速查找

一种哈希表快速查找的改进方法

维普资讯 doc.guandang.net

C 315/ P N4-2 8 T I S 1 0— 3 X S N 0 7 1 0

计算机工程与科学 C OMP E NGI E NG& S I N UT R E NE RI C E CE

20 0 8年第 3 O卷第 9期 Vo . 0, ., 0 8 1 3 No 9 2 0

文章编号:0 71 O 2O )90 6—3 10—3 X(0 8 0—0 60

一

种哈希表快速查找的改进方法 O a h Ta l fH s b e 马如林。蒋华。张庆霞

An I p o e s a c i g M e h d m r v d Fa tSe r h n to

MA R - n JA G a Z A igxa ul,I N Hu。 H NG Q n -i i

(桂林电子科技大学计算机与控制学院,广西桂林 5 1 0 ) 4 0 4 (col f o ue n o t lG inU i ri l t ncT cn lg, ul 4 0 4C ia Sh o o mp t adC nr, ul nv st o Ee r i eh o yG in5 10, hn ) C r o i e y f co o i

摘要:哈希表由于其速度快的优点在数据查询中有着广泛的应用。本文在结合冲突解决机制和数据元素被查找的先验概率的基础上,出了一种提高哈希表查找效率的优化方法,提并对该方法在链地址法处理哈希冲突的情况下进行了理论分析,与原哈希表方法相比,该方法降低了冲突时执行查询的查找长度,而使查询响应时间更短。最后对该方法进行从了实例验证,实验结果表明,新方法是有效并且简便的。 Abta t Ha h tbeh sb e d l sd i aaq ey src: s a l a en wiey u e n d t u r .Thsp p rp t o wa d a p i z t nm eh dwhc a i a e u sfr r n o t miai to ih i - o r p o e a hn, a e nac n l ts ligm eh ns a d t ep irp o a it ft esa c e l e t. u temo e t i rv sh s ig b s do o fi -ovn c a im n h r r b bl y o h e r h d ee n s F rh r r,hs c o i m p p ra ay e h o eial o t i m eh d daswj a s- o f csi h iig t d r se .C mp e vt h

r i a e n l zst e rtcl h w hs y to e l t h rh c n it c ann a d e ss o a d、ih t eo i - h l n he r g n l a h me h d,h s ag rt m e u e h e r h n e g h wh n c n l t c u o a h r e h e c in o e r h n . a s t o s t i o ih r d c st es a c ig ln t e o f c so c r s st s o t n t e r a t fsa c i g h l i o o F n l, h x e i n ss o t a h sn w t o r fe t e a d c n ie i a l t e e p rme t h w h tt i e me h d i mo ee c i n o c s. y s v

关键词:哈希表;查询;希冲突;哈先验概率 Ke r s H a h t b e q e; s o l in; ro r b b l y y wo d: s a l; u r Ha h c li o p i rp o a i t y s i

中图分类号: P 1 T 31

文献标识码: A 意键 K有:,

1引言 随着信息的迅猛发展,人们对信息的需求不断增长,常

0 H ( ) m一 1 0≤ i≤ Ki≤,≤~ 1

这样,就可以利用函数 H将数据集中的元素映射到表 A中, K ) H(便是 K在表中的存储位置。然而,由于数据

常需要使用搜索引擎来解决日常生活的大量问题,中使其用的一项关键技术就是数据查找。数据查找正成为人们每天生活的一部分。因此,如何提高数据查找的效率是工程 师们不断研究的课题。 数据查找一般可分为如下几种:顺序匹配、二分查找和哈希查找。顺序匹配需要一个个地匹配,以效率低下,所不

集中各元素键的取值可能有一个很大的范围,以即使当所数据集中的元素个数不是很多时,很难选取出一个合适也的哈希函数 H,它能保证对于任意不同的 K K有 H和 ( ) Ki≠H( ) Kj。若 Ki≠, H( )而 Ki=H( )则这种现 Ki, 象称为冲突现象,一般称之为哈希冲突。 处理哈希冲突的方法也有很多,如链地址法、线形探测

太适合大规模查找;二分查找需要数据有序;而哈希查找方

再散列、再散列法、立一个公共溢出区等方法。但是,建在建立哈希表处理这些冲突时,

我们往往不会考虑发生冲突时提高效率的解决冲突方法。比如,字符串 s t和 S 2的哈希值相同,而在实际情况下,找 S的频率远远高于 S;查 z 而如果哈希表在建立时未将其作为一个考虑因素,使得 s 连接在 S之后,。查找效率非常低下,尤其是在处理大批相同哈希值的情况下。所以,本文提出了一种基于键被查找

法由于其查找速度快,查询、插入、删除容易操作[等原因】] 而获得了广泛的应用,网络处理[、如 2垃圾邮件过滤[、] 3数]据库连接查询[和中文分词[等。 ]] 哈希查找的基本原理:设置一个长度为 m的表 A,用 一

一

个哈希函数 H把数据集中的 n个关键字 (也称为键 )唯地转换成 O~m一1围内的数值,范即对于数据集中的任 ÷收稿日期:0 71—4修订日期:0 80—4 2 0-12; 2 0-12

作者简介:马如林 (90 )男, 18一,江苏盐城人,硕士生,研究方向为数据库和网络信息安全;蒋华,博士,副教授,研究方向为空间数据库技术和网络信息安全;张庆霞,士生,硕研究方向为计算机辅助软件工程。 通讯地址:4 0 4广西桂林市桂林电子科技大学计算机与控制学院; l 3 7 3 4 1; - i rl ma malcm 5 10 Te:1 98 4 0 2 E mal ui@g i o: n . A d es S h o f o u e n n r l Gul ie s y o lcr n c c n lg,Gul, a g i 4 0 4 P R ia d rs: c o l mp tra d C to, in Unv r i f e t is oC o i t E o Te h oo y i n Gu n x 1 0, . Chn i 5

哈希表快速查找

第1页

热门文档

相关文档

  • 一种哈希表快速查找的改进方法

    一种哈希表快速查找的改进方法_IT/计算机_专业资料。哈希表由于其速度快的优点在数据查询中有着广泛的应用。本文在结合冲突解决机制和数据元素被查找的先验概率的基...

  • 7.哈希表查找(链地址法)

    7.哈希表查找(链地址法)_IT/计算机_专业资料。//哈希表查找 //链地址法 #...8.交换排序(快速排序) 8.排序全部代码 8.选择排序(堆排序) 8.选择排序(直接...

  • 哈希表及哈希表查找相关概念

    哈希表概念 哈希表概念 对于动态查找表而言,1) 表长不确定;2)在设计查找表时,只知道关 键字所属范围,而不 知道确切的关键字。因此,一般情况需建立一个函数...

  • 一种基于哈希表和Trie树的ip路由快速查找算法

    一种基于哈希表和Trie树的ip路由快速查找算法_互联网_IT/计算机_专业资料。一种基于哈希表和 !"#$ 树的快速 %& 路由查找算法崔尚森 &!! & ! 张白一 ! ...

  • 哈希查找表

    哈希查找表_计算机/互联网_科技_PPT专区。哈希查找表 为什么 构造哈希表 哈希表 的概念 哈希函数 的构造方法 讲课思路 冲突 处理方法 哈希表的 查找分析 为什么使...

  • 查找与哈希表

    在处理线性表时,如果既希望能够快速查找, 又要经常动态变化,则可以采用分块查找...AVL树:每个结点的平衡因子的绝对值 不超过1的二叉排序树 哈希表Hash(散列表) ...

  • 哈希表查找

    哈希表查找_计算机软件及应用_IT/计算机_专业资料 暂无评价0人阅读0次下载举报文档 哈希表查找_计算机软件及应用_IT/计算机_专业资料。哈希表查找: #include<...

  • 哈希表查找的设计

    哈希表查找的设计一.问题描述:哈希表查找的设计:设哈希表长为 20,用除留余数法构造一个哈希函数,以开放定址法 中的线性探测再散列法作为解决冲突的方法,编程...

  • 哈希表(Hash)的查找

    详细讲解哈希表以及哈希表的查找方式。哈希表(Hash) 哈希表(Hash)的查找 一、哈希表相关...

  • 哈希表的建立与查找

    哈希表的建立与查找_天文/地理_自然科学_专业资料。哈希表的建立与查找 李德江...哈希表快速查找 3页 免费 哈希查找,哈希表 3页 免费喜欢此文档的还喜欢 ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email