精华内容
下载资源
问答
  • 最近复习了下数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时比较迷茫,不知道到底是怎么计算出来的。现在通过查阅资料终于知道如何计算了,所以记录下来以供以后查阅。  下面下2010年...

    最近复习了下数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时比较迷茫,不知道到底是怎么计算出来的。现在通过查阅资料终于知道如何计算了,所以记录下来以供以后查阅。

       下面看下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。  

            等概率情况下查找不成功的平均查找长度:

            接下来讨论不成功的情况, 看表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(注意不是地址9,因为初始只可能在0~6之间,因此循环回去)的距离为5,因此查找不成功的次数为5.

            地址6,到第一个关键为空的地址2(注意不是地址9,因为初始只可能在0~6之间,因此循环回去)的距离为4,因此查找不成功的次数为4.

            因此查找不成功的次数表如下表所示

    Key 7 8 30 11 18 9 14
    Count 3 2 1 2 1 5 4

    (表4)

           所以ASLunsuccess= (3+2+1+2+1+5+4)/ 7 = 18/7。

     

           以上表述如有不对的地方,欢迎大家指正。谢谢。。。

    展开全文
  • 最近复习了下数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时比较迷茫,不知道到底是怎么计算出来的。现在通过查阅资料终于知道如何计算了,所以记录下来以供以后查阅。  下面下2010年...
    哈希表等概率情况下查找成功和查找不成功的平均查找长度的计算


    最近复习了下数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时比较迷茫,不知道到底是怎么计算出来的。现在通过查阅资料终于知道如何计算了,所以记录下来以供以后查阅。
       下面看下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。  
            等概率情况下查找不成功的平均查找长度:
            接下来讨论不成功的情况, 看表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(注意不是地址9,因为初始只可能在0~6之间,因此循环回去)的距离为5,因此查找不成功的次数为5.
            地址6,到第一个关键为空的地址2(注意不是地址9,因为初始只可能在0~6之间,因此循环回去)的距离为4,因此查找不成功的次数为4.
            因此查找不成功的次数表如下表所示
    Key 7 8 30 11 18 9 14
    Count 3 2 1 2 1 5 4
    (表4)

           所以ASLunsuccess= (3+2+1+2+1+5+4)/ 7 = 18/7。

    展开全文
  • 最近复习数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时不太理解,不知道到底是怎么计算出来的。了几篇博客后终于知道如何计算了,总结如下。 例题: 将关键字序列(7、8、30、11、...

    最近复习数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时不太理解,不知道到底是怎么计算出来的。看了几篇博客后终于知道如何计算了,总结如下。

     

    例题:

    将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组,散列函数为: H(key) = (keyx3) MOD 7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。

    (1)请画出所构造的散列表。

    (2)分别计算等概率情况下查找成功和查找不成功的平均查找长度。

     

    (1)首先明确一个概念:装载因子。装载因子是指所有关键子填充哈希表后饱和的程度,它等于 填入表中的关键字总数/哈希表的长度

    根据题意,我们可以确定哈希表的长度为 L = 7/0.7 = 10;因此此题需要构建的哈希表是下标为0~9的一维数组。

     

    这里采用线性探测再散列法处理冲突,构造散列表。

           H(7) = (7x3) MOD 7 = 0,地址为0,因此放到散列表的数组下表为0的位置,这个位置上没有关键字,因此没有冲突可以直接填入;

           H(8) = (8x3) MOD 7 = 3,地址是3,因此放到散列表的数组下表为3的位置,这个位置上没有关键字,因此没有冲突可以直接填入;

           H(30) = (30x3) MOD 7 = 6,地址是6,因此放到散列表的数组下表为6的位置,这个位置上没有关键字,因此没有冲突可以直接填入;

           H(11) = (11x3) MOD 7 = 5,地址是5,因此放到散列表的数组下表为5的位置,这个位置上没有关键字,因此没有冲突可以直接填入;

           H(18) = (18x3) MOD 7 = 5,地址是5,因此放到散列表的数组下表为5的位置,但这个位置上已经有关键字11,遇到了冲突,此时我们根据线性探测再散列法来处理这个冲突,探测下一个位置6,6这个位置上已经存在关键字30则继续增加1,因此现在的新地址应为7,位置7上没有关键字,放入即可,到此冲突已经解决;

           H(9) = (9x3) MOD 7 = 6,地址是6,因此放到散列表的数组下表为6的位置,但这个位置上已经有关键字30,遇到了冲突,探测下一个位置7,7这个位置上已经存在关键字18则继续增加1,因此现在的新地址应为8,位置8上没有关键字,放入即可;   

           H(14) = (14x3) MOD 7 = 0,地址是0,因此放到散列表的数组下表为0的位置,但这个位置上已经有关键字7,遇到了冲突,探测下一个位置1,位置1上没有关键字,放入即可;   

           到这一步所有关键字均已填入,散列表已经构造完成,如下表所示。

    地址 0 1 2 3 4 5 6 7 8 9
    关键字 7 14   8   11 30 18 9  

     

    (2)等概率情况下查找成功平均查找长度:

            这一问可以根据第一问的构造过程求解:

            key7 一次就填入了表中,因此查找次数为1,同理8, 30, 11查找次数均为1;

            key18 进行了三次探测操作,探测位置分别是5,6,7 ,因此查找次数为3;

            key9 也是三次;

            key14 进行了两次探测,因此查找次数为2。次数如下表所示:

    地址 0 1 2 3 4 5 6 7 8 9
    关键字 7 14   8   11 30 18 9

     

    成功次数 1 2   1   1 1 3 3  

       

            所以ASLsuccess= (1+2+1+1+1+3+3)/ 7 = 12/7。  

           

            接下来讨论不成功的情况,计算查找不成功的次数就直接找关键字到下一个地址关键字为空的距离即可,但根据散列函数地址为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,到第三个关键字为空的地址9的距离为5,因此查找不成功的次数为5;

            地址6,到第三个关键字为空的地址9的距离为4,因此查找不成功的次数为4;

            注意地址7、8、9不用看。

            因此查找不成功的次数表如下表所示:

    地址 0 1 2 3 4 5 6 7 8 9
    关键字 7 14   8   11 30 18 9

     

    失败次数 3 2 1 2 1 5 4      


           所以ASLunsuccess= (3+2+1+2+1+5+4)/ 7 = 18/7。

    展开全文
  • 笔者在读研刚开始的时候,偶尔面经,有...其核心就是哈希函数和哈希表的应用! 哈希函数 哈希函数又称为散列函数,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输...

    文章和资源同步更新至微信公众号:算法工程师之路

    笔者在读研刚开始的时候,偶尔看面经,有这样一个问题:只用2GB内存在20亿个整数中找到出现次数最多的数,当时的我一脸懵逼,怎么去思考,20亿个数?What The Fuck! 但是,看完今天的文章,你或许就会觉得原来也不过如此啊!其核心就是哈希函数和哈希表的应用!

    哈希函数

    哈希函数又称为散列函数,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。假设输出值域为S,哈希函数的性质如下:

    1. 典型的哈希函数都有无限的输入值域
    2. 当哈希函数输入一致时,输出必相同
    3. 当哈希函数传入不同的输入值时,返回值可能一样,也可能不一样,由于输入域远大于值域
    4. (重要)很多的不同输入所得的输出值会均匀的分布在S上(但不是绝对均匀)

    最后一个性质对于一个优秀的哈希函数是非常重要的,并且这种均匀与数据的输入规律无关。比如“aa1”、"aa2"经过hash后可能结果会相差很多,当一个哈希函数的输出在S中是均匀的,那么我们将输出值对m取余(%m),就会将不定长输入映射到0~m-1空间中,并且在这个空间也保持均匀分布!哈希表就是这么做的,一会再说!哈希函数还有以下特点:

    1. 免碰撞:即不会出现输入 x≠y ,但是H(x)=H(y) 的情况,其实这个特点在理论上并不成立,比如目前比特币使用的 SHA256 算法,会有 22562^{256} 种输出,如果我们进行 22562^{256} + 1 次输入,那么必然会产生一次碰撞,事实上,通过 理论证明 ,通过 21302^{130} 次输入就会有99%的可能性发生一次碰撞,不过即使如此,即便是人类制造的所有计算机自宇宙诞生开始一直运算到今天,发生一次碰撞的几率也是极其微小的。
    2. 隐匿性:也就是说,对于一个给定的输出结果 H(x) ,想要逆推出输入 x ,在计算上是不可能的。如果想要得到 H(x) 的可能的原输入,不存在比穷举更好的方法。

    常见的哈希函数有:SHA1、MD5、SHA2等
    哈希函数映射

    哈希表

    哈希表就是利用哈希函数,可以根据关键码而直接进行访问的数据结构,也就是将关键码(Key value)通过哈希函数映射到表中的一个位置来进行访问。由于是直接访问,所以对于哈希表的元素理论上的增删改查时间复杂度都是O(1)。
    在这里插入图片描述
    而计算散列地址的方法有很多种,通常我们使用的是除留余数法,也就是说使用哈希函数对关键字得到的输出值对散列表长度取余得到的余数即为散列地址。

    哈希冲突

    由于我们的输入长度和范围是任意的,但是经过哈希函数后的输出值域是固定的,所以必然会产生冲突。如上图的buckets152(红色区域)就相当于发生冲突!处理冲突的方法有:

    • 开放地址法
    • 再散列法
    • 公共溢出法
    • 拉链法(经典、重点)
      我们来说下拉链法,也如上图所示,拉链法的思路很简单,就是当发生哈希冲突后,会在当前地址区域建立一个链表,将冲突目标添加到链表中去。这种方式也不太好,当冲突发生过多时,链表的查找方式效率也就不是很高了!
      因此对于JAVA中(C++标准中没有hashmap,只有第三方的),hashmap的实现也是类似,但是有一点改进,也就是如果发生冲突,将冲突对象添加到链表,假设冲突个数达到了8次,那么就会使用红黑树来代替链表,以加快查找速度。冲突个数少时,没有必要使用红黑树

    C++中的hash_map

    c++的hash_map和map的用法很类似,但一定要区别,map和hash_map虽然都是key-value形式,但是map的底层是红黑树,而hash_map的底层是hash表!
    如果在Linux下使用hash_map,一定要加上一个__gnu_cxx的命名空间声明!

    #include<iostream>
    #include<hash_map>
    
    using namespace __gnu_cxx;    // Linux下使用时,需要加上这句话才可以使用hash_map.
    
    using namespace std;
    
    int main(int args, char** argv){
        hash_map<int, string>* has = new hash_map<int, string>;
        has->insert(make_pair(32, "zhang"));
        has->insert({0, "teddy"});     // 两种插入元素的方法
    
        auto res = has->find(0);
        auto res2 = has->find(32);
        cout << res->second << endl;
        cout << res2->second << endl;
    
        return 0;
    }
    

    题目:2G内存下在20亿数据中找到出现次数最多的数

    首先我们确定value的范围,如果一个数出现了20亿次,那么value就为20亿次。因此我们使用32位的正整型,也就是4B的空间,同理key也是4B的空间,因此一条记录(Entry)需要8B的空间,当记录为20亿个时,需要至少16GB的内存。
    在极端最差的状态,20亿个数都不相同,那么哈希表中可能会有20亿条记录,这样的话显然内存不足,因此一次性统计20个数风险很大。
    解决方案:将包含有20亿个数的大文件分成16个小文件,利用哈希函数,这样的话,同一个重复的数肯定不会分到不同的文件中去,并且,如果哈希函数足够好,那么这16个文件中不同的数也不会大于2亿(20 / 16)。然后我们在这16个文件中依次统计就可以了,最后进行汇总得到重复数最多的数。当然如果使用分布式系统,那么可以利用哈希函数将这些数据分配到不同的电脑上去!

    资源分享

    如果想要看更多精彩内容,请关注我的个人公众号 (算法工程师之路)希望大家多多支持哦~

    公众号简介:分享算法工程师必备技能,谈谈那些有深度有意思的算法,主要范围:C++数据结构与算法/深度学习(CV),立志成为Offer收割机!坚持分享算法题目和解题思路(Day By Day)
    在这里插入图片描述

    展开全文
  • 给定一个未排序的整数数组,找出最长连续序列的长度。   说明 要求你的算法复杂度为O(n) 样例 ...给出数组[100, 4, 200, 1, 3, 2],这个最长的连续序列是 [1, 2, 3, 4]...不过我们还是先来看看排序的方案要怎么实...
  • Redis的最外层确实是通过hashtable实现的,在Redis里面,这个哈希表怎么实现呢?我们一下C语言的源码每个键值对都是一个dictEntry,通过指针指向key的存储结构和value的存储结构,而且next存储了指向下一个键值对...
  • 最近复习了下数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时比较迷茫,不知道到底是怎么计算出来的。现在通过查阅资料终于知道如何计算了,所以记录下来以供以后查阅。 下面下2010年...
  • 哈希表:链表+数组, 链表上挂载的值对应着地址值,在堆里能找到这个值。 数组:查询快,增删慢。(详情参见数据结构与算法) 链表:查询慢,增删快。 结构图:根据每个对象的哈希值决定对应的存储位置–value%数组...
  • 散列表--线性探测法

    2018-05-08 09:19:00
    最近复习了下数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时比较迷茫,不知道到底是怎么计算出来的。现在通过查阅资料终于知道如何计算了,所以记录下来以供以后查阅。 下面下2010年...
  • (三)为什么哈希表的容量(数组长度)是2的整数次幂 (四)put操作的实现源码及设计思路 HashMap中put LinkedHashMap中put (五)get操作的实现源码及设计思路 HashMap中get LinkedHashMap中get (六)怎么进行扩容 ...
  • 面试记录

    2020-04-16 23:21:52
    腾讯 项目相关: ...要各种情况 如何查看报文长度?如何查看头部长度? 如何确定报文已经发送完毕?(粘包问题) 为什么用优先队列,先进先出不行吗?优先队列线程安全问题 ...红黑树查找时间复杂度,哈希表复...
  • JDK1.7版本中的HashMap

    2018-03-10 15:01:15
    以下讲解基于JDK1.7 HashMap底层是一个数组,...下面从put、get、remove这三个方法分析一下源代码,看看HashMap增删查改是怎么做的。 构造HashMap对象的时候做了初始化,指定默认的初始容量(数组长度)和...
  • 怎么判断是否符合条件,也就是窗口中最多的重复字符有几个,再加上k就是可以出现的最长字符串,可以用一个哈希表来记录窗口中最多的字符串,如果用HahMap的话,就可以用A到Z来表示各个key,value是出现次
  • java面试知识点(难)

    2020-12-26 14:07:06
    为什么长度大于8转换成红黑树?这个8怎么来的? HashMap内部数据结构是由数组+链表,红黑树实现的 HashMap初始化 new HashMap() 不传值时,默认大小是16,负载因子是0.75,如果传入初始大小k,初始化大小为大于k的2...
  • ITween插件

    2019-02-25 11:07:29
    这几个函数的不使用哈希表作为参数的时候没有区别,但是当引入哈希表的时候,movefrom和moveto可以根据一个vector3序列(path)进行运动,而moveadd和moveby只能点对点运动,moveby和moveadd这两个函数经过测试,我...
  • 哈希表 堆:最大堆 / 最小堆 树与图:最近公共祖先、并查集 字符串:前缀树(字典树) / 后缀树 数据结构与算法的总结 数据结构总览 链表专题 树专题 堆专题(上) 堆专题(下) 二分专题(上) 二分专题(下)...
  • 大话数据结构

    2018-12-14 16:02:18
    项目经理完代码后拍着桌子对他说:“你数据结构是怎么学的?” 1.3数据结构起源 4 1.4基本概念和术语 5 正所谓“巧妇难为无米之炊”,再强大的计算机,也要有“米”下锅才可以干活,否则就是一堆破铜烂铁。这个...
  • map不初始化长度和初始化长度的区别 map承载多大,大了怎么办 map的iterator是否安全?能不能一边delete一边遍历? 字符串不能改,那转成数组能改吗,怎么怎么判断一个数组是否已经排序 普通map如何不用锁解决...

空空如也

空空如也

1 2
收藏数 32
精华内容 12
关键字:

哈希表长度怎么看