Hash Table

已发布 2017-12-18 12:05:37

理想

如果所有的键都是小整数,我们可以用一个数组来实现无序的符号表。

概览

  • 散列函数:将键转化为数组的一个索引
  • 处理碰撞冲突
    • 拉链法
      • 选择大数组,使得相同索引值的链表尽可能的短
    • 开放地址散列表:使用大小为M的数组保存N个键值对,其中M>N
      • 线性探测法
        • 三种情况
          • 命中,键相同
          • 未命中,键为空
          • 继续查找,键和被查找的键不同
        • 有空位则插入
  • 概率论:概率论是数学分析的重大成果。
    • 利用概率论的经典结论来帮助我们选择适当的参数,来在时间和空间的权衡上作出选择。
    • 指标
      • 散列表的使用率 N/M
comments powered by Disqus