当一组数据项乱序排列时，我们使用顺序查找；当数据项有序时，我们可以使用二分查找来降低算法的复杂度，从顺序查找法的O(n)降低到二分查找法的O(logn)，从而实现更高效的查找.那么问题来了，能否进一步降低搜索的算法复杂度呢？答案是肯定的。现在，我们进一步构造一个新的数据结构，可以将搜索算法的复杂度降低到O(1)，这是一个恒定的水平。实现的这个概念称为散列。散列（hashing）要将搜索的次数减少到一个恒定的水平，首先你必须对数据项的位置有更多的先验知识——如果你事先知道你要找的数据项应该出现在数据集的位置,可以直接到那个位置去查看数据项是否存在。如何通过数据项的值来确定其存储位置来做到这一点？哈希表（hashtable，又名哈希表）就是我们的答案。哈希表是一种数据集，其中数据项的存储方式特别有利于日后快速查找和定位。哈希表中的每个存储位置称为槽，用于保存数据项。每个插槽都有一个唯一的名称。从数据项到存储槽名称的转换称为哈希函数。哈希的一个例子在下面的例子中，哈希函数接受一个数据项作为参数，并返回一个从0到10的整数值，表示存储数据项的槽号（名称）。假设我们有一些数据项：54,26,93,17,77,31有一个常用的哈希方法“余数”，将数据项除以哈希表的大小，余数作为槽号.事实上，“余数”方法以不同的形式出现在所有的哈希函数中。因为哈希函数返回的槽号必须在哈希表大小的范围内，所以一般计算哈希表大小的余数。在我们的例子中，因为槽位号的下标是0~10，所以一共有11个槽位，所以哈希函数就是最简单的余数：h(item)=item%11根据哈希函数h(item)，在计算出每个数据项的存储位置后，就可以将该数据项存储在对应的槽中。如下表所示：ItemHashValue5410264935176770319可以看出，示例中的6个数据项各占1个slot，即6个数据项共占11个slot中的6个。数据项占用此类槽的比例称为哈希表的“负载因子”。本例中的负载系数为6/11。我们把数据项存入哈希表后，查找就很简单了。如果我们要查找某个数据项是否存在于表中，我们需要使用相同的哈希函数计算查找项，并测试返回的槽号对应的槽中是否存在数据项。这样，我们就实现了一个复杂度为O(1)的搜索算法。哈希表查找法的缺点虽然上面的例子实现了复杂度为O(1)的查找算法，但是我们注意到这个例子比较特殊，6个数据项占用6个槽位，即每个槽位只有一个唯一的数据项。那么问题来了，如果再增加一个数据项，比如44，h(44)=0，会导致#0slot有两个数据项，7个数据项只占6个slot，也就是Aslot有2个不同的数据项。这种情况称为碰撞。关于冲突的情况，我们稍后会讨论它的解决方案。本文仅供学习，侵删。学习Python的路上肯定会遇到困难，不要慌张，我这里有一套学习资料，包括40+电子书，800+教学视频，涉及Python基础、爬虫、框架、数据分析、机学习等等，别怕你学不会！https://shimo.im/docs/JWCghr8...《Python学习资料》关注公众号【蟒圈】，每日优质文章推送。
