注：本文如涉及到代码，均经过Python 3.7实际运行检验，保证其严谨性。
本文阅读时间约为3分钟。
前面介绍过顺序查找和二分查找。
当一组数据项的排列是无序时，我们就用顺序查找；当数据项是有序时，我们可以用二分查找法来降低算法复杂度，从顺序查找法的O(n)，降低到二分查找法的O(log n)，从而实现更高效的查找。
那么问题来了，我们能否进一步降低查找的算法复杂度呢？
答案是，能。
现在，我们进一步构造一个新的数据结构，能使得查找算法的复杂度降低到O(1)，也就是常数级别。实现的这种概念就是散列(hashing)。
散列(hashing)
要使得查找的次数降低到常数级别，先要对数据项所处的位置有更多的先验知识——如果事先能知道要找的数据项应该出现在数据集里的什么位置，就可以直接到那个位置查看数据项是否存在即可。
由数据项的值来确定其存放位置，如何能做到这一点呢？
散列表(hash table，又称哈希表)就是我们的答案。
散列表，是一种数据集，其中数据项的存储方式尤其有利于将来快速的查找定位。
散列表中的每一个存储位置，称为槽(slot)，是用来保存数据项的。每个槽都有唯一的名称。
实现从数据项到存储槽名称转换的，称为散列函数(hash function)。
一个散列的示例
下面示例中，散列函数接受数据项作为参数，返回整数值0~10，表示数据项存储的槽号（名称）。
假设我们有这么一些数据项：
<code>54
,
26
,
93
,
17
,
77
,
31
/<code>
有一种常用的散列方法“求余数”，将数据项除以散列表的大小，得到的余数作为槽号。
实际上“求余数”方法会以不同形式出现在所有的散列函数里。
因为散列函数返回的槽号必须在散列表大小范围之内，所以一般会对散列表大小求余。
在我们的这个示例中，因为槽号的下标是0~10，一共11个槽，所以散列函数是最简单的求余：
<code>h(item)
=
item
%
11
/<code>
按照散列函数h(item)，为每个数据项计算出存放的位置之后，就可以将数据项存入相应的槽中。如下表所示：
<code>Item
Hash
Value
54
10
26
4
93
5
17
6
77
0
31
9
/<code>
可以看到，示例中的6个数据项各自占据了1个槽，也就是6个数据项一共占据了11个槽中的6个。这种槽被数据项占据的比例称为散列表的“负载因子”。本例中的负载因子是6/11。
我们把数据项都保存在散列表中之后，查找就非常简单了。
如果要查找某个数据项是否存在于表中，我们需要使用同一个散列函数，对查找项进行计算，测试下返回的槽号所对应的槽中是否有数据项即可。
如此，我们便实现了复杂度为O(1)的查找算法。
散列表查找方法的劣势
上述例子虽然实现了O(1)复杂度的查找算法，但是，我们注意到，示例比较特殊，6个数据项占据了6个槽，也就是每个槽只有1个独一无二的数据项。
那么问题来了，如果再增加1个数据项，比如44，h(44)=0，就造成了#0槽有两个数据项，7个数据项只占据了6个槽的情况，即有一个槽有2个不同的数据项。这种情况称为冲突（collision）。
关于冲突的情况，我们后面再讨论其解决方案。
To be continued.
