Table of Contents

  1. 第五章 散列表
    1. 散列表适合用于
    2. 经验
  2. 小结
  3. 第六章 广度优先搜索


第五章 散列表

  • 散列函数“将输入映射到数字”
  • 散列函数总是将同样的输入映射到相同的索引
  • 散列函数将不同的输入映射到不同的索引
  • 散列函数知道数组有多大,只返回有效的索引
  • 而散列表也使用数组来存储数据,因此其获取元素的速度与数组一样快。

散列表适合用于

  • 模拟映射关系;
  • 防止重复;
  • 缓存/记住数据,以免服务器再通过处理来生成它们。

  • 如果两个键映射到了同一个位置,就在这个位置储存一个链表

经验

  • 散列函数很重要。前面的散列函数将所有的键都映射到一个位置,而最理想的情况是,
    散列函数将键均匀地映射到散列表的不同位置。
  • 如果散列表存储的链表很长,散列表的速度将急剧下降。然而,如果使用的散列函数很
    好,这些链表就不会很长!

  • 在最糟情况下,散列表所有操作的运行时间都为O(n)——线性时间

  • 在平均情况下,散列表的查找(获取给定索引处的值)速度与数组一样快,而插入和删除速
    度与链表一样快,因此它兼具两者的优点!但在最糟情况下,散列表的各种操作的速度都很慢。

  • 因此,在使用散列表时,避开最糟情况至关重要。为此,需要避免冲突。而要避免冲突,需要有1.较低的填装因子2.良好的散列函数。

  • 填装因子大于1意味着商品数量超过了数组的位置数。一旦填装因子开始增大,你就需要在散列表中添加位置,这被称为调整长度(resizing)。

  • 一个不错的经验规则是:一旦填装因子大于0.7,就调整散列表的长度。

  • 什么样的散列函数是良好的呢?你根本不用操心——天塌下来有高个子顶着。如果你好奇,
    可研究一下SHA函数

小结

  • 你几乎根本不用自己去实现散列表,因为你使用的编程语言提供了散列表实现。你可使用
    Python提供的散列表,并假定能够获得平均情况下的性能:常量时间。

  • 散列表是一种功能强大的数据结构,其操作速度快,还能让你以不同的方式建立数据模型。
    你可能很快会发现自己经常在使用它。

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

第六章 广度优先搜索

  • 广度优先搜索指出是否有从A到B的路径。
  • 如果有,广度优先搜索将找出最短路径。
  • 面临类似于寻找最短路径的问题时,可尝试使用图来建立模型,再使用广度优先搜索来
    解决问题。
  • 有向图中的边为箭头,箭头的方向指定了关系的方向,例如,rama→adit表示rama欠adit钱。
  • 无向图中的边不带箭头,其中的关系是双向的,例如,ross - rachel表示“ross与rachel约
    会,而rachel也与ross约会”。
  • 队列是先进先出(FIFO)的。
  • 栈是后进先出(LIFO)的。
  • 你需要按加入顺序检查搜索列表中的人,否则找到的就不是最短路径,因此搜索列表必
    须是队列。
  • 对于检查过的人,务必不要再去检查,否则可能导致无限循环。