算法图解笔记 - 散列表

散列表

  • 运行时间 O(1)
  • 模拟映射关系
  • 防止重复
  • 缓存/记住数据,以免服务器再通知处理来生成它们

操作散列表平均情况散列表最糟情况数组链表 查找 O(1) O(n) O(1) O(n) 插入 O(1) O(n) O(n) O(1) 删除 O(1) O(n) O(n) O(1) 避免冲突的两个条件:

  • 较低的填装因子
    • 散列表包含的元素数/位置总数
  • 良好的散列
    • 数组中的值呈均匀分布
    • 糟糕的散列函数让值扎堆,导致大量的冲突
    • 散列函数SHA

小结

  • 结合散列函数和数组来创建散列表
  • 冲突很糟糕,应该使用可以最大限度减少冲突的散列函数
  • 散列表的查找、插入和删除速度都非常快
  • 散列表适用于模拟隐射关系
  • 一旦填装因子超过0.7,就该调整散列表的长度
  • 散列表可用于缓存数据(例如,在Web服务器上)
  • 散列表算法图解笔记 - 快速排序

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券