哈希表|散列表|hash表

  • A+
所属分类:算法与数据结构

原理

数组可以利用数组下标实现随机访问,时间复杂度为O(1),但数组下标只能是非负整数,对于key不是非负整数的数据,可以利用哈希函数,计算出散列值,作为数组下标,将数据存储在数组中对应下标的位置,即可实现随机访问。

问题

  1. 哈希函数的设计,要尽量使计算出的散列值随机均匀分布。
  2. 哈希值碰撞时的解决方法:开放寻址法、链表法

开放寻址法

插入元素时,当计算出的位置已经有元素占用了,则寻找新的位置,将其插入。线性探索:从当前位置向后寻找空位进行插入。查找元素时,除了根据计算出的散列值进行寻址外,还要比较key值,再确定是否为所需元素。

链表法

每一个散列表的位置都对应着一串链表,将数据插入到链表中,并且可以通过将链表设计成跳表、红黑树来提高查找同一散列值的元素的效率。

装载因子

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

装载因子越大,空闲位置越少,冲突越多。当装载因子过大时,需要进行对散列表动态扩容。动态扩容时,可以在到达阈值之后,多次,每次扩容一点来进行,避免一次性扩容,带来效率的急速下降。

应用

LRU缓存淘汰算法

散列表+双向链表实现,散列表用于快速查找,链表用于快速删除和插入

哈希表|散列表|hash表

Redis有序集合

散列表+跳表。跳表用于排序和按value进行查找。散列表用于按key查找value

Java LinkedHashMap

和LRU缓存淘汰算法实现方式相同。Linked指双向链表。

许龙涛

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: