算法图解笔记 - 散列表

• 散列表
  • 避免冲突的两个条件：
  • 小结

散列表

• 运行时间 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服务器上）
• 散列表算法图解笔记 - 快速排序