设计哈希表
Varsion

哈希列表的查询效率并不能笼统地说成是 O(1)。它跟散列函数、装载因子、散列冲突等都有关系。如果散列函数设计得不好,或者装载因子过高,都可能导致散列冲突发生的概率升高,查询效率下降。

在极端情况下,有些恶意的攻击者,还有可能通过精心构造的数据,使得所有的数据经过散列函数之后,都散列到同一个槽里。如果我们使用的是基于链表的冲突解决方法,那这个时候,散列表就会退化为链表,查询的时间复杂度就从 O(1) 急剧退化为 O(n)。

如何设计散列函数

散列函数的设计不能太复杂

过于复杂的散列函数,会消耗很多计算时间,会间接地影响到散列表的性能。

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

如何解决装载因子过大

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

不仅插入数据的过程要多次寻址或者拉很长的链,查找的过程也会因此变得很慢。

对于动态散列表来说,数据集合是频繁变动的,事先无法预估将要加入的数据个数,所以也无法事先申请一个足够大的散列表。

随着数据慢慢加入,装载因子就会慢慢变大。当装载因子大到一定程度之后,散列冲突就会变得不可接受、不可避免。

针对哈希表,可以进行动态扩容,重新申请一个更大的空间,并将数据搬移到新的哈希表中。

假设每次扩容我们都申请一个原来散列表大小两倍的空间。如果原来散列表的装载因子是 0.8,那经过扩容之后,新散列表的装载因子就下降为原来的一半,变成了 0.4。

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

对于动态散列表,随着数据的删除,散列表中的数据会越来越少,空闲空间会越来越多。如果我们对空间消耗非常敏感,我们可以在装载因子小于某个值之后,启动动态缩容。当然,如果更加在意执行效率,能够容忍多消耗一点内存空间,那就可以不用费劲来缩容了。

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

选择冲突的解决方法

两种主要的散列冲突的解决办法,开放寻址法和链表法。

开放寻址法

开放寻址法不像链表法,需要拉很多链表。哈希中的数据都存储在数组中,可以有效地利用 CPU 缓存加快查询速度。同时,序列化起来比较简单。

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

链表法

链表法比起开放寻址法,对大装载因子的容忍度更高。开放寻址法只能适用装载因子小于 1 的情况。接近 1 时,就可能会有大量的散列冲突,导致大量的探测、再散列等,性能会下降很多。

但是对于链表法来说,只要哈希函数的值随机均匀,即便装载因子变成 10,也就是链表的长度变长了而已,虽然查找效率有所下降,但是比起顺序查找还是快很多。

于链表的散列冲突处理方法比较适合存储大对象、大数据量的哈希表。


  • Post title:设计哈希表
  • Post author:Varsion
  • Create time:2020-08-16 20:54:31
  • Post link:https://blog.varsion.cn/post/494cd93.html
  • Copyright Notice:All articles in this blog are licensed under BY-NC-SA unless stating additionally.
Comments