数据结构—散列表的查找

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

7.4散列表的查找

7.4.1散列表的基本概念

基本思想:记录的存储位置域关键字之间存在对应关系

​ 对应关系——hash函数

​ Loc(i)= H(keyi)

如何查找

数据结构—散列表的查找,数据结构考研,数据结构,散列表

根据散列函数 H(key) = k

查找key=9,则访问H(4)= 18号地址,若内容为18则成功;

若查不到,则返回一个特殊值,如空指针或空记录。

优点:查找效率高

缺点:空间效率低

7.4.2散列表的若干术语

散列方法(杂凑法)

​ 选取某个函数,依该函数按关键字计算元素的存储位置,并按此存放;

​ 查找时,由同一个函数对给定值K计算地址,将k与地址单元中元素关键码进行比,确定查找是否成功。

散列函数(杂凑函数):散列方法中使用的转换函数

散列表(杂凑表):按上述思想构造的表 散列函数:H(key)=k

数据结构—散列表的查找,数据结构考研,数据结构,散列表

冲突:不同的关键码映射到同一个散列地址 key1≠key2,但是H(key1)=H(key2)

例如:有6个元素的关键码分别为:(25,21,39,9,23,11)。

  • 选取关键码与元素位置间的函数为H(k)=k mod 7,
  • 地址编号从0-6
7.4.3散列函数的构造方法

散列存储:选取某个函数,依该函数按关键字计算元素的存储位置

Loc(i)=H(keyi)

在散列查找方法中,冲突是不可能避免的,只能尽可能减少。

使用散列表要解决好两个问题

  1. 构造好的散列函数

    a)所选函数尽可能简单,以便提高转换速度;

    b)所选函数对关键码计算出的地址,应在散列地址集中致均匀分布,以减少空间浪费。

  2. 制定一个好的解决冲突的方案

    查找时,如果从散列函数计算出的地址中查不到关键码,则应当依据解决冲突的规则,有规律地查询其他相关单元。

构造散列函数考虑的因素

  1. 执行速度(即计算散列函数所需要的时间);
  2. 关键字的长度;
  3. 散列表的长度;
  4. 关键字的分布情况;
  5. 查找频率。

根据元素集合的特性构造

  • 要求一:n 个数据源仅占用 n 个地址,虽然散列查找是以空间换时间,但仍希望散列的地址空间尽量小
  • 要求二:无论用什么方法存储,目的都是尽量均匀地存放元素,以避免冲突。
1、直接定址法

Hash(key)= a·key + b (a、b为常数)

优点:以关键码key的某个线性函数值为散列地址,不会产生冲突。

缺点:要占用连续地址空间,空间效率低。

数据结构—散列表的查找,数据结构考研,数据结构,散列表

2、除留余数法

Hash(key)= key mod p(p是一个整数)

关键:如何选取合适的p?

技巧:设表长为m,取p≤m且为质数

数据结构—散列表的查找,数据结构考研,数据结构,散列表

7.4.4处理冲突的方法
1、开放地址法(开地址法)

基本思想:有冲突时就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到,并将数据元素存入。

例如:除留余数法 Hi=(Hash(key)+di) mod m di为增量序列

常用方法:

​ 线性探测法 di为1,2,…m-1线性序列 一旦冲突,就找下一个地址,直到找到空地址存入

数据结构—散列表的查找,数据结构考研,数据结构,散列表

​ 二次探测法 di为12,-12,22,-22,…,q2二次序列

数据结构—散列表的查找,数据结构考研,数据结构,散列表

​ 伪随机探测法 di为伪随机数序列

2、链地址法(拉链法)

基本思想:相同散列地址的记录链成一单链表

m个散列地址就设m个单链表,然后用一个数组将m个单链表的表头指针存储起来,形成一个动态的结构。

数据结构—散列表的查找,数据结构考研,数据结构,散列表

链地址法建立散列表步骤

  • Step1:取数据元素的关键字key,计算其散列函数值(地址)。若该地址对应的链表为空,则将该元素插入此链表;否则执行Step2解决冲突。
  • Step2:根据选择的冲突处理方法,计算关键字key的下一个存储地址。若该地址对应的链表不为空,则利用链表的前插法或后插法将该元素插入此链表。

链地址法的优点

  • 非同义词不会冲突,无聚集现象
  • 链表上结点空间动态申请,更适合于表长不确定的情况
7.4.5散列表的查找

给定值查找值k,查找过程:

数据结构—散列表的查找,数据结构考研,数据结构,散列表

