[What]算法图解_散列表

查找速度优于 二分查找 的优秀算法,平均算法复杂度为 O(1)。

什么是散列表

散列函数就是一个输入对应到一个数值,当散列函数与数组结合就形成了 散列表

Python 中的 dict 类型就是一个散列表结构,可以快速查找。
使用步骤为:
1. 添加 [键] [值] 元素
2. 输入 [键] 而得到 [值]

散列函数必须满足一些要求:

  • 每次相同的输入都必须得到相同的数字
  • 不同的输入映射到不同的数字

散列表的应用

  • 查找
    • 输入名称获取电话号码
    • 输入网址转为IP地址
  • 防止重复
    • 根据姓名查找其是否已经投过票了,防止重复投票
  • 用作缓存
    • 浏览器将常常访问的数据缓存下来,以达到快速访问
    • 服务器根据不同用户缓存其对应的数据,以达到快速访问

冲突

冲突就是指散列表为不同的 [键] 分配了相同的 [值]。

这是由于 散列函数 设计不够优良而造成的。

性能

  散列表(平均情况) 散列表(最糟情况) 数组 链表
查找 O(1) O(n) O(1) O(n)
插入 O(1) O(n) O(n) O(1)
删除 O(1) O(n) O(n) O(1)

为了能够避免冲突,需要:

  • 较低的填装因子
  • 良好的散列函数

填装因子

填装因子 = 散列表包含的元素数 / 位置总数

当填装因子大于1时,就会有冲突,具有两种办法解决:

  • 增加数组长度
经验规则:一旦填装因子大于0.7,就调整散列表长度(不能频繁操作,否则将大大拖慢时间)
  • 将数组中存储链表地址,使用链表存储值,也就是做二维扩展

良好的散列函数

良好的散列函数让数组中的值呈均匀分布。

Last Updated 2018-10-14 日 19:32.
Render by hexo-renderer-org with Emacs 26.1 (Org mode 9.1.14)