本章开头是假设你在杂货店工作。你想打造一个让你能够迅速获悉商品价格的工具，而散列表的速度确实很快。

在平均情况下，散列表执行各种操作的时间都为O(1)。 O(1)被称为常量时间。你以前没有见过常量时间，它并不意味着马上，而是说不管散列表多大，所需的时间都相同。例如，你知道的，简单查找的运行时间为线性时间。

二分查找的速度更快，所需时间为对数时间。

在散列表中查找所花费的时间为常量时间。

一条水平线，看到了吧？这意味着无论散列表包含一个元素还是10亿个元素，从其中获取数据所需的时间都相同。实际上，你以前见过常量时间——从数组中获取一个元素所需的时间就是固定的：不管数组多大，从中获取一个元素所需的时间都是相同的。在平均情况下，散列表的速度确实很快。

在最糟情况下，散列表所有操作的运行时间都为O(n)——线性时间，这真的很慢。我们来将散列表同数组和链表比较一下。

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

因此，在使用散列表时，避开最糟情况至关重要。为此，需要避免冲突。而要避免冲突，需要有：

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

说 明

接下来的内容并非必读的，我将讨论如何实现散列表，但你根本就不需要这样做。不管你使用的是哪种编程语言，其中都内置了散列表实现。你可使用内置的散列表，并假定其性能良好。下面带你去看看幕后的情况。