散列表查找 柔情只为你懂 2023-07-09 14:26 14阅读 0赞 **定义** 通过散列函数寻找某个关键字所存在的位置,利用散列技术存储在一块连续的存储空间中,这块连续的存储空间称为散列表,对应的存储位置成为散列地址。 ![在这里插入图片描述][20200229102306640.png] **冲突** 在查找存储位置的时候会存在关键字不同,但是存储位置相同,即对应的散列函数值相同,这种情况即“冲突”。 **散列函数的构造** 散列函数有很多构造方法,比如直接定址法、除留余数法等等,但不是都适用,因此好的散列函数应该具有:计算简单、散列地址分布均匀的特点 **构造方法** * 直接定址法 这个方法比较直接,就和它的名字一样,直接。比如年龄统计,一个年龄为66的人,那函数就可以直接以66为值。 * 平方取中法 一个值为1234的关键字,sqrt(1234)=1522756,在取最后三位即756作为散列地址。这种方法造成冲突的概率比较大。 * 除留余数法(最常用) 对表长为m,关键字为x的散列函数公式可以表示为:f(x)= x mod p(p<=m),为了尽量避免冲突,选好p是关键。通常选取p为小于等于表长m的最小质数。 **处理散列冲突** f(x)= x mod p;就比如x=37、47,p等于12的时候,37是不是就和47冲突了,所以就要处理冲突来使散列地址发布均匀。 可以做一下改变: ![在这里插入图片描述][20200229104108215.png] 这样f(37)=1,而f(32)=2就避免了冲突,但是光这样无法达到均匀分布,所以可以改善一下di数组: ![在这里插入图片描述][20200229104241370.png] [20200229102306640.png]: https://img-blog.csdnimg.cn/20200229102306640.png [20200229104108215.png]: https://img-blog.csdnimg.cn/20200229104108215.png [20200229104241370.png]: https://img-blog.csdnimg.cn/20200229104241370.png
相关 查找-散列表(哈希表)详解篇 散列表 散列表(Hash Table)是一种基于散列函数(Hash Function)的数据结构,用 于实现快速的数据查找。散列函数将键(Key)映射到存 向右看齐/ 2023年10月14日 10:46/ 0 赞/ 85 阅读
相关 散列表查找 定义 通过散列函数寻找某个关键字所存在的位置,利用散列技术存储在一块连续的存储空间中,这块连续的存储空间称为散列表,对应的存储位置成为散列地址。 ![在这里插入图片描述 柔情只为你懂/ 2023年07月09日 14:26/ 0 赞/ 15 阅读
相关 散列表的查找 对给定的关键字key,用一个函数H(key)计算出元素地址,由此而得散列表(Hash表,哈希表),其中函数H(key)称为散列函数 此函数值称为散列地址。 然而,在实际应用 た 入场券/ 2023年02月28日 05:24/ 0 赞/ 133 阅读
相关 散列表的查找 为什么使用散列表?散列表在查找是有优势的,举例: 1.顺序表查找:一个一个遍历查找 2.有序表:可以通过二分法查找 ....... 那散列表的查找通过一个f(value 迈不过友情╰/ 2022年08月07日 09:41/ 0 赞/ 187 阅读
相关 哈希表(散列表)查找的详解 前言 博客编写人:Willam 博客编写时间:2017/3/29 博主邮箱:2930526477@qq.com(有志同道合之人,可以加qq交流交流编程 怼烎@/ 2022年06月18日 02:42/ 0 赞/ 350 阅读
相关 散列表 1 定义 散列技术是在记录的存储位置和它的关键位置之间建立一个确定的对应关系`f`,使得每个关键字`key`对应一个存储位置`f(key)`,即: 存储位置 = 不念不忘少年蓝@/ 2022年04月04日 06:25/ 0 赞/ 268 阅读
相关 散列表 散列方法不同于顺序查找、二分查找、二叉排序树及B-树上的查找。它不以关键字的比较为基本操作,采用直接寻址技术。在理想情况下,无须任何比较就可以找到待查关键字,查找的期望时间为O 一时失言乱红尘/ 2022年03月22日 17:06/ 0 赞/ 440 阅读
相关 散列表 直接寻址表 假设某个动态集合中的每个元素取自于U=\{0,1,2,…,m-1\},这里的m不是一个很大的数,假设没有两个元素具有相同的关键字。我们用一个数组(直接寻址表), 淩亂°似流年/ 2021年09月26日 14:26/ 0 赞/ 426 阅读
还没有评论,来说两句吧...