数据结构中处理散列冲突的四种方法

这篇具有很好参考价值的文章主要介绍了数据结构中处理散列冲突的四种方法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1 开放定址法

1.1 定义

开放定址法就是一旦发生了冲突,就去寻找下一个空的散列地址

1.2 要求

只要散列表足够大

空的散列地址总能找到,并将记录存入

1.3 线性探测法

数据结构中处理散列冲突的四种方法,考研408,# 数据结构,数据结构,散列冲突

使用该公式用于解决冲突的开放定址法称为线性探测法

对于线性探测法,在出现冲突时,它只能晚后一步一步检测看是否有空位置

假设此时该冲突位置后续没有可用位置,但前面有一个空位置

尽管可以不断地求余数后得到结果,但效率很差

1.4 二次探测法

因此可以改进该算法,增加双向寻找可能的空位置,这种新算法称为二次探测法:

数据结构中处理散列冲突的四种方法,考研408,# 数据结构,数据结构,散列冲突

1.5 随机探测法

此外还有一种方法是,在冲突时,对于位移量di采用随机函数计算得到,我们称为随机探测法

数据结构中处理散列冲突的四种方法,考研408,# 数据结构,数据结构,散列冲突
注意

这里的随机其实是伪随机数

即设置相同的随机种子,则不断调用随机函数的过程中就可以生成不会重复的数列

同时,在查找时,用同样的随机种子,它每次得到的数列也是相同的

因此相同的di就可以得到相同的散列地址

2 再散列函数法

2.1 散列函数

即提供多个散列函数
数据结构中处理散列冲突的四种方法,考研408,# 数据结构,数据结构,散列冲突

2.2 解释

这里的RHi就是不同的散列函数然后每当发生散列地址冲突时

就换一个散列函数计算

相信总会有一个可以把冲突解决掉(todo:: how to search??)

2.3 优点弊端

2.3.1 优点

这种方法能够使得关键字不产生聚集

2.3.2 弊端

当然,相应地也增加了计算的时间

3 链地址法

3.1 定义

将所有关键字为同义词(即哈希地址相同)的记录存储在一个单链表中,我们称这种表为同义词子表

在散列表中只存储所有同义词子表的头指针

3.2 优点弊端

3.2.1 优点

链地址法对于可能会造成很多冲突的散列函数来说

提供了绝不会出现找不到地址的保障

3.2.2 弊端

当然,这也就带来了查找时需要遍历单链表的性能损耗

4 公共溢出区法

即为所有冲突的关键字建立一个公共的溢出区来存放

在查找时,对给定值通过散列函数计算出散列地址后先与基本表的相应位置进行比对如果相等,则查找成功如果不相等,则到溢出表去进行顺序查找如果对于基本表而言,有冲突的数据很少的情况下

公共溢出区的结构对查找性能来说还是非常高的文章来源地址https://www.toymoban.com/news/detail-756195.html

到了这里,关于数据结构中处理散列冲突的四种方法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】哈希表——闭散列 | 开散列(哈希桶)

    🐱作者:一只大喵咪1201 🐱专栏:《数据结构与算法》 🔥格言: 你只管努力,剩下的交给时间! 哈希(Hash):是一种方法,将数据的key值和存储位置建立关系。 在之前学习过的顺序结构以及平衡树中,所有数据的key值和存储位置之间都没有对应的关系。所以在查找一个数据

    2023年04月24日
    浏览(44)
  • 解决Hash(哈希表)冲突的四种方案

    参考鸣谢 解决哈希冲突必须知道的几种方法 小僵鱼 你还应该知道的哈希冲突解决策略 vivo互联网技术 解决哈希冲突的三种方法 kaleidoscopic 每日一题(哈希表及哈希冲突解决办法) 和笙 哈希是一种通过对数据进行压缩, 从而提高效率的一种解决方法 ,但由于哈希函数有限,数据

    2024年02月14日
    浏览(45)
  • 数据结构(顺序结构、链式结构、索引结构、散列结构)

    数据结构,就是一种程序设计优化的方法论,研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算, 目的是加快程序的执行速度、减少内存占用的空间 。 数据的逻辑结构指反映数据元素之间的逻辑关系,而与数据的存储无关,是独立于计算

    2024年02月03日
    浏览(82)
  • 数据结构8 散列函数

    1-1 分数 1 作者 DS课程组单位 浙江大学 Store M elements in a hash table which is represented by an array of size S , the loading density is then M / S . 将M个元素存储在哈希表中,哈希表由大小为S的数组表示,则加载密度为M/S。 T F 1-2 分数 1 作者 冯雁单位 浙江大学 In hashing, functions \\\"insert\\\" and \\\"find\\\" h

    2024年02月07日
    浏览(56)
  • 【数据结构】哈希表的开散列和闭散列模拟

    在顺序和树状结构中,元素的存储与其存储位置之间是没有对应关系,因此在查找一个元素时,必须要经过多次的比较。 顺序查找的时间复杂度为0(N),树的查找时间复杂度为log(N)。 我们最希望的搜索方式:通过元素的特性,不需要对比查找,而是直接找到某个元素。 这一个

    2024年02月22日
    浏览(39)
  • 【数据结构】3.跳表和散列

    跳表可以近似实现二分查找的效果 以下面长度为7的链表举例,该跳表通过3条链表进行存储。假设要查找元素80: 首先在第2级链表查找,因为80大于40,所以在第3个节点右侧查找 然后在第1级链表查找,因为80大于75,所以在第5个节点右侧查找 最后在第0级链表查找,找到元素

    2024年02月08日
    浏览(44)
  • 数据结构——散列函数、散列表

    散列表的基本概念 散列函数的构造方法 处理冲突的方法 散列查找及性能分析 提示:以下是本篇文章正文内容,下面案例可供参考 概念:之前的算法建立在“比较”基础上,效率取决于比较次数 散列函数:将映射成该对应地址的函数,记为Hash(key)=Addr,散列函

    2024年02月07日
    浏览(41)
  • 数据结构哈希表(散列) 之Hash

    声明: 此文章仅限于记录学习之用 , 受限于自身水平和理解能力 , 因此结论可能是不正确的. 如果您需要学习,建议参考其他文章 看了下网上一些大佬的教程, 写的云山雾绕的. 简单总结下吧. 以言简意赅为主. hash 就是把任意输入通过算法生成一个int值. 这个值就是放数据的地址

    2024年02月21日
    浏览(46)
  • 【C++入门到精通】 哈希结构 | 哈希冲突 | 哈希函数 | 闭散列 | 开散列 [ C++入门 ]

    在现代计算机科学和数据结构中,哈希(Hash)是一项重要而广泛应用的技术。通过将输入数据映射为固定长度的哈希值,哈希函数能够快速高效地进行数据存储、搜索和比较。然而,由于输入数据的多样性和哈希值的有限长度,哈希冲突成为了一个不可避免的问题。本文将介

    2024年02月08日
    浏览(44)
  • 查找算法【哈希表】 - 处理冲突的方法:开放地址法-二次探测法 & 随机探测法 & 再散列法

    查找算法【哈希表】 - 处理冲突的方法:开放地址法-二次探测法 随机探测法 再散列法 【二次探测法】 二次探测法指采用前后跳跃式探测的方法,发生冲突时,向后1位探测,向前1位探测,向后2^2 位探测,向前2^2 位探测……以跳跃式探测,避免堆积。 二次探测的增量序列为

    2024年02月10日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包