精华内容
下载资源
问答
  • 利用线性探测法构造哈希表

    千次阅读 2016-08-30 17:07:29
    利用线性探测法构造哈希表  已知一组关键字为(26,36,41,38,44,15,68,12,06,51),用除余法构造散列函数,用线性探查法解决冲突构造这组关键字的散列表。  解答:为了减少冲突,通常令装填因子α 由...
    利用线性探测法构造哈希表

          已知一组关键字为(26,36,41,38,44,15,68,12,06,51),用除余法构造散列函数,用线性探查法解决冲突构造这组关键字的散列表。
      解答:为了减少冲突,通常令装填因子α     由除余法的散列函数计算出的上述关键字序列的散列地址为(0,10,2,12,5,2,3,12,6,12)。
         前5个关键字插入时,其相应的地址均为开放地址,故将它们直接插入T[0],T[10),T[2],T[12]和T[5]中。
         当插入第6个关键字15时,其散列地址2(即h(15)=15%13=2)已被关键字41(15和41互为同义词)占用。故探查h1=(2+1)%13=3,此地址开放,所以将15放入T[3]中。
         当插入第7个关键字68时,其散列地址3已被非同义词15先占用,故将其插入到T[4]中。
         当插入第8个关键字12时,散列地址12已被同义词38占用,故探查hl=(12+1)%13=0,而T[0]亦被26占用,再探查h2=(12+2)%13=1,此地址开放,可将12插入其中。
         类似地,第9个关键字06直接插入T[6]中;而最后一个关键字51插人时,因探查的地址12,0,1,…,6均非空,故51插入T[7]中。

    展开全文
  • 线性探测法构造哈希表(hash)

    千次阅读 2015-08-03 21:00:28
    以下是用线性探测法构造哈希表的一个具体例子: 已知一组关键字为(39,49,54,38,44,28,68,12,06,77),用除余法构造散列函数,用线性探查法解决冲突构造这组关键字的散列表。  解答:为了减少冲突,通常...
    以下是用线性探测法构造哈希表的一个具体例子:
    

    已知一组关键字为(39,49,54,38,44,28,68,12,06,77),用除余法构造散列函数,用线性探查法解决冲突构造这组关键字的散列表。
      解答:为了减少冲突,通常令装填因子α<l。这里关键字个数n=10,不妨取m=13,此时α≈0.77,散列表为T[0..12],散列函数为:h(key)=key%13。
         由除余法的散列函数计算出的上述关键字序列的散列地址为(0,10,2,12,5,2,3,12,6,12)。
         前5个关键字插入时,其相应的地址均为开放地址,故将它们直接插入T[0],T[10),T[2],T[12]和T[5]中。
         当插入第6个关键字15时,其散列地址2(即h(15)=15%13=2)已被关键字41(15和41互为同义词)占用。故探查h1=(2+1)%13=3,此地址开放,所以将15放入T[3]中。
         当插入第7个关键字68时,其散列地址3已被非同义词15先占用,故将其插入到T[4]中。
         当插入第8个关键字12时,散列地址12已被同义词38占用,故探查hl=(12+1)%13=0,而T[0]亦被26占用,再探查h2=(12+2)%13=1,此地址开放,可将12插入其中。

         类似地,第9个关键字06直接插入T[6]中;而最后一个关键字51插人时,因探查的地址12,0,1,…,6均非空,故51插入T[7]中。


    转载自:http://blog.163.com/wf_shunqiziran/blog/static/1763072092012612114126231/

    展开全文
  • 使用线性探测法构造哈希表

    千次阅读 2011-07-11 17:30:34
    原文:http://hi.baidu.com/jiang_yy_jiang/blog/item/931d763ed8edc8f2838b13c3.html 已知一组关键字为(26,36,41,38,44,15,68,12,06,51),用除余法构造散列函数,用线性探查解决冲突构

    原文:http://hi.baidu.com/jiang_yy_jiang/blog/item/931d763ed8edc8f2838b13c3.html


    已知一组关键字为(26,36,41,38,44,15,68,12,06,51),用除余法构造散列函数,用线性探查法解决冲突构造这组关键字的散列表。
      解答:为了减少冲突,通常令装填因子α<l。这里关键字个数n=10,不妨取m=13,此时α≈0.77,散列表为T[0..12],散列函数为:h(key)=key%13。
         由除余法的散列函数计算出的上述关键字序列的散列地址为(0,10,2,12,5,2,3,12,6,12)。
         前5个关键字插入时,其相应的地址均为开放地址,故将它们直接插入T[0],T[10),T[2],T[12]和T[5]中。
         当插入第6个关键字15时,其散列地址2(即h(15)=15%13=2)已被关键字41(15和41互为同义词)占用。故探查h1=(2+1)%13=3,此地址开放,所以将15放入T[3]中。
         当插入第7个关键字68时,其散列地址3已被非同义词15先占用,故将其插入到T[4]中。
         当插入第8个关键字12时,散列地址12已被同义词38占用,故探查hl=(12+1)%13=0,而T[0]亦被26占用,再探查h2=(12+2)%13=1,此地址开放,可将12插入其中。
         类似地,第9个关键字06直接插入T[6]中;而最后一个关键字51插人时,因探查的地址12,0,1,…,6均非空,故51插入T[7]中。


    展开全文
  • 线性探测法构建哈希表

    千次阅读 2017-03-26 16:27:04
    下面看下2010年2010年全国硕士研究生入学统一考试计算机科学与...散列表的存储空间是一个下标从0开始的一维数组,散列函数为: H(key) = (keyx3) MOD 7,处理冲突采用线性探测再散列,要求装填(载)因子为0.7。

    下面看下2010年2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题中一个考哈希表的题。
    Question1:
    将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组,散列函数为: H(key) = (keyx3) MOD 7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。
    (1) 请画出所构造的散列表。
    (2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。
    Ans:
    (1).首先明确一个概念装载因子,装载因子是指所有关键子填充哈希表后饱和的程度,它等于 关键字总数/哈希表的长度。 根据题意,我们可以确定哈希表的长度为 L = 7/0.7 = 10;因此此题需要构建的哈希表是下标为0~9的一维数组。根据散列函数可以得到如下散列函数值表。
    H(Key) = (keyx3) MOD 7, 例如key=7时, H(7) = (7x3)%7 = 21%7=0,其他关键字同理。
    Key 7 8 30 11 18 9 14
    H(Key) 0 3 6 5 5 6 0
    (表1)
    采用线性探测再散列法处理冲突,所构造的散列表为:
    地址 0 1 2 3 4 5 6 7 8 9
    关键字 7 14 8 11 30 18 9
    (表2)
    下面对散列表的构造方式加以说明,注意表1中的关键字7和14,30和9, 11和18,这三组关键子的H(Key)值相同,这在构建散列表时就会产生冲突,因为他们的地址相同,所以要通过一定的冲突处理方法来解决这个问题。依题,采用线性探测再散列法处理冲突。下面详细介绍如何构建散列表:
    第一个key 7,它的地址是0,因此放到散列表的数组下表为0的位置,这个位置上没有关键字,因此没有冲突可以直接填入;
    第二个key 8,它的地址是3,因此放到散列表的数组下表为3的位置,这个位置上没有关键字,因此没有冲突可以直接填入;
    第三个key 30,它的地址是6,因此放到散列表的数组下表为6的位置,这个位置上没有关键字,因此没有冲突可以直接填入;
    第四个key 11,它的地址是5,因此放到散列表的数组下表为5的位置,这个位置上没有关键字,因此没有冲突可以直接填入;
    第五个key 18,它的地址是5,因此放到散列表的数组下表为5的位置,但这个位置上已经有关键字11,遇到了冲突,此时我们根据线性探测再散列法来处理这个冲突,探测下一个位置6, 6这个位置上已经存在关键字30则继续增加步长1,因此现在的新地址应为7,位置7上没有关键字,放入即可,到此冲突已经解决;
    第六个key 9,它的地址是6,因此放到散列表的数组下表为6的位置,但这个位置上已经有关键字30,遇到了冲突,探测下一个位置7, 7这个位置上已经存在关键字18则继续增加步长1,因此现在的新地址应为8,位置8上没有关键字,放入即可;
    第七个key 14,它的地址是0,因此放到散列表的数组下表为0的位置,但这个位置上已经有关键字7,遇到了冲突,探测下一个位置1, 位置1上没有关键字,放入即可;
    到这一步所有关键字均已填入,散列表已经构造完成,如表2所示。
    (2)等概率情况下查找成功平均查找长度:
    这一问可以根据第一问的构造过程求解:
    key7一次就填入了表中,因此查找次数为1,同理8, 30, 11查找次数均为1; key18 进行了3次放入操作,探测位置分别是5,6,7 ,因此查找次数为3;key9也是3次;key14 进行了两次探测,因此查找次数为2。次数表如表3所示
    Key 7 8 30 11 18 9 14
    Count 1 1 1 1 3 3 2
    (表3)
    所以ASLsuccess= (1+1+1+1+3+3+2)/ 7 = 12/7。
    查找不成功时的查找次数:第n个位置不成功时的比较次数为,第n个位置到第1个没有数据位置的距离:如第0个位置取值为1,第1个位置取值为2.注意:
    <查找成功时,分母为哈希表元素个数,查找不成功时,分母为哈希表长度。>

    展开全文
  • 哈希表(线性存储)+ 线性探测法解决哈希冲突: 将关键路径通过哈希函数映射到哈希表中,哈希表是线性的结构体数组,其中,线性存储中,哈希长度这里要提前给出,给出的长度一般是是大于插入数据数组的长度的最小...
  • 哈希概念 在之前学习过的顺序搜索和二叉树搜索中,元素存储位置和元素各关键码之间没有对应关系,因此在查找一个元素时,必须要经过关键码的多次比较。搜索的效率取决于搜索过程中元素的比较次数。 我们希望...
  • 线性探测法构造hash

    2014-10-17 09:52:42
    已知一组关键字为(39,49,54,38,44,28,68,12,06,77),用除余法构造散列函数,用线性探查解决冲突构造这组关键字的散列表。  解答:为了减少冲突,通常令装填因子α  由除余法的散列函数计算出的上述...
  • 用拉链法和线性探测法解决哈希冲突 转自:http://www.tuicool.com/articles/QNjAbaf   前言 前面学习到的几种算法比如 红黑树 , 二叉搜索树 ,查找插入 时间复杂度 最快也只能到 O(logn) .现在介绍一...
  • 构造哈希表以及二次探测法

    千次阅读 2018-09-16 19:53:39
    构造哈希表(散列表)以及二次探测法 今天做笔试题时,遇到一道构造哈希表的题,hash函数是 k%11 ,然后一个数组记不清了,然后就是问二次探测法进行,问下面那个是正确,懵逼啊,没做过,不知道,乱选直接下...
  • 哈希表-线性探测法理论 线性探测法的理论我们在上一篇博客已经阐述了。 现在我们来看看线性探测法的增删查的代码思想: 哈希表的增加元素: 注意:往后遍历寻找空闲位置的时候,要注意是环形遍历哦!不然访问数组...
  • 从键盘输入各记录,以用户名为关键字建立哈希表, 哈希函数用除留取余数法构造, 采用线性探测法解决冲突。可以插入、查找、删除并显示给定用户名的记录, 并计算查找长度, 哈希表保存到文件中。 测试数据: 取自己...
  • 哈希表构造线性探测法

    千次阅读 2016-11-08 12:24:50
    散列表(Hash table,也叫哈希表),是依据关键码值(Key value)而直接进行訪问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来訪问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组...
  • 构造哈希表之二次探测法

    万次阅读 多人点赞 2016-06-08 01:19:00
    HashTable-散列表/哈希表 是根据关键字(key)而直接...构造哈希表的几种方法 1.直接定址(取关键字的某个线性函数为哈希地址) 2.除留余数(取关键值被某个不大于散列表长m的数p除后的所得的余数为散列地址) 3.
  • 哈希表线性探测法和链地址法求查找成功与不成功的平均查找
  • 开放定制也是处理构造哈希表中关键字的哈希地址冲突的
  • 线性探测哈希表

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

    千次阅读 2018-10-27 13:34:48
    分别画出用线性探测法和拉链法解决冲突时构造哈希表,并求出在等概率情况下,这两种方法的查找成功和查找不成功的平均查找长度。 2.链地址法:用链地址发解决冲突的方法时:把所有关键字为同义词的记录...
  • 搜索结构之哈希表线性探测法

    万次阅读 2017-06-20 12:01:58
    散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组...
  • 一、哈希表 1、概念  哈希表(Hash Table)也叫散列表,是根据关键码值(Key Value)而直接进行访问的数据结构。它通过把关键码值映射到哈希表中的一个位置来访问记录,以加快查找的速度。这个映射函数就做散列函数,...
  • /* / / @哈希表(线性探测法) / */ #include<stdio.h> #include<stdlib.h> #include<windows.h> #define Field -1 #define null -32768 typedef struct hashmap...
  • 1知识点:除留余数法定义hash函数+线性探测法解决hash冲突数据结构实验之查找七:线性之哈希表 Time Limit: 1000MS Memory Limit: 65536KBProblem Description 根据给定的一系列整数关键字和素数p,用除留余数法...
  • 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组...
  • 根据给定的一系列整数关键字和素数p,用除留余数法定义hash函数H(Key)=Key%p,将关键字映射到长度为p的哈希表中,用线性探测法解决冲突。重复关键字放在hash表中的同一位置。 Input 连续输入多组数据,每组...
  • 哈希表(除留余数法构造 线性探测再散列法处理冲突)#include &lt;stdio.h&gt;#include &lt;stdlib.h&gt;#include &lt;string.h&gt;int main(){ int a[11]={22,41,53,46,30,13,1,67},b[11]...
  • 【数据结构】哈希表线性探测法

    万次阅读 多人点赞 2018-03-28 22:41:15
    哈希表是一种搜索结构,当数据量大时,哈希搜索的效率高,平均时间复杂度O(1)。 【哈希查找】: (1)在插入时,根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放。 (2)在搜索时,对...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,419
精华内容 2,567
关键字:

线性探测法构造哈希表