数据结构—散列表的查找,数据结构考研,数据结构,散列表文章来源地址https://www.toymoban.com/news/detail-654753.html

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

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

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

相关文章

  • 数据结构【考研笔记】

    1、基本概念 1)数据 数据是 信息的载体 ,是描述客观事物属性的数、字符及所有 能输入到计算机中并被计算机程序识别和处理的符号 的集合。数据是计算机程序加工的原料。 2)数据元素、数据项 数据元素是数据的基本单位,通常作为一个整体进行考虑和处理。一个数据

    2024年02月12日
    浏览(49)
  • 24考研数据结构-——绪论2

    1.4.1 渐近时间复杂度 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作T(n)=O(n),它表示随问题规模n的增大而增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的 渐近时间复杂度 ,简称时间复杂度。 大O表示“同阶”,

    2024年02月16日
    浏览(42)
  • 考研数据结构--栈和队列

    内容 栈 :栈的抽象数据类型定义、栈的存储表示及基本操作实现、栈的应用 栈的定义(特点) 栈是一种后进先出(LIFO)的线性表,只能在一端进行插入和删除操作,这一端称为栈顶,另一端称为栈底。 打个比方: 有一个胡同很窄只能通过一辆车,而且是死胡同,只能从胡

    2023年04月19日
    浏览(45)
  • 考研数据结构:第八章 排序

    2.1.1算法思想 插入排序的思想很简单,就是不断的把一个个带排序的记录,按的大小插入到前面已经排好序的子序列中。直到全部序列插入完成。 比如我们现在要对下面的序列进行排序, 刚开始我们从1号位开始 我们会认为当前处理的这个元素之前都是有序的 现在把

    2024年02月11日
    浏览(38)
  • 24考研数据结构-图的存储结构邻接矩阵

    【1】顶点的结点结构 ——————— | data | firstarc | ——————— data数据域:储存顶点vi firstarc链域:指向链表中第一个结点 【2】弧的结点结构 —————————— | adjvex | info | nextarc | —————————— adjvex邻接点域:与顶点vi邻接的点在图中的位置 info数据域

    2024年02月14日
    浏览(57)
  • 王道考研数据结构--2.单链表

    1.前言 2.难点 2.1c和c++的引用转换 2.2引入头结点的好处 2.3头插法和尾插法 3.代码段 3.1C语言自定义bool操作 3.2单链表结构体定义 3.3创建新节点 3.4头插法和尾插法 3.5查找 3.6按位序插入 3.7后插和前插 3.8删除 3.9求表长 3.10遍历输出单链表 4.完整代码 日期:2023.6.21 书籍:2024年数据

    2024年02月09日
    浏览(116)
  • 24考研数据结构-线性表4

    2.4.4单链表的查找操作(默认带头节点,不带头节点后续更新) 2.4.4.1 按位查找操作 GetElem(L, i): 按位查找操作,获取表L中第i个位置的元素的值; 注意: 1.边界情况 i=0,返回头节点;iL.length,返回null; 2.ji即查找到j = i 的节点,就是第i个节点。 3.平均复杂度O(n) 2.4.4.2 按值

    2024年02月16日
    浏览(40)
  • 【数据结构】24王道考研笔记——图

    图的定义 有向图以及无向图 简单图以及多重图 度 顶点-顶点间关系 连通图、强连通图 子图 (有向图也一样) 连通分量 强连通分量 生成树 生成森林 边的权、带权网/图 特殊形态的图 总结: 邻接矩阵 存储带权图(网): 对角线处可以填0或∞ 空间复杂度为O(|V| 2 )只和顶

    2024年02月17日
    浏览(50)
  • 【数据结构】| 王道考研——树的前世今生

    根据王道考研数据结构总结出的知识点,以下是文章整体大纲: 1.1 概念 树是n个结点的有限集合,n = 0时称为空树,这是一种特殊情况。任意一棵非空树中应满足: 有且仅有一个特定的称为根的节点 当n1时,其余结点可分为m个互不相交的有限集合T1、T2、T3……Tm;每个集合又

    2024年02月15日
    浏览(50)
  • 王道考研数据结构--4.2循环队列

    目录 前言  1.循环队列的定义 2.循环队列的结构 3.循环队列的操作 3.1定义循环队列 3.2初始化 3.3入队 3.4出队 3.5遍历,求表长 3.6清空销毁 4.完整代码 日期:2023.7.25 书籍:2024年数据结构考研复习指导(王道考研系列) 内容:实现顺序队列的基本实现,主要功能如下: 1.循环队

    2024年02月15日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包