侧边栏壁纸
  • 累计撰写 247 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

散列函数设计与散列冲突处理

kaixindeken
2021-04-21 / 0 评论 / 0 点赞 / 89 阅读 / 1,456 字

在不考虑哈希冲突的情况下,散列表查找、删除、插入的时间复杂度都是 O(1),非常高效。

散列函数设计

要减少哈希冲突,提高散列表操作效率,设计一个优秀的散列函数至关重要,我们平时经常使用的 md5 函数就是一个散列函数,但是其实还有其他很多自定义的设计实现,要根据不同场景,设计不同的散列函数来减少散列冲突,而且散列函数本身也要很简单,否则执行散列函数本身会成为散列表的瓶颈。我们日常很少会自己去设计散列函数,但是做一些简单的了解还是有必要的。

通常有以下几种散列函数构造方法:

  • 直接定址法:即 f(key) = a*key + b,f 表示散列函数,a、b 是常量,key 是键值
  • 数字分析法:即对数字做左移、右移、反转等操作获取散列值
  • 除数留余法:即 f(key) = key % p,p 表示容器数量,这种方式通常用在将数据存放到指定容器中,如何决定哪个数据放到哪个容器,比如分表后插入数据如何处理(此时 p 表示拆分后数据表的数量),分布式 Redis 如何存放数据(此时 p 表示几台 Redis 服务器)
  • 随机数法:即 f(key) = random(key),比如负载均衡的 random 机制

以上只是一些比较场景的散列函数设计思路,还有很多其他的设计方法,这里就不一一列举了。

散列冲突处理

设计再好的散列函数也不能完全避免散列冲突,我们只能优化自己的实现让散列冲突尽可能少出现罢了,如果出现了散列冲突,该如何处理呢?下面给出一些思路:

  • 开放寻址法:该方法又可以细分为三种 —— 线性寻址、二次探测、随机探测。线性寻址表示出现散列冲突之后,就去寻找下一个空的散列地址;线性寻址步长是1,二次探测步长是线性寻址步长的2次方,其它逻辑一样;同理,随机探测每次步长随机。不管哪种探测方法,散列表中空闲位置不多的时候,散列冲突的概率就会提高,为了保证操作效率,我们会尽可能保证散列表中有一定比例的空闲槽位,我们用装载因子来表示空位的多少,装载因子=填入元素/散列表长度,装载因子越大,表明空闲位置越少,冲突越多,散列表性能降低。
  • 再散列函数法:发生散列冲突后,换一个散列函数计算散列值
  • 链地址法:发生散列冲突后,将对应数据链接到该散列值映射的上一个值之后,即将散列值相同的元素放到相同槽位对应的链表中。链地址法即使在散列冲突很多的情况下,也可以保证将所有数据存储到散列表中,但是也引入了遍历单链表带来性能损耗。

介绍完以上内容之后,想必你对如何打造工业级散列表已经心中有数。主要考虑因素包含以下几个方面:

  • 散列函数设置合理,不能太过复杂,成为性能瓶颈;
  • 设置装载因子阈值,支持动态扩容,装载因子阈值设置要充分权衡时间、空间复杂度;
  • 如果一次性扩容耗时长,可采取分批扩容的策略,达到阈值后只申请空间,不搬移数据,以后每插入一条数据,搬移一个旧数据,最后逐步完成搬移,期间为了兼容新老散列表查询,可以先查新表,再查老表;
  • 散列冲突解决办法:开放寻址法在数据量较小、装载因子小的时候(小于1)选用;链表法可以容忍装载因子大于1,适合存储大对象、大数据量的散列表,且更加灵活,支持更多优化策略。

补充一张链地址法处理散列(哈希)冲突的图示:

1.png

0

评论区