欢迎访问我的博客：http://wangnan.tech

第五章 散列表

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

散列表适合用于

• 模拟映射关系；

• 防止重复；

• 缓存/记住数据，以免服务器再通过处理来生成它们。

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

经验

• 散列函数很重要。前面的散列函数将所有的键都映射到一个位置，而最理想的情况是，
  散列函数将键均匀地映射到散列表的不同位置。

• 如果散列表存储的链表很长，散列表的速度将急剧下降。然而，如果使用的散列函数很
  好，这些链表就不会很长！

• 在最糟情况下，散列表所有操作的运行时间都为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）的。
• 你需要按加入顺序检查搜索列表中的人，否则找到的就不是最短路径，因此搜索列表必
  须是队列。
• 对于检查过的人，务必不要再去检查，否则可能导致无限循环。