精华内容
下载资源
问答
  • 数据结构 哈希表 ASL 失败查找

    千次阅读 2019-07-17 11:12:07
  • α = 表中填入的记录数/哈希表长度 ==> 哈希表长度 = 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

    展开全文
  • Hash的平均查找长度ASL计算方法

    千次阅读 2019-07-11 10:13:24
    Hash的“查找成功的ASL”和“查找不成功的ASLASL指的是 平均查找时间 关键字序列:(7、8、30、11、18、9、14) 散列函数: H(Key) = (key x 3) MOD 7 装载因子(用来计算长的): 0.7 处理冲突: 线性探测再...

    Hash表的“查找成功的ASL”和“查找不成功的ASL”
    ASL指的是 平均查找时间

    关键字序列:(7、8、30、11、18、9、14)

    散列函数:
    H(Key) = (key x 3) MOD 7

    装载因子(用来计算表长的):
    0.7

    处理冲突:
    线性探测再散列法

    查找成功的ASL计算方法:

    因为现在的数据是7个,填充因子是0.7。所以数组大小=7/0.7=10,即写出来的散列表大小为10,下标从0~9。
    第一个元素7,带入散列函数,计算得0。
    第二个元素8,带入散列函数,计算得3。
    第三个元素30,带入散列函数,计算得6。
    第四个元素11,带入散列函数,计算得5。
    第五个元素18,带入散列函数,计算得5;此时和11冲突,使用线性探测法,得7。
    第六个元素9,带入散列函数,计算得6;此时和30冲突,使用线性探测法,得8。
    第七个元素14,带入散列函数,计算得0;此时和7冲突,使用线性探测法,得1。
    所以散列表:

    地址0
    key7

    所以查找成功的计算:
    如果查找7,则需要查找1次。
    如果查找8,则需要查找1次。
    如果查找30,则需要查找1次。
    如果查找11,则需要查找1次。
    如果查找18,则需要查找3次:第一次查找地址5,第二次查找地址6,第三次查找地址7,查找成功。
    如果查找9,则需要查找3次:第一次查找地址6,第二次查找地址7,第三次查找地址8,查找成功。
    如果查找地址14,则需要查找2次:第一次查找地址0,第二次查找地址1,查找成功。
    所以,ASL=(1+2+1+1+1+3+3)/ 7=12/ 7

    查找不成功的ASL计算方法:

    鉴于网络上有各种版本,本人认为此种计算方法比较合理。验证实例可以参考2010年的计算机408考研真题的第一道计算大题和答案。

    1. 定义什么叫查找不成功
    举个例子来说吧。在已知上面散列表的基础上,如果要查找key为4的关键字。根据散列函数可以计算Hash(key)=Hash(4)=5。此时在地址为5的地方取出那个数字,发现key=11,不等于4。这就说明在装填的时候会发生冲突。根据冲突处理方法,会继续检测地址为6的值,发现key=30,依然不等。这个时候到了地址为6,但是依然没有找到。那么就说明根本就没有key=4这个关键字,说明本次查找不成功。注意:为什么到地址6?因为散列函数中有 mod7 ,对应的地址为06,即06查找失败的查找次数。
    再举一个例子。查找key为0的关键字,根据散列函数可以计算Hash(key)=Hash(0)=0。此时在地址为0的地方取出那个数字,发现key=7,不等于0。这就说明在装填的时候会发生冲突。根据冲突处理方法,会继续检测地址为1的值,发现key=14,依然不等。这个时候到了地址为3,发现为空,依然没有找到。所以停止查找,本次查找不成功。因为如果key=0这个关键字存在的话,依照冲突处理函数,就一定能找到它。总不能丢了吧。

    2. 根据第一点定义的不成功,依次推下去:
    查找地址为0的值所需要的次数为3,
    查找地址为1的值所需要的次数为2,
    查找地址为2的值所需要的次数为1,
    查找地址为3的值所需要的次数为2,
    查找地址为4的值所需要的次数为1,
    查找地址为5的值所需要的次数为5,
    查找地址为6的值所需要的次数为4。
    3.计算
    查找不成功ASL=(3+2+1+2+1+5+4)/ 7=18/ 7

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

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

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

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

    递归算法:

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

    否则,

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

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

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

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

    展开全文
  • 哈希表查找不成功的ASL问题

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

    千次阅读 2019-04-09 21:06:30
    开放地址查找成功的ASL和不成功的ASL 问题描述 ASL 指的是平均查找时间 关键字序列:(7、8、30、11、18、9、14) 散列函数: H(Key) = (key x 3) MOD 7 装载因子: 0.7 处理冲突: 线性探测再散列法 查找成功的 ...
  • 二叉树(binary tree)和哈希表(hash table)都是很基本的数据结构,但是我们要怎么从两者之间进行选择呢?他们的不同是什么?优缺点分别是什么? 回答这个问题不是一两句话可以说清楚的,原因是在不同的情况下,选择的...
  • 【hash】hash平均查找长度(ASL

    千次阅读 2019-08-28 14:00:41
      hash 在处理 collision 的时候有...  本文记录使用开链法的情况下,Hash 查找成功和查找不成功的平均查找长度(ASL - ),其他方法同理。   首先开链法是指,每一个表格元素维护一个list,hash function...
  • 哈希表及处理冲突的方法

    千次阅读 2018-11-20 13:08:14
    哈希法又称***散列法、杂凑法以及关键字地址计算法***等,相应的表称为哈希表。 这种方法的基本思想是:首先在元素的关键字k和元素的存储位置p之间建立一个对应关系f,使得p=f(k),f称为哈希函数。 创建哈希表...
  • 二叉排序树 ...哈希表及其实现 最常见的代码需求: 再论数组 一个常见的情形 解决方案   代码   小结     整个数据结构总结 扩展学习  更多品种的树 ...
  • 哈希表习题

    千次阅读 2019-12-05 19:44:15
    选取哈希函数H(k)=(3k)%11,用线性探测散列法和二次探测再散列法分别处理...试在0~10的散列地址空间中,对关键字序列(22,41,53,46,30,13,01,67)构建哈希表,并求等概率情况下查找成功的平均查找长度。 线性探测...
  • 关于ASL(平均查找长度)的简单总结

    千次阅读 2021-05-23 09:12:15
    ASL(Average Search Length),即平均查找长度,在查找运算中,由于所费时间在关键字的比较上,所以把平均需要和待查找值比较的关键字次数成为平均查找长度。它的定义是这样的:其中n为查找中元素个数,Pi为查找第i...
  • hash函数查找和ASL计算

    千次阅读 2018-06-05 23:20:00
    Hash的“查找成功的ASL”和“查找不成功的ASLASL指的是 平均查找时间 关键字序列:(7、8、30、11、18、9、14) 散列函数: H(Key) = (key x 3) MOD 7 装载因子: 0.7 处理冲突:线性探测再散列法 查找成功...
  • 哈希表与二叉排序树的比较

    千次阅读 2018-12-07 14:20:58
    第三,笼统地来说,尽管散列表的查找等操作的时间复杂度是常量级的,但因为哈希冲突的存在,这个常量不一定比 logn 小,所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时,也不一定就比平衡二叉...
  • 你们有人知道把哈希表求出来之后,ASL不成功怎么求吗?[face]emoji:010.png[/face]明天考试,今天补救。
  • Hash的“查找成功的ASL”和“查找不成功的ASLASL指的是 平均查找时间 关键字序列:(7、8、30、11、18、9、14) 散列函数:  H(Key) = (key x 3) MOD 7 装载因子:  0.7 处理冲突:线性探测再散列法 ...
  • hash 中成功ASL 和不成功ASL的计算

    千次阅读 2017-12-29 18:20:25
    α = 表中填入的记录数/哈希表长度 ==> 哈希表长度 = 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) = (9...
  • 散列表的ASL计算

    2019-09-29 07:46:37
    处理冲突的方法为二次探测法Hi= ( H(key) + di )mod 15 ( di=12,-12,22,-22,… ),请写出构造散列表的详细计算过程,填写散列表,并计算在等概率的情况下查找成功和失败时的平均查找长度ASL。 地址 0 .....
  • 哈希表与哈希查找

    2021-08-28 14:07:36
    哈希表(哈希查找) ​ 前面对于顺序表进行查找时,在判断当前数据是否是要查找的数据时,需要去通过“=”来进行判断,直到有了相等的关键字才返回地址。在这种查找方式中,“比较”是必不可免的,那么是否有一种...
  • 哈希表设计

    2021-01-03 20:06:32
    实验 哈希表设计 数据结构课设 发出来分享 水平有限 希望各位网友多多交流和指正 一、实验目的 熟练掌握哈希表的构造方法,深刻理解哈希表与其他结构表的实质性差别。 二、实验原理 程序的功能是对一批关键字集合...
  • 线性探测哈希表

    2020-06-22 23:02:07
    5.给定一个关键字序列(13,4,18,20,32,15,9,24),哈希表长度为 11,哈希函数为 H(Key)=Key%11,采用线性探测法解决冲突,画出构造的哈希表(8 分),并求出等概率查找时查找成功 的 ASL(成功) (1 分),...
  • 哈希表的插入、删除、查找的时间复杂度都是 O(1); 而平衡二叉查找树的插入、删除、查找的时间复杂度都是 O(logn)。 哈希表速度快,但缺点明显,被反杀: 散列表中的数据是无序存储的,如果要输出有序的数据,需要...
  • 姓名哈希表

    千次阅读 多人点赞 2020-06-13 14:53:55
    /为班级30个人的姓名设计一个哈希表,假设姓名用汉语拼音表示。要求用除留余数法 构造哈希函数,用线性探测再散列法处理冲突,平均查找长度的上限为2。 编写数据结构和算法来实现。要求:将哈希函数和处理冲突方法...
  •  哈希表—线性探测法的ASL成功、不成功计算 将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组。散列函数为: H(key) = (keyx3) MOD 7,处理冲突采用线性...
  • 哈希表查找不成功时的平均查找长度计算和查找成功时的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 ...
  • hash 中ASL 和不成功ASL的计算

    万次阅读 2017-01-09 13:17:29
    α = 表中填入的记录数/哈希表长度 ==> 哈希表长度 = 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...
  • Library import pandas as pd import numpy as np import time 读取数据 df = pd.read_excel('重庆市印刷和记录媒介...print("长为:", len(df)) df.head() 长为: 754 ID 企业名称 电话 企业地址
  • 哈希表(链地址法)

    2021-09-09 08:39:22
    链地址法原理 具体实现代码 hash.h #ifndef _HASH_H_ #define _HASH_H_ typedef int data_t; typedef struct node{ data_t key; data_t value; struct node * next; }link,*linklist; typedef struct{ ...

空空如也

空空如也

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

哈希表asl