数据结构和算法之——散列表中

栏目: 编程工具 · 发布时间: 6年前

内容简介:散列函数设计的好坏,决定了散列冲突发生的概率,也直接决定了散列表的性能。那什么才是好的散列函数呢?首先,其次,

散列函数设计的好坏,决定了散列冲突发生的概率,也直接决定了散列表的性能。那什么才是好的散列函数呢?

首先, 散列函数的设计不能太复杂 。过于复杂的散列函数,势必会消耗很多计算时间,也就间接地影响到散列表的性能。

其次, 散列函数生成的值要尽可能随机并且均匀分布 。这样才能避免或者最小化散列冲突,而且即便出现冲突,散列在每个槽内的数据也比较平均,不会出现某一个槽内数据特别多的情况。

手机号码前面几位重复的可能性很大,但是后面几位就比较随机,我么可以取手机号的后四位数作为散列值;对运动会参赛成员统计成绩的时候,选手后两位的号码就可以作为散列值。这种散列函数的设计方法,我们一般叫作“数据分析法”。

在散列表上 实现 Word 中拼写检查功能时,我们可以这样设计:将单词中每个字母的 ASCII 值“进位”相加,然后再和散列表的大小求余、取模,作为散列值。比如,英文单词 nice,转化出来的散列值就是:

hash("nice")=(("n" - "a") *26*26*26 + ("i" - "a")*26*26 + ("c" - "a")*26+ ("e"-"a")) / 78978
复制代码

事实上,散列函数的设计方法还有很多,比如直接寻址法、平方取中法、折叠法、随机数法等。

2. 装载因子过大了怎么办?

装载因子越大,说明散列表中的元素越多,空闲位置越少,散列冲突的概率就越大。

针对散列表,当装载因子过大时,我们可以进行 动态扩容 ,重新申请一个更大的散列表,将数据搬移到这个新散列表中。

但是,针对散列表的扩容,数据搬移要复杂很多,因为散列表的大小变了,数据的存储位置也变了,所以我们需要散列函数重新计算每个数据的存储位置。

数据结构和算法之——散列表中

插入一个数据,最好情况下,不需要扩容,最好时间复杂度是 ,最坏情况下,启动扩容,我们需要重新申请内存空间,重新计算哈希位置,并且搬移数据,所以时间复杂度为 。用摊还分析法,均摊情况下,时间复杂度接近于最好情况,就是 。

实际上,对于动态散列表,随着数据的删除,散列表越来越小,我们还可以在装载因子小于某个值之后,启动动态缩容。

装载因子阈值的设定需要权衡时间、空间复杂度。如果内存空间不紧张,对执行效率要求很高,可以降低装载因子的阈值;相反,如果内存空间紧张,对执行效率要求又不高,可以增加装载因子的值,甚至可以大于 1。

3.如何避免低效地扩容?

我们刚刚分析到,大部分情况下,动态扩容的散列表插入数据都很快,但是在特殊情况下,当装载因子达到阈值时,需要先进行扩容,再插入数据 ,这时候,插入数据就会很慢,尤其是在数据量已经非常大的情况下。

因此,我们可以考虑 不要一次性把数据全部都搬移过去 。当装载因子达到阈值时,我们申请新的空间,但并不将老的数据搬移到新散列表中。当有新的数据要插入时,我们不仅将新数据插入到新散列表中,而且同时从老的散列表中拿出一个数据放到新散列表中。这样,经过多次插入操作后,我们就一点一点地完成了数据搬移,插入操作也变得更快了。

数据结构和算法之——散列表中

至于这期间的查询操作,我们先从新散列表中查找,如果没有找到,再去老的散列表中查找。

通过这样的均摊方法,任何情况下,插入一个数据的时间复杂度都为 。

4.如何选择冲突解决方法?

4.1. 开放寻址法

  • 优点
    • 数据都存储在数组中,可以有效地利用 CPU 缓存加快查询速度
    • 没有指针,序列化起来比较简单
  • 缺点
    • 删除数据需要特殊标记,比较麻烦
    • 冲突的代价更高,一般装载因子上限不能太大,更浪费内存

当数据量比较小、装载因子比较小的时候,适合用开放寻址法。

4.2. 链表法

  • 优点
    • 内存利用率比开放寻址法要高,链表结点可以在需要的时候再创建
    • 对大装载因子容忍度更高,只要散列函数的值随机均匀,即使装载因子变成 10,也就是链表的长度变长了而已
  • 缺点
    • 存储小对象需要额外的指针,比较耗内存,但对于大对象则可以忽略
    • 链表分散存储,无法利用 CPU 缓存

另外,我们还可以对链表法加以改造,将链表改造成其他更高效的动态数据结构,比如跳表、红黑树。这样,即使出现散列冲突,也可以保证查找的时间复杂度为 。

数据结构和算法之——散列表中

基于链表的散列冲突方法比较适合存储大对象、大数据量的散列表,而且,比起开放寻址法,它更加灵活,支持更多的优化策略。


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

The Mechanics of Web Handling

The Mechanics of Web Handling

David R. Roisum

This unique book covers many aspects of web handling for manufacturing, converting, and printing. The book is applicable to any web including paper, film, foil, nonwovens, and textiles. The Mech......一起来看看 《The Mechanics of Web Handling》 这本书的介绍吧!

随机密码生成器
随机密码生成器

多种字符组合密码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

html转js在线工具
html转js在线工具

html转js在线工具