精华内容
下载资源
问答
  • 散列表查找失败平均查找长度

    千次阅读 多人点赞 2020-11-01 21:04:40
    要想知道 散列表查找失败平均查找长度,就要知道什么叫做查找失败!举个栗子:8个数字 key%11 如下算好了: 散列地址 0 1 2 3 4 5 6 7 8 9 10 关键字 33 1 13 12...

    如果你看了很多其他博客然后都看不懂看到了这篇,你一定可以容易懂的!我佛了,这么简单的东西死板地讲题目不讲原理鬼看得懂啊,这种风气真的不行,我忍不住想骂一声垃圾,啥玩意儿,误人子弟!原理懂了啥题不会做?

    要想知道 散列表查找失败的平均查找长度,就要知道什么叫做查找失败!举个栗子:8个数字  key%11  如下算好了:

    散列地址 0 1 2 3 4 5 6 7 8 9 10
    关键字 33 1 13 12 34 38 27 22      
    冲突次数 0 0 0 2 3 0 1 7      

    什么叫做查找失败?比如你要查55这个关键字,你必须%11,等于0,查地址0为33,不对,下一位1,不对,继续往下查找直到出现空的才知道这个关键字一定不存在,否则就放在空着的那个地址。所以以上表,计算地址为0的关键字查了9次才才知道没有这个关键字称为查找失败;计算地址为1的关键字只有探测完1-8号才能确定该元素不存在,以此类推。但是注意了,如果计算地址为8的或者9的、10的,只需要查找一次就知道该地址为空,失败了。因此查找一次就行。而且要知道如果查找成功是除以关键字个数,但是查找失败是除以你要模的数字本题是11,千万记住了,不是地址个数,不是关键字个数。综上所述,查找失败的平均查找长度为(9+8+7+6+5+4+3+2+1+1+1)/11=47/11。放心错不了,书上原题。

    还要注意,如下题型H(key)=key%7:

    散列地址 0 1 2 3 4 5 6 7 8
    关键字 98 22 30 87 11 40 6 20  

    千万注意,%7只能映射到0-6,散列函数不可能映射7,因此查找失败平均查找长度为(9+8+7+6+5+4+3)/7=6。看到这你可能想骂娘,啥玩意儿,别急。我会让你看懂,因为我最讨厌虾鸡吧写博客的傻逼玩意儿,写的不清楚又不解释,还误人子弟,low咖!!!好了回归正题。首先要知道,我们求平均查找长度其实在求概率,对于成功的平均查找长度,查找每个元素的概率是1/8,这个8就是关键字个数。就是说,查找成功你只能选择8个中的一个,否则成功不了,所以都是在等概率1/8情况下。查找失败也是一样,这里对每个位置的查找概率都是1/7,注意7是你要模的数字,就是说,你随便拿几个数,模7,只能是0、1、2、3、4、5、6,其中一种情况,不可能是7、8以后的数字,所以只需要计算地址在0-6中的概率。如果计算地址后为0,那么需要比较9次,以此类推,所以只能是上面的计算式子,别搞错了噢!还有要注意有些散列表不是完全填满,中间有空位,那相信你看完上面原理就不用我解释了,找到了空位还没有就说明不存在嘛,否则它就占位这个空位了。注意以上所讨论的全部是线性探测,如果是平方探测注意左右跳动,具体问题具体分析,就不展开了。相信你看到这个已经真正明白了什么叫做查找失败平均查找长度。对于垃圾博客需要狠狠骂,对于我也是,我写的烂的大家给我狠狠骂,这样才能少一些误人子弟的渣渣了,只讲怎么怎么操作不讲原理有什么狗屁用,换个方式描述不还是不会。知其然要知其所以然!!!以上如果有错误,还请大家狠狠指出来,谢谢大家!

    比如这篇博客,真佛了,一来就巴拉巴拉在那算算算,好像谁不会计算散列表似的,人家真正不懂的是查找失败的平均查找长度的计算,真正的标题党。垃圾文章!!!

     

     

     

     

     

     

    展开全文
  • 因此,散列表查找元素的性能是极好的。常用于作为在常量时间范围内辅助查找一个元素。对于普通数组,可以直接寻址,即可以直接通过数组下标访问一个元素。如果空间允许的话,可以将元素的key作为数组下标映射。但是...

    散列表

    散列表(hash table)是实现字典操作的有效数据结构。在最坏情况下,查找一个元素的时间复杂度是O(n);而在合理假设情况下,查找一个元素的时间复杂度是O(1)。因此,散列表查找元素的性能是极好的。

    常用于作为在常量时间范围内辅助查找一个元素。

    对于普通数组,可以直接寻址,即可以直接通过数组下标访问一个元素。如果空间允许的话,可以将元素的key作为数组下标映射。但是,如果实际存储的元素要比实际可存储的元素小很多时,仍使用直接寻址法,会带来很大的空间浪费。主要缺点:

    1、空间浪费;

    2、一次申请庞大的空间,内存容量限制。

    bbd48169542b916c3ebf3fcce008d176.png
    ea013907e69d033acdaffcbca97618d1.png
    0bb5543bad3ed173b480c580e97d4808.png
    48ded858c6a79e8f0e70bcb114a5bcab.png

    因此,散列表是作为对普通数组的扩展。在散列表中,不是通过关键字作为数组下标,而是根据关键字来计算出数组下标。如果多个关键字计算出同一个下标,就会出现“冲突”。所以,在理想情况下,如果完全可以避免冲突的话,散列表的元素查找时间就是O(1)。

    在直接寻址方式下,元素是放在关键字为K的槽中;而散列方式下,元素是放在f(K)的槽中,其中,函数f()称为散列函数,通过散列函数来计算出槽的位置。

    散列函数

    • 除法散列法

    f(k) = k % m

    其中,k是关键字,m是所映射的槽数。假设:m = 10,k = 99,则f(99) = 99 % 10 = 9

    m不要取2的幂。为什么?

    假设k是0~1000范围内数值,m为8,即2的3次幂。

    96 % 8 = 0110 0000 % 2³ = (1*2³*2³ + 1*2²*2³) % 2³ = 0

    97 % 8 = 0110 0001 % 2³ = (1*2³*2³ + 1*2²*2³ + 1*2º) % 2³ = 1*2º= 1

    98 % 8 = 0110 0010 % 2³ = (1*2³*2³ + 1*2²*2³ + 1*2¹) % 2³ = 2¹= 2

    99 % 8 = 0110 0011 % 2³ = (1*2³*2³ + 1*2²*2³ + 1*2¹ + 1*2º) % 2³ = 2¹+ 2º = 3

    100 % 8 = 0110 0100 % 2³ = (1*2³*2³ + 1*2²*2³ + 1*2²) % 2³ = 2² = 4

    101 % 8 = 0110 0101 % 2³ = (1*2³*2³ + 1*2²*2³ + 1*2² + 1*2º) % 2³ = 2² + 2º = 5

    102 % 8 = 0110 0110 % 2³ = (1*2³*2³ + 1*2²*2³ + 1*2² + 1*2¹) % 2³ = 2² + 2¹ = 6

    103 % 8 = 0110 0111 % 2³ = (1*2³*2³ + 1*2²*2³ + 1*2² + 1*2¹+ 1*2º) % 2³ = 2² + 2¹ + 2º = 7

    104 % 8 = 0110 1000 % 2³ = (1*2³*2³ + 1*2²*2³ + 1*2³) % 2³ = 0

    105 % 8 = 0110 1001 % 2³ = (1*2³*2³ + 1*2²*2³ + 1*2³ + 1*2º) % 2³ = 2º = 1

    以上分析可知,余数在0~7范围内,不会超过8,也就是k的后三位就可以完全表示余数。如果关键字均匀分布在后三位,此方法可行。但如果遇到:

    0000 0000(0)

    0000 1000(8)

    0001 0000(16)

    0001 1000(24)

    如上后三位均为0的情况,这些关键字都处于同一个槽中,无法很好的避免冲突。所以,好的散列函数为了尽可能的避免冲突的发生,应该尽量考虑所有位。

    一个不接近2的幂次的素数是一个好的选择。

    假设一个存放2000个字符的hash表,可以接受的冲突是3次,则2000/3 ≈ 667,m的选择是接近667,但不接近2的幂次的素数,因此m可以选择为673,或677,或683,或691,或701。

    • 乘法散列法

    f(k) = ⎣m(kA % 1)⎦

    其中:

    1、0

    2、kA % 1得到的是kA结果的小数部分

    3、m是槽数,一般取2的p次

    假设k=123_456,p=14,m=2^14=16_384,w=32(每个关键字占32位)

    ∵ 0

    ∴ A=s / 2^32,其中 0 < s < 2^32,当A ≈(√5 - 1)/2时,是个比较理想的值

    s = A * 2^32

    s=2.6544357694972305E9

    ∵ k和s都是32位

    ∴ ks = r1 * 2^32 + r2 <1>

    kA = ks / 2^32,相当于将ks右移32位 <2>

    ∵ kA % 1 取小数部分

    ∴ 其中r2即为小数部分 <3>

    ∵ m(kA % 1),m=2^14

    ∴ 即将r2左移14位 <4>

    r2的高14位即是f(k)的结果,f(123_456) = 67

    8a25332339081826c9588dfcda849c19.png
    • 实现
    0f88d6ec47b1194b4b6f1e2b1e3e1064.png
    7998bafa80a88fcc633217a558dd668e.png

    解决冲突

    • 链接法

    把散列在同一个槽中的所有元素都放在一个链表中。

    1、插入最坏情况时间复杂度是O(1),因为在发生冲突时,始终插入到链表头位置;

    2、查找平均情况是O(1),最坏情况是O(n),即所有元素都散列到同一个槽中。

    假设有n个元素,放到m个槽位中,则α=n/m,α称为装载因子。在简单均匀散列假设下:

    1)一次不成功查找平均时间为O(1+α);

    2)一次成功查找平均时间为O(1+α);

    3、删除,对于双向链表最坏情况O(1),而对于单向链表删除和查找渐进相同。

    全部字典操作都可以在平均情况O(1)时间内完成。

    61294034da8dd0a4219d25ec55f9eb5a.png
    334977cae98a8eb28ea0ca755561c7c3.png
    670f683ffa5e31ef4c2516b7a68a955b.png
    6707d1004bf69cbf4a20831aa1c007be.png
    • 开放寻址法

    所有元素都放在散列表中,当插入元素发生冲突时,通过线性探查(二次探查/双重散列)将元素放入到槽位为NULL的位置。查找和插入都可以在线性时间O(1)内完成。

    开放寻址法不需要额外的空间存储冲突元素,而是通过计算出存放的槽位提高检索速度,从而提高了空间的利用率。

    α绝对不会超过1,因为当散列表被填满时,不能再插入任何元素,此时n和槽数m相等。

    假设有n个元素,放到m个槽位中,则α=n/m<1。在简单均匀散列假设下:

    1)一次不成功查找平均时间为1/(1-α);

    2)一次成功查找平均时间为(1/α)㏑(1/(1-α));

    1、线性探查

    h(k, i) = (h'(k) + i) % m

    1)i = 0, 1, 2, ... m-1

    2)共有m中不同的探查序列

    3)会造成一次群集(重度),连续槽被占用(查找是顺序自增),相应的查找时间也会相应增加。

    2、二次探查

    h(k, i) = (h'(k) + c1i+c2i²) % m

    1)i = 0, 1, 2, ... m-1

    2)共有m中不同的探查序列

    3)会造成二次群集(轻度),当初始位置相同时,探查序列也就相同了。

    3、双重散列

    h(k, i) = (h1(k) + ih2(k)) % m

    1)开放寻址的最好方法之一,所产生的探查序列具有随机性。

    2)为了可以探查整个散列表,要求h2(k)同m必须互素(公约数为1)

    a、m是2的幂次,h2(k)总返回基数

    b、m是素数,h2(k)总返回比m小的正整数

    c9fab432238ba626f16336f4a76c847c.png
    d36b3d8d79785106913495a8cf4e78ee.png
    4d80f35123922621f41591032ebbf5b1.png
    83576b46cda6aea8015c8b009dc4a612.png
    6a0e5de200b6c0540fcfff7587e46b93.png
    • 完全散列(perfect hashing)

    能够在O(1)最坏情况时间内完成关键字的查找。要求关键字集合是静态的,各个关键字一旦进入散列表,就不会再变化了。如:cd-rom的文件名,程序设计语言的关键字。

    Java集合框架中的HashSet和HashMap

    HashSet

    1、基于Hash表,实际上是基于HashMap实例。每一个元素对应HashMap的key。

    2、无序(基于hash表),元素不可重复。

    3、对于基本操作,如add、remove、contains、size提供了时间复杂度是O(1)的性能。对于iterate,同Hash表的容量相关,因此为保证性能,初始容量不要太大或负载因子不要太小。

    HashMap

    1、与Hashtable大致一致,除了它是不同步、key和value接受null值。

    2、无序,特别是不能保证一直保持不变。

    3、对于基本操作,如get、put提供了时间复杂度是O(1)的性能。对于iterate,同Hash表的容量相关,因此为保证性能,初始容量不要太大或负载因子不要太小。

    4、有两个参数影响其性能

    1)初始容量,Hash表的槽数。

    2)负载因子,一个度量散列表在自动增加其容量之前被允许达到的容量占比的程度。当哈希表的长度超过了负载因子和当前的容量的乘积,哈希表会重建(重新散列),最后的容量是原来容量的两倍。

    5、默认情况容量是16,负载因子是0.75。

    6、HashMap使用链接法解决冲突(相同hash值),当链表长度大于等于TREEIFY_THRESHOLD(默认为8)时,将链表转换为红黑树,当小于等于UNTREEIFY_THRESHOLD(默认为6)时,又会将红黑树转换为链表以达到最佳性能。

    df48c936cef5a6e9c5fd4d864646be90.png
    展开全文
  • 散列思想散列表的英文叫“Hash Table”,我们平时也叫它“哈希表”或者“Hash表”,你一定也经常听过它,我在前面的文章里,也不止一次提到过,但是你是不是真的理解这种数据结构呢?散列表用的是数组支持按照下标...

    散列思想

    散列表的英文叫“Hash Table”,我们平时也叫它“哈希表”或者“Hash表”,你一定也经常听过它,我在前面的文章里,也不止一次提到过,但是你是不是真的理解这种数据结构呢?

    散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表。

    我用一个例子来解释一下。假如我们有89名选手参加学校运动会。为了方便记录成绩,每个选手胸前都会贴上自己的参赛号码。这89名选手的编号依次是1到89。现在我们希望编程实现这样一个功能,通过编号快速找到对应的选手信息。你会怎么做呢?

    我们可以把这89名选手的信息放在数组里。编号为1的选手,我们放到数组中下标为1的位置;编号为2的选手,我们放到数组中下标为2的位置。以此类推,编号为k的选手放到数组中下标为k的位置。

    因为参赛编号跟数组下标一一对应,当我们需要查询参赛编号为x的选手的时候,我们只需要将下标为x的数组元素取出来就可以了,时间复杂度就是O(1)。这样按照编号查找选手信息,效率是不是很高?

    实际上,这个例子已经用到了散列的思想。在这个例子里,参赛编号是自然数,并且与数组的下标形成一一映射,所以利用数组支持根据下标随机访问的时候,时间复杂度是O(1)这一特性,就可以实现快速查找编号对应的选手信息。

    你可能要说了,这个例子中蕴含的散列思想还不够明显,那我来改造一下这个例子。

    假设校长说,参赛编号不能设置得这么简单,要加上年级、班级这些更详细的信息,所以我们把编号的规则稍微修改了一下,用6位数字来表示。比如051167,其中,前两位05表示年级,中间两位11表示班级,最后两位还是原来的编号1到89。这个时候我们该如何存储选手信息,才能够支持通过编号来快速查找选手信息呢?

    思路还是跟前面类似。尽管我们不能直接把编号作为数组下标,但我们可以截取参赛编号的后两位作为数组下标,来存取选手信息数据。当通过参赛编号查询选手信息的时候,我们用同样的方法,取参赛编号的后两位,作为数组下标,来读取数组中的数据。

    这就是典型的散列思想。其中,参赛选手的编号我们叫作键(key)或者关键字。我们用它来标识一个选手。我们把参赛编号转化为数组下标的映射方法就叫作散列函数(或“Hash函数”“哈希函数”),而散列函数计算得到的值就叫作散列值(或“Hash值”“哈希值”)。

    323914b522837e1ae9813c9dbecd2805.png

    通过这个例子,我们可以总结出这样的规律:散列表用的就是数组支持按照下标随机访问的时候,时间复杂度是O(1)的特性。我们通过散列函数把元素的键值映射为下标,然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时,我们用同样的散列函数,将键值转化数组下标,从对应的数组下标的位置取数据。

    散列函数

    从上面的例子我们可以看到,散列函数在散列表中起着非常关键的作用。现在我们就来学习下散列函数。

    散列函数,顾名思义,它是一个函数。我们可以把它定义成hash(key),其中key表示元素的键值,hash(key)的值表示经过散列函数计算得到的散列值。

    那第一个例子中,编号就是数组下标,所以hash(key)就等于key。改造后的例子,写成散列函数稍微有点复杂。我用伪代码将它写成函数就是下面这样:

    int hash(String key) { // 获取后两位字符 string lastTwoChars = key.substr(length-2, length); // 将后两位字符转换为整数 int hashValue = convert lastTwoChas to int-type; return hashValue;}

    刚刚举的学校运动会的例子,散列函数比较简单,也比较容易想到。但是,如果参赛选手的编号是随机生成的6位数字,又或者用的是a到z之间的字符串,该如何构造散列函数呢?我总结了三点散列函数设计的基本要求:

    1. 散列函数计算得到的散列值是一个非负整数;
    2. 如果key1 = key2,那hash(key1) == hash(key2);
    3. 如果key1 ≠ key2,那hash(key1) ≠ hash(key2)。

    我来解释一下这三点。其中,第一点理解起来应该没有任何问题。因为数组下标是从0开始的,所以散列函数生成的散列值也要是非负整数。第二点也很好理解。相同的key,经过散列函数得到的散列值也应该是相同的。

    第三点理解起来可能会有问题,我着重说一下。这个要求看起来合情合理,但是在真实的情况下,要想找到一个不同的key对应的散列值都不一样的散列函数,几乎是不可能的。即便像业界著名的MD5、SHA、CRC等哈希算法,也无法完全避免这种散列冲突。而且,因为数组的存储空间有限,也会加大散列冲突的概率。

    所以我们几乎无法找到一个完美的无冲突的散列函数,即便能找到,付出的时间成本、计算成本也是很大的,所以针对散列冲突问题,我们需要通过其他途径来解决。

    散列冲突

    再好的散列函数也无法避免散列冲突。那究竟该如何解决散列冲突问题呢?我们常用的散列冲突解决方法有两类,开放寻址法(open addressing)和链表法(chaining)。

    1.开放寻址法

    开放寻址法的核心思想是,如果出现了散列冲突,我们就重新探测一个空闲位置,将其插入。那如何重新探测新的位置呢?我先讲一个比较简单的探测方法,线性探测(Linear Probing)。

    当我们往散列表中插入数据时,如果某个数据经过散列函数散列之后,存储位置已经被占用了,我们就从当前位置开始,依次往后查找,看是否有空闲位置,直到找到为止。

    我说的可能比较抽象,我举一个例子具体给你说明一下。这里面黄色的色块表示空闲位置,橙色的色块表示已经存储了数据。

    505f32de1109665970daafb7323b63f8.png

    从图中可以看出,散列表的大小为10,在元素x插入散列表之前,已经6个元素插入到散列表中。x经过Hash算法之后,被散列到位置下标为7的位置,但是这个位置已经有数据了,所以就产生了冲突。于是我们就顺序地往后一个一个找,看有没有空闲的位置,遍历到尾部都没有找到空闲的位置,于是我们再从表头开始找,直到找到空闲位置2,于是将其插入到这个位置。

    在散列表中查找元素的过程有点儿类似插入过程。我们通过散列函数求出要查找元素的键值对应的散列值,然后比较数组中下标为散列值的元素和要查找的元素。如果相等,则说明就是我们要找的元素;否则就顺序往后依次查找。如果遍历到数组中的空闲位置,还没有找到,就说明要查找的元素并没有在散列表中。

    91f655dfdd86de52f7ce56d3a62e6efa.png

    散列表跟数组一样,不仅支持插入、查找操作,还支持删除操作。对于使用线性探测法解决冲突的散列表,删除操作稍微有些特别。我们不能单纯地把要删除的元素设置为空。这是为什么呢?

    还记得我们刚讲的查找操作吗?在查找的时候,一旦我们通过线性探测方法,找到一个空闲位置,我们就可以认定散列表中不存在这个数据。但是,如果这个空闲位置是我们后来删除的,就会导致原来的查找算法失效。本来存在的数据,会被认定为不存在。这个问题如何解决呢?

    我们可以将删除的元素,特殊标记为deleted。当线性探测查找的时候,遇到标记为deleted的空间,并不是停下来,而是继续往下探测。

    dd1fb97cbdfb6bc03634714cefca9430.png

    你可能已经发现了,线性探测法其实存在很大问题。当散列表中插入的数据越来越多时,散列冲突发生的可能性就会越来越大,空闲位置会越来越少,线性探测的时间就会越来越久。极端情况下,我们可能需要探测整个散列表,所以最坏情况下的时间复杂度为O(n)。同理,在删除和查找时,也有可能会线性探测整张散列表,才能找到要查找或者删除的数据。

    对于开放寻址冲突解决方法,除了线性探测方法之外,还有另外两种比较经典的探测方法,二次探测(Quadratic probing)和双重散列(Double hashing)。

    所谓二次探测,跟线性探测很像,线性探测每次探测的步长是1,那它探测的下标序列就是hash(key)+0,hash(key)+1,hash(key)+2……而二次探测探测的步长就变成了原来的“二次方”,也就是说,它探测的下标序列就是hash(key)+0,hash(key)+12,hash(key)+22……

    所谓双重散列,意思就是不仅要使用一个散列函数。我们使用一组散列函数hash1(key),hash2(key),hash3(key)……我们先用第一个散列函数,如果计算得到的存储位置已经被占用,再用第二个散列函数,依次类推,直到找到空闲的存储位置。

    不管采用哪种探测方法,当散列表中空闲位置不多的时候,散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率,一般情况下,我们会尽可能保证散列表中有一定比例的空闲槽位。我们用装载因子(load factor)来表示空位的多少。

    装载因子的计算公式是:

    散列表的装载因子=填入表中的元素个数/散列表的长度

    装载因子越大,说明空闲位置越少,冲突越多,散列表的性能会下降。

    2.链表法

    链表法是一种更加常用的散列冲突解决办法,相比开放寻址法,它要简单很多。我们来看这个图,在散列表中,每个“桶(bucket)”或者“槽(slot)”会对应一条链表,所有散列值相同的元素我们都放到相同槽位对应的链表中。

    c0881b78608213ec685bc1d7917b7919.png

    当插入的时候,我们只需要通过散列函数计算出对应的散列槽位,将其插入到对应链表中即可,所以插入的时间复杂度是O(1)。当查找、删除一个元素时,我们同样通过散列函数计算出对应的槽,然后遍历链表查找或者删除。那查找或删除操作的时间复杂度是多少呢?

    实际上,这两个操作的时间复杂度跟链表的长度k成正比,也就是O(k)。对于散列比较均匀的散列函数来说,理论上讲,k=n/m,其中n表示散列中数据的个数,m表示散列表中“槽”的个数。

    内容小结

    今天讲了一些比较基础、比较偏理论的散列表知识,包括散列表的由来、散列函数、散列冲突的解决方法。

    散列表来源于数组,它借助散列函数对数组这种数据结构进行扩展,利用的是数组支持按照下标随机访问元素的特性。散列表两个核心问题是散列函数设计和散列冲突解决。散列冲突有两种常用的解决方法,开放寻址法和链表法。散列函数设计的好坏决定了散列冲突的概率,也就决定散列表的性能。

    针对散列函数和散列冲突,今天只讲了一些基础的概念、方法,下一节会更贴近实战、更加深入探讨这两个问题。
    展开全文
  • 请先参考深入了解散列表什么是基于拉链法的散列表?对于散列算法的碰撞处理,一种直接的办法就是将大小为M的数组中的每个元素...基于拉链法的散列表查找方法:首先根据散列值找到对应的链表,然后沿着链表顺序查...

    c526dca62dca12d8408bc6681a408aa2.png

    请先参考深入了解散列表


    什么是基于拉链法的散列表?

    对于散列算法的碰撞处理,一种直接的办法就是将大小为M的数组中的每个元素指向一条链表,链表中的每个结点都存储了散列值为该元素的索引的键值对。

    这种方法称为拉链法,因为发生冲的元素都被存储在链表中。

    这个方法的基本思想就是选择足够大的M,使得所有的链表都尽可能的短以保证高效地查找

    基于拉链法的散列表的查找方法:

    1. 首先根据散列值找到对应的链表,
    2. 然后沿着链表顺序查找相应的键。

    拉链法的一种实现方法

    1. 使用原始的链表数据类型。
    2. 采用一般性的策略(但效率稍低),为M个元素分别构建符号表来保存散列到这里的键。

    拉链法中链的平均长度

    因为我们要用M条链表保存N个键,无论键在各个链表中的分布如何,链表的平均长度肯定为

    N/M

    例如,假设所有的键都落在了第一条链表上,所有链表的平均长度仍然

    (N+0+0+0+…+0)/M  = N/M。

    拉链法在实际情况中很有用,因为每条链表确实都大约有N/M个键值对。在一般情况中,我们能够依赖这种高效的查找和插入操作。

    3e3e34b1318721df7a0cab696fd8a89c.png

    代码实现

    public class SeparateChainingHashST<Key, Value> {
        private static final int INIT_CAPACITY = 4;
    
        private int n;                                // 键值对的总数
        private int m;                                // 散列表的大小
        private SequentialSearchST<Key, Value>[] st;  // 存放链表对象的数组
    
        public SeparateChainingHashST() {             //无参构造
            this(997);
        } 
        public SeparateChainingHashST(int m) {       //有参构造
            this.m = m;                              //创建M条链表
            st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[m];
            for (int i = 0; i < m; i++)
                st[i] = new SequentialSearchST<Key, Value>();
        } 
    
     private int hash(Key key) {                       //获得键的hash值
            return (key.hashCode() & 0x7fffffff) % m;
        } 
     public Value get(Key key) {                       //获取符号表中的指定键
            int i = hash(key);
            return st[i].get(key);
        } 
     public void put(Key key, Value val) {             //存放一个键值对到符号表
            if (val == null) {
                delete(key);
                return;
            }
            //如果列表的平均长度>= 2,则将表大小增加一倍
            if (n >= 10*m) resize(2*m);
            int i = hash(key);
            if (!st[i].contains(key)) n++;
            st[i].put(key, val);
        } 
     public Iterable<Key> keys() {                      //返回符号表中键的迭代器
            Queue<Key> queue = new Queue<Key>();
            for (int i = 0; i < m; i++) {
                for (Key key : st[i].keys())
                    queue.enqueue(key);
            }
            return queue;
        } 

    这段简单的符号表实现维护着一条链表的数组,用散列表来为每个键选择一条链表。简单起见,我们使用了SequentialSearchST。在创建st[]时需要进行类型转换,因为Java不允许泛型的数组。默认的构造函数会使用997条链表,因为对于较大的符号表,这种实现比SequentialSearchST大约快1000倍。当你能够预知需要的符号表大小时,这种短小精悍的方案能够得到不错的性能。

    一种更可靠的方案是动态调整链表数组的大小,这样无论在符号表中有多少键值对都能保证链表较短。

    散列表的大小

    在实现基于拉链法的散列表时,我们的目标是选择适当的数组大小M,既不会因为空链表而浪费大量内存,也不会因为链表太长而在查找上浪费大量时间。对于拉链法来说这并不是关键性的选择。

    如果存入的键多余预期,查找所需的时间只会比选择更大的数组稍长;如果少于预期,虽然有些空间浪费但查找会非常快。

    当内存不是很紧张时,可以选择一个足够大的M,使得查找所选要的时间变为常数;当内存紧张时,选择尽量大的M仍然能够将性能提高M倍。

    删除操作

    要删除一个键值对,先用散列值找到含有该键的SequentialSearchST对象,然后调用该对象的delete()方法。

      public void delete(Key key) {
            if (key == null) throw new IllegalArgumentException("argument to delete() is null");
    
            int i = hash(key);
            if (st[i].contains(key)) n--;
            st[i].delete(key);
    
            // 如果列表的平均长度<= 2,则将表大小减半
            if (m > INIT_CAPACITY && n <= 2*m) resize(m/2);
        } 

    有序性相关操作

    散列最主要的目的在于均匀地将键散布开来,因此在计算散列后键的顺序信息就丢失了。如果你需要快速找到最大键或者最小键,或是查找某个范围内的键,散列表都不是合适的选择,因为这些操作的时间都是线性的。


    小小总结:

    基于拉链法的散列表的实现简单。在键的顺序并不重要的应用中。它可能是最快的(也是使用最广泛的)符号表实现。

    展开全文
  • 散列技术时记录的存储位置和它的关键字之间建立的一个确定对应的关系f,使得每个关键字key对应一个存储位置f(key),查找时根据这个对应的关系找到给定值key的映射f(key),若查找集合中存储这个记录,则必定在f(key)...
  • 什么是散列表散列表(hash table),我们平时叫它哈希表或者Hash 表,你肯定经常听到它。散列表是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以...
  • 一,散列表的基本概念直接将元素的储存位置和其关键字之间建立某种直接关系,那么在进行查找时,就无需做比较或做很少次的比较,按照这种关系直接由关键字找到相应的记录,这就是散列表查找法的思想。它通过对元素...
  • 散列表 散列表(Hash table,也叫哈希表)【也被称:散列映射、映射、字典和关联数组】,是根据键... 散列表应用的例子有很多,经常被用在大海捞针式的查找。 案例1,为了查找电话簿中某人的号码,可以创建一个按...
  • 这可能是这么多种数据结构中最有用的-----散列表-----散列表。一、什么是散列表超市中用到的条形码,每个码对应一个商品,扫一下马上就能知道商品的价格,查询速度O(1)。哪种数据结构能做到这样? 那只有散列表了...
  • 散列表( hash table)  学习散列表——最有用的基本数据结构之一。散列表用途广泛,本章将介绍其常见的用途。 学习散列表的内部机制:实现、冲突和散列函数。这将帮助你理解如何分析散列表的性能。散列表是一种...
  • 创建与输入数组相等长度的新数组,作为直接寻址表。两数之和的期望是Target,将Target依次减输入数组的元素,得到的值和直接寻址表比较,如果寻址表存在这个值则返回;如果不存在这个值则将输入数组中的元素插入寻址...
  • 引用自算法图解,作者[美] Aditya Bhargava 译袁国忠 特别备注:本书非原创,但...有顾客来买东西时,你得在一个本子中查找价格。如果本子的内容不是按字母顺序排列的,你可能为查找苹果(apple)的价格而浏览每一...
  • 前面说过,如果两个数据项被散列映射到同一个槽,需要一个系统化的方法在散列表中保存第二个数据项,这个过程被称为“解决冲突”。如果散列函数是完美的,那就不会有散列冲突,但实际情况是,完美散列函数常常并不...
  • 首先我们要明确哈希表中下标每一个位置都有可能存储一个关键字数据,所以我们要求的失败平均查找长度即为: 失败平均查找长度=每一个位置查找失败的次数相加/哈希表长 那么每一个位置在什么情况下算是查找失败呢? 在...
  • 散列表平均查找长度计算题

    千次阅读 多人点赞 2019-11-25 16:27:56
    现有长度为11且初始为空的散列表HT,散列函数是H(key) = key %7,采用线性探查(线性探测再散列)法解决冲突将关键字序列87,40,30, 6,11,22,98,20依次插入到HT后,HT查找失败平均查找长度是 A. 4 B.5.25 C.6 D....
  • 哈希表查找失败平均查找长度

    千次阅读 2019-10-09 18:02:18
    1. 散列表中已经含有之前插入的元素。 即表已经不空了,若为空的话再插入元素的时候查找空位置一次就可以找到。 2. 这个位置是散列函数函数可以散列到的位置,不一定是表的总长。 如:散列函数为H(key) = (keyx...
  • 01知识框架02知识点详解1散列表的相关概念①什么是散列表和散列函数?是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射...
  • 散列表的动态扩容解答+面试题一、散列表(哈希表、Hash 表)不同与之前我们介绍的线性表,所有的数据都是顺序存储,当我们需要在线性表中查找某一数据时,当线性表过长,需要查找的数据排序比较靠后的话,就需要花费...
  • 有关HashMap(哈希表)的部分理解:HashMap是一个散列表,存储的是键值对(key-value),能够快速地查找所需的对象(O(1)时间复杂度)。HashMap有两个影响其性能的参数:“初始容量”-哈希表在创建时的容量;...
  • Hash表也称散列表,也有直接译作哈希表,Hash表是一种特殊的数据结构,它同数组、链表以及二叉排序树等相比较有很明显的区别,它能够快速定位到想要查找的记录,而不是与表中存在的记录的关键字进行比较来进行查找。...
  • 题图Pid=68670770在最近的学习过程中,发现身边很多朋友对...散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,...
  • 散列表的ASL计算

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

    2020-07-22 19:08:59
    散列表 文章目录: 基本概念 Hash函数的构造方法 Hash的冲突处理办法 查找成功和失败的ASL 1.基本概念 ...2.常用Hash函数的构造方法 ...4.平均查找长度ASL 1.对于用开放定址法的Hash表求ASL: 1)ASL1:查找每个关键字
  • 查找总结

    2017-09-12 09:33:16
    1、线性查找法 2、二分查找 3、分块查找 4、散列表 常用的哈希函数 除留余数法 常用的解决冲突的方法 线性探测法、拉链法 ...查找成功时平均查找长度 ...查找失败平均查找长度
  • 最近学了数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时比较迷茫,不知道到底是怎么计算出来的。现在通过查阅资料终于知道如何计算了,所以记录下来以供以后查阅。 Question1: 将关键字序列...
  • 查找算法

    2019-10-08 16:35:59
    一、查找 ...散列结构:散列表Hash,性能分析,冲突处理,效率指标--平均查找长度,查找成功,查找失败 线性表顺序查找: typedef struct List{ ElemType *elem; int table_len;//表长 }SSTabl...
  • 数据结构之查找

    2020-07-20 22:37:12
    ASL:即平均查找长度(平均比较次数),是衡量一个查找算法效率优劣的标准 1.顺序查找 顺序表的查找分为有序查找和无序查找 无序查找 1.无序查找的代码实现 ①通过添加哨兵的方式 2.查找成功和失败的ASL 注意...

空空如也

空空如也

1 2 3
收藏数 43
精华内容 17
关键字:

散列表查找失败平均查找长度