散列表

• 散列表——最有用的基本数据结构之一。
• 散列表实现为字典，你可使用函数dict来创建散列表。

散列表适合用于：

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

散列函数

散列函数是这样的函数，即无论你给它什么数据，它都还你一个数字。

性能

良好的散列函数让数组中的值呈均匀分布。

糟糕的散列函数让值扎堆，导致大量的冲突。

在平均情况下，散列表的查找（获取给定索引处的值）速度与数组一样快，而插入和删除速度与链表一样快，因此它兼具两者的优点！但在最糟情况下，散列表的各种操作的速度都很慢。 因此，在使用散列表时，避开最糟情况至关重要。为此，需要避免冲突。而要避免冲突，需要有：

• 较低的填装因子；
• 良好的散列函数。
  

填装因子

散列表使用数组来存储数据，因此你需要计算数组中被占用的位置数。例如，下述散列表的 填装因子为2/5，即0.4。

填装因子越低，发生冲突的可能性越小， 散列表的性能越高。一个不错的经验规则是：一旦填装因子大于0.7，就调整散列表的长度。

小结

不用自己去实现散列表，因为你使用的编程语言提供了散列表实现。并假定能够获得平均情况下的性能：常量时间。

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