精华内容
下载资源
问答
  • 哈希平均查找长度

    万次阅读 多人点赞 2017-08-13 10:53:31
    题目:关键字序列为:{38,25,74,63,52,48},哈希函数为H(k)=k%7,哈希表的长度为7,用线性探测和链地址法处理冲突,分别计算等概率情况下查找成功的平均查找长度。注:没给哈希表长度,给出装填因子时,可求哈希...

    题目:关键字序列为:{38,25,74,63,52,48},哈希函数为H(k)=k%7,哈希表的长度为7,用线性探测和链地址法处理冲突,分别计算等概率情况下查找成功的平均查找长度。

    注:没给哈希表长度,给出装填因子时,可求哈希表长度,
    可根据此公式装填因子=元素个数/表长推:表长=元素个数/装填因子。

    线性探测法

    这里写图片描述

    由上构造的哈希表如下:
    这里写图片描述

    等概率下查找成功的平均查找长度为:
    ASL=(1+3+1+1+2+4)/6=2

    链地址法
    这里写图片描述

    由上构造的哈希表如下:
    这里写图片描述

    等概率下查找成功的平均查找长度为:
    ASL=(1*4+2*2)/6=1.3

    展开全文
  • 哈希表的平均查找长度可以为0吗,老师上课说可以,说是不用比较,但我感觉至少也要1啊
  • 哈希表查找 平均查找长度 解析

    万次阅读 2012-05-03 15:23:12
    哈希表的装填因子 α 的定义如下:  α = 哈希表中元素个数 / 哈希表的长度 ...手工计算等概率情况下查找 成功 的平均查找长度公式  规则如下: ASLsucc=   其中 Ci 为置入每

           哈希表的装填因子 α 的定义如下:

                    α = 哈希表中元素个数 / 哈希表的长度

           α 可描述哈希表的装满程度。显然,α 越小,发生冲突的可能性越小,而 α 越大,发生冲突的可能性也越大

    手工计算等概率情况下查找 成功 的平均查找长度公式

           规则如下:

    ASLsucc 

           其中 C为置入每个元素时所需的比较次数
           
    例如:已知一组关键字序列(191423016820842755111079)按哈希函数H(key)=key % 13 和线性探测处理冲突构造所得哈希表ht[0..15],如图1所示

    比较次数1     2      1      4      3      1      1     3     9      1      1     3

           查找19时,通过计算H(19)= 6,ht[6].key非空且值为19查找成功,则查找关键字19 ,仅需要计算1次地址就可以找到;

           查找14时,通过计算H(14)= 1,ht[1].key非空且值为14查找成功,则查找关键字19 ,仅需要计算1次地址就可以找到;

           查找23时,通过计算H(23)=10,ht[10].key非空且值为23查找成功,则查找关键字23 ,仅需要计算1次地址就可以找到;

           同样,查找关键字68,20,11,均需要计算一次地址就可以找到;

           查找关键字01时,通过计算H(01)=1,ht[1].key非空且值为14≠01,则找第一次冲突处理后的地址H1=(1+1)% 13=2,此时,ht[2].key非空且值为01,查找成功因此查找关键字01时,需要计算2次地址才可以找到;

           查找关键字55时,通过计算H(55)=3,ht[3].key非空且值为68≠55,则找第一次冲突处理后的地址H1=(3+1)% 13=4,此时,ht[4].key非空且值为27≠55,则找第二次冲突后处理地址H2=(3+2)% 13=5, ht[5].key非空且值为55查找成功,因此查找关键字27时,需要计算3次地址才能找到,同理,查找关键字10,84均需要计算3次地址才能找到;

           查找关键字27时,通过计算H(27)=1,ht[1].key非空且值为14≠27,则找第一次冲突处理后的地址H1=(1+1)% 13=2,此时,ht[2].key非空且值为01≠27,则找第二次冲突后处理地址H2=(1+2)% 13=3, ht[3].key非空且值为68≠27,则找第三次冲突后处理地址H3=(1+3)% 13=4,ht[4].key非空且值为27,查找成功,因此查找关键字27时,需要计算4次地址才可以找到;

           根据上面的方法,查找关键字79时,通过计算H(79)=1,ht[1].key非空且值为14≠79,则找第一次冲突处理后的地址H1=(1+1)% 13=2,此时,ht[2].key非空且值为01≠79,则找第二次冲突后处理地址H2=(1+2)% 13=3, ht[3].key非空且值为68≠79,则找第三次冲突后处理地址H3=(1+3)% 13=4,ht[4].key非空且值为27≠79,则找第四次冲突后处理地址H4=(1+4)% 13=5,ht[5].key非空且值为55≠79,则找第五次冲突后处理地址H5=(1+5)% 13=6,ht[6].key非空且值为19≠79则找第六次冲突后处理地址H6=(1+6)% 13=7,ht[7].key非空且值为20≠79,则找第七次冲突后处理地址H7=(1+7)% 13=8,ht[8].key非空且值为84≠79,则找第八次冲突后处理地址H8=(1+8)% 13=9,ht[9].key非空且值为79,查找成功,因此查找关键字79时,需要计算9次地址才可以找到。

           据此计算公式,对如图8.27的哈希表,采用线性探测再散列法处理冲突, 计算出在等概率查找的情况下其查找成功的平均查找长度为:

    ASL(12)==2.5

           为便于计算, 在图8.27哈希表下方加注圆圈, 圆圈内表示的是有冲突时的计算次数, 如代表需要一次地址计算就可找到的关键字有6个,依此类推,即可得到计算结果。

    同理据此公式, 对采用链地址法处理冲突的哈希表例图8.26, 计算出在等概率情况下其查找成功的平均查找长度为:

    ASL(12)succ=

     

    手工计算在等概率情况下查找 不成功 的平均查找长度公式

    查找不成功的情况:(1)  遇到空单元

                                   (2)  按解决冲突的方法完全探测一遍后仍未找到。0 -> r-1 个不成功查找的入口,从每个入口进入后,直到确定查找不成功为止,其关键字的比较次数就是与该入口对应的不成功查找长度。

           

    规则如下:

    ASLunsucc 

           其中Ci为函数取值为 i 时确定查找不成功时比较次数

           据此计算公式,对如图8.27的哈希表,采用线性探测再散列法处理冲突, 计算出在等概率查找的情况下其查找不成功的平均查找长度为:

    ASL(13)==6

           同理据此公式,对采用链地址法处理冲突的哈希表例图8.26, 计算出在等概率情况下其查找不成功的平均查找长度为:

    ASL(13)unsucc=

    链地址法:

     











    展开全文
  • 如何计算哈希表查找失败时的平均查找长度

    千次阅读 多人点赞 2020-04-30 18:20:01
    1.请回答采用线性探测再散列和链地址法处理冲突构建的哈希表中,查找失败时的平均查找长度如何计算? 例:已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为:H(key)=keyMOD13,哈希表长为m=15,设每个记录...

    题目描述:
    1.请回答采用线性探测再散列和链地址法处理冲突构建的哈希表中,查找失败时的平均查找长度如何计算?
    例:已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)
    哈希函数为: H(key)=key MOD 13,哈希表长为m=15,设每个记录的查找概率相等,采用以上两种方法处理冲突,查找失败时的平均查找长度各是多少?

    今天数据结构老师讲的哈希表,留了一个“如何计算哈希表查找失败时的平均查找长度”可是把我给难为住了。(从中午12:00到下午16:00才搞懂,果然还是我太vegetable了

    几个小伙儿伴纷纷查资料,又是计算又是讨论,但是始终没有得到一致的结论。

    纠结的点主要就是:分母应该是哈希表长还是哈希函数里所给的MOD后面的13呢。查了很多资料发现里面的说法不一,而且查到的每一篇博客所给的题目都是除数(MOD后面的那个数)和哈希表长相等。(啊,可能我找的太少啦吧,找啦两三篇都是这样就去问老师啦)

    后来同学告诉我慕课上面讲的就有...anyway~现在是懂了,下面我就用大白话来描述一下我对这个“查找失败时的平均查找长度”的理解

    查找失败的次数就是指:根据哈希函数算出来你所要查找的关键字的位置,如果这个位置存的不是你的目标关键字,那么就按照你所定的存储哈希函数的规则,也就是所在位置+1向后寻找,直到找到你所要的关键字,如果遇到了表中的空位,那么就说明这个表中没有这个关键字,那么查找失败的次数就是你从“通过哈希函数算出的位置”到“表中的第一个遇到的空位”所经过的位数

    也就是说,分母指的是哈希表所给定的长度!!!

    就比如说,你的哈希表如下所示(由上面题目“采用线性探测再散列”生成的哈希表;):

    0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
      14 1 68 27 55 19 20 84 79 23 11 10    

    创建过程为:按照关键字序列顺序依次向哈希表中填入,发生冲突后按照“线性探测”探测到第一个空位置填入

    现在我问你:我想要查找关键字“2”,那么我需要比较多少次才能知道失败了呢?

    答:根据所生成的表可以很容易的看出,关键字“2”不存在于表中。通过题目所给的哈希函数H(key)=key MOD 13可以算出关键字“2”应该在表中序号为2的位置,而如果2的位置所存的数与关键字“2”不相等,那么我需要按照“线性探测”直到找到关键字“2”。如果我没有找到关键字“2”,反而是遇到了空的位置,那么就说明关键字“2”查找失败了,那么我所走的步数就是查找失败的次数。把所有的位置查找失败的次数加起来除以表的总长度,就是“查找失败时的平均查找长度”

    ps:如果有错误欢迎指正,来自一个卑微的计算机大学僧

    答案(以线性探测再散列为例):第一行:序号;第二行:关键字;第三行:查找成功时查找长度;第四行:查找失败时查找长度

    0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
      14 1 68 27 55 19 20 84 79 23 11 10    
      1 2 1 4 3 1 1 3 9 1 1 3    
    1 13 12 11 10 9 8 7 6 5 4 3 2 1 1

    查找失败时的平均查找长度=(1+13+12+11+10+9+8+7+6+5+4+3+2+1+1)/ 15 = 93 / 15

    展开全文
  • 采用除留余数法实现哈希表的创建,任意采用一种处理冲突的方法解决冲突,计算哈希表的平均查找长度。实现以下功能:已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79),哈希函数定义为:H(key)=key MOD 13, 哈希...

    采用除留余数法实现哈希表的创建,任意采用一种处理冲突的方法解决冲突,计算哈希表的平均查找长度。实现以下功能:

    已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79),哈希函数定义为:H(key)=key MOD 13, 哈希表长为m=16。实现该哈希表的散列,并计算平均查找长度(设每个记录的查找概率相等)。

    (1)哈希表定义为定长的数组结构;

    (2)使用线性探测再散列或链地址法解决冲突;

    (3)散列完成后在屏幕上输出数组内容或链表;

    (4)输出等概率查找下的平均查找长度;

    (5)完成散列后,输入关键字完成查找操作,要分别测试查找成功与查找不成功两种情况。

    一、函数间的调用关系

    ff73ae8c9679f0b0ed29f8e24c2bc76a.png

    二、相关算法描述

    1、散列表的创建(除留余数法)算法

    准备工作:将所有散列表初始化为NULLKEY.循环一组关键字个数次,执行以下:

                    ①调用Hash()函数,除留余数法求得放入关键字地址H0

                   ②进入第一个条件判断,判断①得到的地址H0是否为NULLKEY,若单元H0为空,将关键字放入此单元,同时计数器count加一操作,统计关键字比较的次数

                   ③如果条件②不满足,说明利用散列函数得到的单元已经存在关键字,利用线性探测法找下一个散列地址Hi,通过while循环找到新单元地址,循环条件为(HT[Hi].key!=NULLKEY),每循环一次,计数器count加一

                    ④当跳出while循环,说明已经找到没有关键字的单元,可以将关键字key存入,计数器count加一

                    ⑤调用Disp()函数,循环关键字次数输入散列表在屏幕

                    ⑥通过引用传递,将计数器count的数值带回,可以计算出平均查找长度的值

    for (int i = 1;i <= 12;++i)  {    cout << "请输入第" << i << "个关键字:";    cin >> key;    H0 = Hash(key);                    //除留余数法求得插入的地址H0    if (HT[H0].key == NULLKEY)    {      HT[H0].key = key;                //若单元H0为空,将关键字放入此单元      count++;    }                          //if    else    {      int i = 1;      Hi = H0;                    //进入else,说明当前地址为H0的单元不为空      while (HT[Hi].key != NULLKEY)          //当地址Hi对应的单元为空的时候跳出循环      {        Hi = (H0 + i) % MAXSIZE;          //按照线性探测法计算下一个散列地址Hi        ++i;                    //步长+1        count++;      }      HT[Hi].key = key;                //关键字key存放到地址为Hi的单元中      count++;    }                          //else  }

    2、散列表的查找(采用线性探测法处理冲突)

    ①根据散列函s数Hah(key)计算散列地址,若单元H0为空,则所查元素不存在,若单元H0中的关键字为key,则查找成功

    按照线性探测法计算下一个散列地址Hi,若单元Hi为空,则所查元素不存在,若单元H0中的关键字为key,则查找成功

    H0 = Hash(key);                      //根据散列函数Hash(key)计算散列地址  if (HT[H0].key == NULLKEY)    return -1;                      //若单元H0为空,则所查元素不存在  else if (HT[H0].key == key)    return H0;                      //若单元H0中的关键字为key,则查找成功  else  {    for (int i = 1;i < MAXSIZE;++i)    {      Hi = (H0 + i) % MAXSIZE;            //按照线性探测法计算下一个散列地址Hi      if (HT[Hi].key == NULLKEY)        return -1;                  //若单元Hi为空,则所查元素不存在      else if (HT[Hi].key == key)        return Hi;                  //若单元H0中的关键字为key,则查找成功    }                          //for    return -1;  }

    三、完整源码

    #include#includeusing namespace std;#define MAXSIZE 16                      //定长哈希表长度#define NULLKEY 0                      //单元为空的标记typedef int KeyType;typedef int InfoType;/*哈希表的存储结构*/typedef struct{  KeyType key;                      //关键字项目  InfoType otherinfo;                    //其他数据项}HashTable[MAXSIZE];/*散列函数,求散列地址*/int Hash(KeyType key){  return key % 13;                    //除留余数法}/*初始化数组*/void Init(HashTable& HT){  for (int i = 1;i <= 12;i++)    HT[i].key=NULLKEY;                  //初始化将哈希表等长数组的所有单元置为NULLKEY  cout << "数组初始化完成" << endl;}/*散列表的创建,除留余数法*/void CreateHash(HashTable &HT,int &number){  int key,H0,Hi,count=0;  cout << "给出一组关键字:19,14,23,1,68,20,84,27,55,11,10,79" << endl;  for (int i = 1;i <= 12;++i)  {    cout << "请输入第" << i << "个关键字:";    cin >> key;    H0 = Hash(key);                    //除留余数法求得插入的地址H0    if (HT[H0].key == NULLKEY)    {      HT[H0].key = key;                //若单元H0为空,将关键字放入此单元      count++;    }                          //if    else    {      int i = 1;      Hi = H0;                    //进入else,说明当前地址为H0的单元不为空      while (HT[Hi].key != NULLKEY)          //当地址Hi对应的单元为空的时候跳出循环      {        Hi = (H0 + i) % MAXSIZE;          //按照线性探测法计算下一个散列地址Hi        ++i;                    //步长+1        count++;      }      HT[Hi].key = key;                //关键字key存放到地址为Hi的单元中      count++;    }                          //else  }  number = count;}/*散列表的查找,采用线性探测法处理冲突*/int SearchHash(HashTable HT, KeyType key){  //在散列表HT中查找关键字为key的元素,若查找成功,则返回散列表的单元标号,否则返回-1  int H0, Hi;  H0 = Hash(key);                      //根据散列函数Hash(key)计算散列地址  if (HT[H0].key == NULLKEY)    return -1;                      //若单元H0为空,则所查元素不存在  else if (HT[H0].key == key)    return H0;                      //若单元H0中的关键字为key,则查找成功  else  {    for (int i = 1;i < MAXSIZE;++i)    {      Hi = (H0 + i) % MAXSIZE;            //按照线性探测法计算下一个散列地址Hi      if (HT[Hi].key == NULLKEY)        return -1;                  //若单元Hi为空,则所查元素不存在      else if (HT[Hi].key == key)        return Hi;                  //若单元H0中的关键字为key,则查找成功    }                          //for    return -1;  }                            //else}/*在屏幕上输出数组内容*/void Disp(HashTable HT){  cout << endl << "哈希表中的内容为:";  for (int i = 1;i <= 12;i++)    cout << HT[i].key << setw(5);        //输出哈希表中的内容  cout << endl;}int main(void){  KeyType key;  int number;  HashTable HT;                        Init(HT);                        //初始化数组单元都为NULLKEY  CreateHash(HT,number);                      //创建哈希表  Disp(HT);                        //输出到屏幕上  cout << "输出等概率查找条件下的平均查找长度" << (number*1.0) / 12 << endl;  //输出等概率查找条件下的平均查找长度  do  {    cout << "请输入要查找的关键字key:";    cin >> key;                        //输入要查找的关键字    if (SearchHash(HT, key) == -1)      cout << "查找失败,关键字不存在!" << endl;      //若返回下标为-1,则查找失败    else      cout << "查找成功,其关键字在哈希表中的位置为:" << SearchHash(HT, key);//查找成功,输出其在哈希表中的地址    cout << endl;  } while (key >= 0);  return 0;}

    四、调试结果

    c76326a546e88cd5fdda88721dcdefcd.png

    展开全文
  • 哈希表查找——成功和不成功时的平均查找长度

    万次阅读 多人点赞 2017-09-17 13:27:21
    哈希表查找——成功和不成功时的平均查找长度 以下求解过程是按照“计算机统考的计算方法”,不同的老师、教材在“处理冲突”上可能会有不同的方法,所以最主要的是掌握原理即可,对于考研的朋友最好掌握统考...
  • 哈希表查找不成功时的平均查找长度 哈希表查找不成功时的平均查找长度(zz)哈希表查找不成功怎么计算?解答:先建好表,然后可以算出每个位置不成功时的比较次数之和,再除以表空间个数! 例如:散列函数为hash(x)=...
  • 哈希表查找失败的平均查找长度

    千次阅读 2019-10-09 18:02:18
    “它是表中所有可能散列到的位置上要插入新元素时为找到空桶的探查次数的平均值。” 理解: 1. 散列表中已经含有之前插入的元素。 即表已经不空了,若为空的话再插入元素的时候查找空位置一次就可以找到。 2. 这...
  • 哈希表的平均查找长度

    千次阅读 2017-08-03 15:34:17
    查找成功时的平均查找长度 查找不成功时的平均查找长度 http://www.doc88.com/p-903238204265.html
  • 哈希表查找不成功时的平均查找长度计算和查找成功时的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 ...
  • 哈希表查找不成功的平均查找长度

    千次阅读 2017-05-27 10:40:52
    1.查找失败的情况:哈希表中不存在这个元素才会查找失败 2.查找失败的判定;见书 3.因为所查找的数是不确定的,因此可以取遍哈希函数的所有取值,而每一个取值相当于入口,从入口开始查找,当满足失败判定时,确认...
  • 最近复习数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时不太理解,不知道到底是怎么计算出来的。看了几篇博客后终于知道如何计算了,总结如下。 例题: 将关键字序列(7、8、30、11、...
  • 哈希表(又名为是散列表) 散列是一个用于唯一标识对象并在一些预先计算的唯一索引(称为“密钥”)存储每个对象的过程。因此,对象以“键值”对的形式存储,这些项的集合被称为“字典”。可以使用该键值搜索每个...
  • 也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,记为 Hash(key) = Addr 这里的地址是数组下标、索引或内存地址等)。存放记录的数组叫做散列表。②什么是...
  • 本文首发于 vivo互联网技术 微信公众号 链接:https://mp.weixin.qq.com/s/5vxYoeARG1nC7Z0xTYXELA作者:Xuegui ...本文主要介绍哈希冲突、解决方案,以及各种哈希冲突的解决策略上的优缺点。一、哈希表概述哈希表的...
  • ”主要知识点查找表的检索机制平均查找长度折半查找表二叉排序树哈希表1 查找表的检索机制本章给出了三种类型的查找表,第一类是线性索引,记录关键字一般按序排列,以提高检索速度。对应检索采用基于比较检索方法。...
  • 哈希算法的平均查找长度计算

    万次阅读 多人点赞 2017-07-29 23:21:54
    将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0...(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。  Ans:  (1).首先明确一个概念装载因子,装载因
  • 有关HashMap(哈希表)的部分理解:HashMap是一个散列表,存储的是键值对(key-value),能够快速地查找所需的对象(O(1)时间复杂度)。HashMap有两个影响其性能的参数:“初始容量”-哈希表在创建时的容量;...
  • 散列技术时记录的存储位置和它的关键字之间建立的一个确定对应的关系f,使得每个关键字key对应一个存储位置f(key),查找时根据这个对应的关系找到给定值key的映射f(key),若查找集合中存储这个记录,则必定在f(key)...
  • 哈希查找平均长度

    千次阅读 2018-08-11 22:24:55
    将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。...(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 一、查找成功平均长度 通过公式计算出存放的位置,如果该位置已经...
  • 散列表的动态扩容解答+面试题一、散列表(哈希表、Hash 表)不同与之前我们介绍的线性表,所有的数据都是顺序存储,当我们需要在线性表中查找某一数据时,当线性表过长,需要查找的数据排序比较靠后的话,就需要花费...
  • 题图Pid=68670770在最近的学习过程中,发现身边很多朋友对哈希表的原理和应用场景不甚了解,处于会用但不知道什么时候该用的状态,所以我找出了刚学习Java时写的HashMap实现,并以此为基础拓展关于哈希表的实现原理...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 415
精华内容 166
关键字:

哈希平均查找长度