精华内容
下载资源
问答
  • 哈希表查找不成功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

    展开全文
  • –1)从根结点出发, 沿着左分支或右分支逐层向下直至关键字等于给定值的结点; ——查找成功 –2)从根结点出发, 沿着左分支或右分支逐层向下直至指针指向空树为止。... ——查找不成功 如图,为二叉排序...

    1)从根结点出发, 沿着左分支或右分支逐层向下直至关键字等于给定值的结点;
                                                     ——
    查找成功

    2)从根结点出发, 沿着左分支或右分支逐层向下直至指针指向空树为止
                                                    
    ——查找不成功

    如图,为二叉排序树:知道这个之后就很好理解了。比如线性探测再散列,因为一旦往右确定为空,即可确定不存在,即查找不成功。

    递归算法:

    若二叉排序树为空, 则查找不成功;

    否则,

    若给定值等于根结点的关键字, 查找成功

    若给定值小于根结点的关键字, 则继续在左子树上进行查找;

    若给定值大于根结点的关键字, 则继续在右子树上进行查找。

    总之:是在根指针T所指二叉排序树中递归地查找关键字等于key的记录

    展开全文
  • 哈希表查找不成功时的平均查找长度计算和查找成功时的ASL 例如: 关键字集合   { 19, 01, 23, 14, 55, 68, 11, 82, 36 } 设定哈希函数 H(key) = key MOD 11 ( 表长=11 ) 查找成功次数: 1 ...

    哈希表查找不成功时的平均查找长度计算和查找成功时的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

    查找不成功次数:10    9     8    7    6    5     4       3      2    1    1

    查找成功时的平均查找长度:ASL=(1+1+2+1+3+6+2+5+1)/9=22/9
    查找不成功时的平均查找长度:ASL=(10+9+8+7+6+5+4+3+2+1+1)/11=56/11
    说明:
    第n个位置不成功时的比较次数为,第n个位置到第1个没有数据位置的距离。
      如:第0个位置到第1个没有数据位置(9)的距离为10!





    展开全文
  • 数据结构 Hash表(哈希表

    万次阅读 多人点赞 2018-05-20 01:23:34
    要想知道什么是哈希表,那得先了解哈希函数 哈希函数 对比之前博客讨论的二叉排序树 二叉平衡树 红黑树 B B+树,它们的查找都是先从根节点进行查找,从节点取出数据或索引与查找值进行比较。那么,有没有一种...
  •  哈希表—线性探测法的ASL成功、不成功计算 将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组。散列函数为: H(key) = (keyx3) MOD 7,处理冲突采用线性...
  • 哈希表查找——成功和不成功时的平均查找长度

    万次阅读 多人点赞 2017-09-17 13:27:21
    哈希表查找——成功和不成功时的平均查找长度 以下求解过程是按照“计算机统考的计算方法”,不同的老师、教材在“处理冲突”上可能会有不同的方法,所以最主要的是掌握原理即可,对于考研的朋友最好掌握统考...
  • 你们有人知道把哈希表求出来之后,ASL不成功怎么求吗?[face]emoji:010.png[/face]明天考试,今天补救。
  • 接下来讨论不成功的情况, 看2,计算查找不成功的次数就直接找关键字到第一个地址上关键字为空的距离即可, 但根据哈希函数地址为MOD7,因此初始只可能在06的位置。等概率情况下,查找06位置查找失败的查找次数为:...
  • 哈希表查找不成功时的平均查找长度 哈希表查找不成功时的平均查找长度(zz)哈希表查找不成功怎么计算?解答:先建好表,然后可以算出每个位置不成功时的比较次数之和,再除以表空间个数! 例如:散列函数为hash(x)=...
  • 一、哈希表 1、概念  哈希表(Hash Table)也叫散列表,是根据关键码值(Key Value)而直接进行访问的数据结构。它通过把关键码值映射到哈希表中的一个位置来访问记录,以加快查找的速度。这个映射函数就做散列函数,...
  • 哈希表:线性探测法和链地址法求查找成功与不成功的平均查找
  • 继续小结,做到一道求 哈希表查找成功与查找不成功 情况下平均查找长度的计算问题,迷惑了好一会,在这里总结下来: 首先,你要明白的是平均查找长度求的是期望,那么你就按照求期望的方法来求平均查找长
  • 哈希表

    2019-05-04 15:44:34
    给定一组元素的关键字hash[] = {78,90,66,70,155,82,123,231},利用除留余数法和线性再探测散列法将元素存储再哈希表中,并查找给定的关键字,求平均查找长度。 分析:主要考察哈希表的构造和冲突解决办法 代码: #...
  • 姓名哈希表

    千次阅读 多人点赞 2020-06-13 14:53:55
    /为班级30个人的姓名设计一个哈希表,假设姓名用汉语拼音表示。要求用除留余数法 构造哈希函数,用线性探测再散列法处理冲突,平均查找长度的上限为2。 编写数据结构和算法来实现。要求:将哈希函数和处理冲突方法...
  • 编程实现:构造哈希表:在地址空间为0~12,对以下关键字序列:(Jan,Feb,Apr,May,Jun,Jul,Aug,Sep,Oct)建哈希表,并且求出等概率情况下查找成功与不成功的平均查找长度。 实现代码: typedef struct HashTable{ ...
  • 哈希表设计

    2021-01-03 20:06:32
    实验 哈希表设计 数据结构课设 发出来分享 水平有限 希望各位网友多多交流和指正 一、实验目的 熟练掌握哈希表的构造方法,深刻理解哈希表与其他结构表的实质性差别。 二、实验原理 程序的功能是对一批关键字集合...
  • 构建出来的哈希表有八个元素,针对这八个元素的比较次数,得出ASLsuccess=(1+1+1+2+1+2+1+2)/8=11/8. 而查找失败时的平均查找长度,却是针对位置的查找。 为什么呢,因为如果我们要查找表中的元素,那么一定可以找到...
  • 哈希表问题

    2013-06-01 19:32:25
    设定哈希函数 H(key) = key MOD 11 ( 表长=11 ),输入一组关键字序列,根据线性探测再散列解决冲突的方法建立哈希表的存储结构,显示哈希表,任意输入关键字,判断是否在哈希表中。
  • 哈希表习题

    千次阅读 2019-12-05 19:44:15
    选取哈希函数H(k)=(3k)%11,用线性探测散列法和二次探测再散列法分别处理...试在0~10的散列地址空间中,对关键字序列(22,41,53,46,30,13,01,67)构建哈希表,并求等概率情况下查找成功的平均查找长度。 线性探测...
  • 一、哈希表 1、概念 哈希表(Hash Table)也叫散列表,是根据关键码值(Key Value)而直接进行访问的数据结构。它通过把关键码值映射到哈希表中的一个位置来访问记录,以加快查找的速度。这个映射函数就做散列函数,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,708
精华内容 1,083
关键字:

哈希表不成功的asl