算法——散列表

散列表也是一种有用的基本数据结构，本文主要关于散列表的内部机制：实现、冲突和散列函数。

为什么会需要散列表？可以考虑有关查找的情况。

如果是简单查找，时间为O(n)，如果用二分查找，时间为O(log n)。但是如果能够达到每个查找的时间为O(1)的话，散列函数就有了用武之地。

散列函数

散列函数就是将输入映射到数字。散列函数必须满足一些要求。

散列函数必须是一致的，将不同的输入映射到不同的数字。

实际上散列函数能够准备指出相应的存储位置，根本不用查找。具体原因在于：

散列函数总是将同样的输入映射到相同的索引，散列函数将不同的输入映射到不同的索引。散列函数知道数组有多大，并且只会返回有效的索引。

结合散列函数和数组就可以创建一种称为散列表的数据结构。

Python提供的散列表实现为字典dict。散列表由键和值组成。

散列表适合用在模拟映射关系，防止重复，缓存数据等情况下。

冲突

前面说散列函数总是将不同的键映射到数组的不同位置。但是假如两个键分配的位置相同，就会产生冲突。那么在同一个位置就会按照链表的方式存储。

所以散列函数很重要。最理想的情况是将散列函数将键均匀的映射到散列表的不同位置。

如果散列表存储的链表很长，散列表的性能将急剧下降。所以如果使用的散列函数很好，链表就不会很长。

性能

在平均情况下，散列表执行各种操作的时间都是O(1)，实际上指的是不论散列表多大，各种操作的时间都是相同的。

但是在最糟的情况下，散列表所有操作的时间为O(n)。因此在使用散列表时需要避开最糟的情况。

避开最糟的情况有两种：较低的填装因子，良好的散列函数。

填装因子

填装因子就是： 。

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

调整散列表长度的操作需要很长时间，但是平均而言，即便考虑到调整长度所需的时间，散列表操作所需的时间也是O(1)。

良好的散列函数

良好的散列函数让数组中的值呈均匀分布。糟糕的散列函数让值扎堆，导致大量的冲突。

而什么事良好的散列函数呢？SHA散列算法就是一种常见的散列函数。

散列表小结

散列表是一种功能强大的数据结构，其操作速度快，还能让你以不同的方式建立数据模型。

你可以结合散列函数和数组来创建散列表。

冲突很糟糕，你应使用可以最大限度减少冲突的散列函数。

散列表的查找、插入和删除速度都非常快。

散列表适合用于模拟映射关系。

一旦填装因子超过0.7，就该调整散列表的长度。

散列表可用于缓存数据（例如，在Web服务器上）。

散列表非常适合用于防止重复。