精华内容
下载资源
问答
  • 哈希表查找不成功的ASL问题

    千次阅读 多人点赞 2017-10-24 23:07:31
    哈希表(等概率情况下)查找成功与查找不成功的平均查找长度计算问题,迷惑了好一会,在这里总结下来:  首先,你要明白的是平均查找长度求的是期望,那么你就按照求期望的方法来求平均查找长度吧,千万记着...

    哈希表(等概率情况下)查找成功与查找不成功的平均查找长度计算问题,迷惑了好一会,在这里总结下来:

      首先,你要明白的是平均查找长度求的是期望,那么你就按照求期望的方法来求平均查找长度吧,千万记着期望怎么求平均查找长度就怎么求啊。

      题目:

    在地址空间为0~16的散列区中,对以下关键字序列构造两个哈希表:
    {Jan, Feb, Mar, Apr, May,  June, July, Aug, Sep, Oct, Nov, Dec}
    (1) 用线性探测开放地址法处理冲突;
    (2) 用链地址法(开散列存储)处理冲突 
    并分别求这两个哈希表在等概率情况下查找成功和查找不成功时的平均查找长度。设哈希函数为 
    H(key) = i/2,其中i为关键字中第一个字母在字母表中的序号,如下:
    A B C D E F G H I  J    K   L  M  N  O   P   Q   R  S  T   U   V   W  X  Y   Z
    1 2 3 4  5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

      解决如下:

    (1) 线性探测进入散列区的次序如下,X 代表冲突,要找下一个空格
    Jan -> 5
    Feb -> 3
    Mar -> 6
    Apr -> 0
    May -> 6X -> 7
    June -> 5X -> 6X -> 7X -> 8
    July -> 5X -> 6X -> 7X -> 8X -> 9
    Aug -> 0X -> 1
    Sep -> 9X -> 10
    Oct -> 7X -> 8X -> 9X -> 10X -> 11
    Nov -> 7X -> 8X -> 9X -> 10X -> 11X -> 12
    Dec -> 2

    0

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    Apr

    Aug

    Dec

    Feb

     

    Jan

    Mar

    May

    Jun

    July

    Sep

    OCt

    Nov

     

     

     



      很明显,查找成功时,查找Jan、Feb、Mar等仅需要一次,其余的也可以由上面看出来
      所以查找成功时平均查找长度 (ASL) = (1 + 1 + 1 + 1 + 2 + 4 + 5 + 2 + 2 + 5 + 6 + 1) / 12 = 31/12 = 2.58 为什么是除以12呢?因为查找成功的情况总共有12种啊

      查找不成功时呢?什么是查找不成功呢?查找不成功就是从查找位置开始直到一个位置为空需要比较的次数。

      首先,26/2=13,也就是说查找不成功的情况也只能出现在0~13之间,只有这14种情况。

      举个例子来说,查找Aay吧,根据hash表,与Apr比较不匹配,接着与Aug比较又是不匹配,接着与Dec比较又是不匹配,又与Feb比较又是不匹配,到了4位置的时候为空了,即4上内容与nullkey比较,结果为空,所以查找Aay失败,查找长度为5。同理也能计算其他的。

      最终平均查找失败时平均查找长度为(5+4+3+2+1+9+8+7+6+5+4+3+2+1)/14=60/14。注意啊,这里是除以14啊。(这是求期望的方法啊)

    (2) 链地址法
    0 之下有 Apr, Aug
    2 之下有 Dec
    3 之下有 Feb
    5 之下有 Jan, June, July
    6 之下有 Mar, May
    7 之下有 Oct, Nov
    9 之下有 Sep
    查找成功时候,查 Apr, Dec, Feb, Jan, Mar, Oct, Sep 各需 1 次,查 Aug, June, May, Nov 各需 2 次,查 July 需 3 次。

    所以查找成功时平均查找长度 (ASL) = (1 * 7 + 2 * 4 + 3 * 1) / 12 = 18/12 = 1.5

    查找失败时平均查找长度:举个例子吧,查找Boy,2/2=1,而1的地方的指针为空,就不用比较就可以知道不存在,查找产度为0。查找Aay,与Apr比较不匹配,与Aug比较不匹配,同时,Aug指向下一个节点的指针为空,就可以知道查找失败,查找长度为2。

     所以查找失败的平均查找长度:(2+1+1+3+2+2+1)/14=12/14。






       
    展开全文
  • α = 表中填入的记录数/哈希表长度 ==> 哈希表长度 = 7/0.7 = 10 H(7) = (7x3) MOD 7 = 0 H(8) = (8x3) MOD 7 = 3 H(30) = (30x3) MOD 7 = 6 H(11) = (11x3) MOD 7 = 5 H(18) = (18x3) MOD 7 = 5 H(9) = (9x3) MOD...

    以下求解过程是按照“计算机统考的计算方法”,不同的老师、教材在“处理冲突”上可能会有不同的方法,所以最主要的是掌握原理即可,对于考研的朋友最好掌握统考真题的解题方法。
    题目
    例子:(2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题第一题)

    将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组。散列函数为: H(key) = (keyx3) MOD 7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。
    (1) 请画出所构造的散列表;
    (2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。
    1.散列表:
    α = 表中填入的记录数/哈希表长度 ==> 哈希表长度 = 7/0.7 = 10
    H(7) = (7x3) MOD 7 = 0 H(8) = (8x3) MOD 7 = 3 H(30) = (30x3) MOD 7 = 6
    H(11) = (11x3) MOD 7 = 5 H(18) = (18x3) MOD 7 = 5 H(9) = (9x3) MOD 7 = 6
    H(14) = (14x3) MOD 7 = 0
    按关键字序列顺序依次向哈希表中填入,发生冲突后按照“线性探测”探测到第一个空位置填入。
    0 1 2 3 4 5 6 7 8 9
    7 14 8 11 30 18 9
    2.查找长度:
    2.1 查找成功的平均查找长度
    (待查找的数字肯定在散列表中才会查找成功)
    查找数字A的长度 = 需要和散列表中的数比较的次数;
    步骤:
    比如 查找数字:8
    则 H(8) = (8x3) MOD 7 = 3
    哈希表中地址3处的数字为8,进行了第一次比较:8 = 8,则查找成功,查找长度为1;
    比如查找数字:14
    则 H(14) = (14x3) MOD 7 = 0
    哈希表中地址0处的数字为7,进行第一次比较:7≠14
    哈希表中地址1处的数字为14,进行第二次比较:14=14 ,则查找成功,查找长度为2。
    由此可得到如下数据:【2016年12月26日修改,多谢@一楼的朋友指正】
    0 1 2 3 4 5 6 7 8 9
    7 14 8 11 30 18 9
    1 2 1 1 1 3 3
    所以总的查找成功的平均查找长度= (1+1+1+1+3+3+2)/7 = 12/7
    2.2查找不成功的平均查找长度
    (待查找的数字肯定不在散列表中)
    【解题的关键之处】根据哈希函数地址为MOD7,因此任何一个数经散列函数计算以后的初始地址只可能在0~6的位置
    查找0~6位置查找失败的查找次数为:
    地址0,到第一个关键字为空的地址2需要比较3次,因此查找不成功的次数为3.
    地址1,到第一个关键字为空的地址2需要比较2次,因此查找不成功的次数为2.
    地址2,到第一个关键字为空的地址2需要比较1次,因此查找不成功的次数为1.
    地址3,到第一个关键字为空的地址4需要比较2次,因此查找不成功的次数为2.
    地址4,到第一个关键字为空的地址4需要比较1次,因此查找不成功的次数为1.
    地址5,到第一个关键字为空的地址2(比较到地址6,再循环回去)需要比较5次,因此查找不成功的次数为5.
    地址6,到第一个关键字为空的地址2(比较到地址6,再循环回去)需要比较4次,因此查找不成功的次数为4.
    于是得到如下数据:
    0 1 2 3 4 5 6 7 8 9
    7 14 8 11 30 18 9
    3 2 1 2 1 5 4
    则查找不成功的平均查找长度 = (3+2+1+2+1+5+4)/7 = 18/7

    展开全文
  • 哈希表

    2017-01-07 21:03:33
    概述 哈希函数的基本构造方法 处理冲突的常用方法 哈希表的建立、查找及其ASL分析
    • 概述
    • 哈希函数的基本构造方法
    • 处理冲突的常用方法
    • 哈希表的建立、查找及其ASL分析

    概念

    哈希表的基本思想

    在记录的存储地址与它的关键词之间建立一个确定的对应关系,这样理想状态下不经过比较,一次存储就能得到所查元素。

    哈希表

    一个有限的连续的地址空间,用以容纳用哈希地址存储的记录。

    哈希函数

    记录的存储位置与它的关键词之间存在的一种对应关系

    冲突

    对不同的关键字可能得到同一哈希地址,即key1key2,而H(key1)=H(key2)

    同义词

    具有相同函数值的关键字对该哈希函数来说称做同义词。

    哈希散列地址

    根据设定的哈希函数H(key)和处理冲突的方法确定的记录的存储位置。

    装填因子

    表中填入的记录数n和哈希表表长m之比。
    α=n/m


    哈希函数的基本构造方法

    若是非数字关键字,则需先对其进行数字化处理。

    直接定址法
    H(key)=akey+b,a,b
    此法仅适合于:地址集合的大小 = 关键字集合的大小
    例:
    有一个1岁到100岁的人口数字统计表,其中,年龄作为关键字,哈希函数取关键字自身。(即H(key)=key)

    地址 01 02 03 100
    年龄 1 2 3 100
    人数 3000 2000 2500

    若有一个解放后出生的人口调查表,关键字是年份,哈希函数取关键字加一常数:H(key)=+(1948) 表格略

    数字分析法
    取关键字的若干数位作为哈希地址。

    假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, …, us),分析关键字集中的全体,并从中提取分布均匀的若干位或它们的组合作为地址。
    此方法仅适合于:能预先估计出全体关键字的每一位上各种数字出现的频度。

    平方取中法
    取关键字平方后的中间几位作为哈希地址。

    求“关键字的平方值” 的目的是“扩大差别” ,同时平方值的中间各位又能受到整个关键字中各位的影响。
    此方法适合于: 关键字中的每一位都有某些数字重复出现频度很高的现象。

    折叠法
    将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几个部分的叠加和(舍去进位)作为哈希地址。

    此方法适合于: 关键字的数字位数特别多。
    两种叠加方法

    除留余数法
    H(key)=key MOD p (p<=m)
    m:哈希表的表长
    p:最好为素数,有助于哈希表的散列

    为什么要对 p 加限制?

    给定一组关键字为: 12, 39, 18, 24, 33, 21, 若取 p=9, 则对应的哈希函数值将为: 3, 3, 0, 6, 6, 3
    可见,若 p 中含质因子 3, 则所有含质因子 3 的关键字均映射到“3 的倍数”的地址上,从而增加了“冲突”的可能。

    随机数法
    H(key)=random(key)
    此方法适合于:关键字长度不等时的情况。


    处理冲突的常用方法

    开放定址法 (空缺编址法)
    (为产生冲突的地址寻找下一个哈希地址)
    Hi = ( H(key)+di ) MOD m
    i=1,2, …, k (k<=m-1)
    m:哈希表的表长; di:增量序列

    1)线性探测再散列 di= 1,2, …, m-1
    缺陷:有聚集(堆积)现象—非同义词地址冲突。

    若冲突,则依次位置+1,直到找到空闲位置,插入

    2)二次探测再散列 di= 12, -12, 22, -22, 32,…,+-k2
    k <=m/2

    若冲突,则以冲突位置为基准,依次看+12,12,+22,22,+32,32,...的位置上是否空闲,若空闲则插入,以此类推。

    3)伪随机探测再散列 di = 伪随机数序列

    4) 双重散列函数探查法 di= i*h1(key)
    0< i <=m- 1
    要求:h1(key)的值与m互素。
    m为素数时, h1(key)可取1到m-1之间的任何数,建议h1(key)=key mod (m-2) +1
    m为2的方幂时, h1(key)可取1到m-1之间的任何奇数

    再哈希法
    Hi = RHi(key) i=1,2, … , k RHi为不同的散列函数

    链地址法
    为每个哈希地址建立一个单链表,存储所有具有同义词的记录。

    建立一个公共溢出区


    哈希表的建立、查找及其ASL分析

    展开全文
  • 哈希表查找不成功时的平均查找长度计算和查找成功时的ASL 例如: 关键字集合 { 19, 01, 23, 14, 55, 68, 11, 82, 36 } 设定哈希函数 H(key) = key MOD 11 ( 表长=11 ) 查找成功次数: 1 1 2 1 3 6 2 5 1 ...
  • –1)从根结点出发, 沿着左分支或右分支逐层向下直至关键字等于给定值的结点; ——查找成功 –2)从根结点出发, 沿着左分支或右分支逐层向下直至指针指向空树为止。 ——查找不成功 如图,为二叉排序...
  •  哈希表—线性探测法的ASL成功、不成功计算 将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组。散列函数为: H(key) = (keyx3) MOD 7,处理冲突采用线性...
  • 线性表和树表的查找算法都是基于查找值与查找表中记录的关键字值的比较,也就是说这些方法都是建立在“比较”基础上的,算法的查找效率取决于查找过程中所进行的“比较”次数。...哈希表的基本概念(1)哈希...
  • 线性探测哈希表

    2020-06-22 23:02:07
    5.给定一个关键字序列(13,4,18,20,32,15,9,24),哈希表长度为 11,哈希函数为 H(Key)=Key%11,采用线性探测法解决冲突,画出构造的哈希表(8 分),并求出等概率查找时查找成功 的 ASL(成功) (1 分),...
  • 哈希表平均查找长度

    万次阅读 多人点赞 2017-08-13 10:53:31
    题目:关键字序列为:{38,25,74,63,52,48},哈希函数为H(k)=k%7,哈希表的长度为7,用线性探测和链地址法处理冲突,分别计算等概率情况下查找成功的平均查找长度。注:没给哈希表长度,给出装填因子时,可求哈希...
  • 在压缩包下附带了利用 C 语言开发的哈希表的运算方法(包括增、删、改、查)以及计算并显示哈希表的平均查找长度 ASL,同时还附代了对应的课程设计报告。压缩包下的源代码导入Vc++6.0编译器后便可调试运行。非常适合...
  • 哈希表的构造方法: ...平均查找长度ASL哈希表构造方法和处理冲突的方法都有关。一般情况下,处理冲突方法相同的哈希表,其平均查找长度依赖于哈希表的装填因子: α=表中填入的记录数哈希表的长度...
  • 哈希表 - 开散列

    2018-09-05 22:48:26
    开散列很简单。ASL的计算忘了,找了两道题都没算对,这才是我不写的真正原因…代码里是... 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关 键码值映...
  • 哈希表 - 闭散列

    2018-09-05 21:57:25
    闭散列主要就是需要注意一下“墓碑”的操作,其他的其实都简单。ASL的计算忘了,找了两道题都没算对,这才是我不写的... 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也...
  • Java之哈希表

    千次阅读 2016-01-28 11:57:34
    一、 Hash概念 ...使ASL趋近与0. 1) 哈希(Hash)函数是一个映象,即:将关键字的集合映射到某个地址集合上,它的设置很灵活,只要这个地址集合的大小不超出允许范围即可; 2) 由于哈希函数是一个压缩
  • 字典和哈希表

    千次阅读 2018-07-26 11:06:53
    字典是支持基于关键码的数据存储与检索的数据结构,也被成为查找、映射或关联。 有关检索效率的评价标准,通常考虑的是在一次完整检索过程中比较关键码的平均次数,通常称为平均检索长度(Average Search ...
  • 2.哈希表 2.1 哈希集 哈希集是集合的实现之一,它是一种存储不重复值的数据结构。头文件为<unordered_set>,基本用法如下: unordered_set<int> hashset; // 2. insert a new key...
  • ASL指标分析了哈希表的性能。
  • 1、哈希函数的定义 对于一些查找表来说,它的查找过程是:为给定值按某种顺序和记录集合中各个关键字进行比较的一个过程。这类查找表的平均查找长度都是不为0的。 所以,对于查找表,希望ASL...哈希表定义:根据设定
  • 实现哈希表创建及查找算法,哈希函数使用除余法,用拉链法处理冲突。 函数接口定义: void CreateHash(HashTable HT[],int n); //输入不大于m的n个不为0(0表示空值)的数,用拉链法解决冲突构造散列表 float ASL...
  • 6-4 创建哈希表及查找(拉链法) (10分) 实现哈希表创建及查找算法,哈希函数使用除余法,用拉链法处理冲突。 函数接口定义: void CreateHash(HashTable HT[],int n); //输入不大于m的n个不为0(0表示空值)的数,用...
  • 哈希表 这些查找方法的特点:记录在表中的位置和其关键字间不存在确定关系,查找的过程为给定值依次和各个关键字进行比较,查找的效率取决进行比较的关键字个数。它们的平均查找长度(ASL)都不为0. 若希望ASL=0 ...
  • 返回目录:Chilan Yu:《数据结构》目录链接​zhuanlan.zhihu.com哈希法又称散列...创建哈希表时,把关键字为k的元素直接存入地址为f(k)的单元;以后当查找关键字为k的元素时,再利用哈希函数计算出该元素的存储位置...
  • 一、查找 给定一个值K,在...二,静态查找 静态查找的查找算法主要有: 1.顺序查找(线性查找) 2.折半查找(二分或对分查找) 3.分块查找(索引顺序查找) 1.顺序查找 用逐一比较的办法顺序查找关键字。...
  • 六、对静态查找表,有时也可能找到不发生冲突的哈希函数,即此时的哈希表ASL=0,称此类哈希函数为理想(perfect)的哈希函数。   1.  顺序表和有序表的查找方法及其平均查找长度的计算方法。 2.  静态查找树...
  • 就除留取余发来复习一下哈希查找 除留取余发的表达式f(k)=k%p, 其中f(k)为关键字K的地址 P为小于等于哈希表空间长度的...解:1 构造哈希表 2 求成功与不成功的平均查找次数ASL 第一步 : 确定哈希函数中的P,因为哈希表
  • 建立一个公共溢出区衡量哈希表查找效率的量度——平均查找长度(ASL) 哈希函数的构造方法有哪些? 直接定址法(适用于均匀哈希函数) 数字分析法(适用于关键字位数比哈希地址位数大,且关键字已知) 平方取...
  • ASL 平均查找长度

    千次阅读 2018-09-04 08:40:12
    哈希表查找 接下来整理一下上面每个方式的平均查找长度 顺序表查找ASL 如果每个关键字查找概率相同,则ASL = (n+1)/2。  一般都是概率相同。 二分查找ASL 举例说明: 这是一个有序序列(下标和关键字相同): ...

空空如也

空空如也

1 2 3 4 5
收藏数 89
精华内容 35
关键字:

哈希表asl