第4章-散列表

散列表

输入一个值，通过散列函数输出一个数，就像数组一样。

散列表（hash table）：在python中提供了散列表的实现：字典（dict）。

散列表是由键值对组成的，键Key不允许重复

冲突

大多数编程语言都提供了散列表的实现，不用考虑他们是怎么实现的，但你依然需要考虑性能，明白散列表的性能，就得先搞清楚什么是冲突：

比如有一个二十六位的数组，第一个位置存放a开头的，第二个位置存放b开头的

这样apple自然存放在一位置，banana自然存放在b，如果又来一个ayocados呢，也应该存放在一位置，就会覆盖掉apple，这样是不行的。

冲突产生了。为了避免，解决最简单的方式如：如果两个键映射到同一个位置，在这个位置上存储一个链表就行。

apple和avocado映射到了同一个位置

性能

散列表执行各种操作的时间都是O(1)，O(1)被称为常量时间，它并不意味着马上，而是说不管散列表多大，所需要的时间都是相同的。

在最糟糕的情况下，散列表所有操作的运行时间都是O(n)：线性时间，这很慢，将散列表和数组链表比较一下：

在平均情况下，散列表的查询（获取索引值）速度和数组一样快，而插入和删除速度和链表一样快，因此它兼得了两个的优点！

但在最糟糕的情况下，散列表的各种操作的速度都很慢。因此需要避免冲突：

• 较低的填装因子（位置足够多）
• 良好的散列函数（避免出现链表）