我们已经知道数组可以通过下标 O(1) 访问，但是删除一个中间元素却要移动其他元素的位置，时间复杂度为 O(n)。 而循环双端链表可以在知道一个节点的情况下迅速删除它，但是查找复杂度又变成了 O(n)。
难道就没有一种可以快速定位和删除元素的方法吗？似乎想要快速找到一个元素除了知道下标之外别无他法，于是乎聪明的计算机科学家又想到了一种方法。 能不能给每个元素一种“逻辑下标”，然后直接找到它呢？散列表就是这种实现。它通过一个哈希函数来计算一个元素应该放在数组哪个位置，当然对于一个特定的元素，哈希函数每次计算的下标必须要一样才可以，而且范围不能超过给定的数组长度。

散列（Hashing）是电脑科学中一种对数据的处理方法，通过某种特定的函数/算法（称为散列函数/算法）将要检索的项与用来检索的索引（称为散列，或者散列值）关联起来，生成一种便于搜索的数据结构（称为散列表）。旧译哈希（误以为是人名而采用了音译）。它也常用作一种信息安全的实现方法，由一串数据中经过散列算法（Hashing algorithms）计算出来的数据指纹（data fingerprint），经常用来识别文件与数据是否有被篡改，以保证文件与数据确实是由原创者所提供。

如今，散列算法也被用来加密存在数据库中的密码（password）字符串，由于散列算法所计算出来的散列值（Hash Value）具有不可逆（无法逆向演算回原本的数值）的性质，因此可有效的保护密码。

• 若关键字为 k，则其值存放在 f(k) 的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系 f 为散列函数，按这个思想建立的表为散列表。
• 对不同的关键字可能得到同一散列地址，即 k1≠k2，而 f(k1) = f(k2) ，这种现象称为冲突。
• 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

开放寻址法中，所有的元素都存放在散列表里，当产生哈希冲突时，通过一个探测函数计算出下一个候选位置，如果下一个获选位置还是有冲突，那么不断通过探测函数往下找，直到找个一个空槽来存放待插入元素。 函数定义:
其中，hash(key) 是哈希函数，di 是增量序列，i 为已冲突的次数。

• 线性探测法(linear probing)： h(k,i)=(h′(k)+i)%m,i=0,1,...,m−1 di= i ，或者其他线性函数。相当于逐个探测存放地址的表，直到查找到一个空单元，然后放置在该单元。
• 平方探测法(quadratic probing)： 当一个槽被占用，以二次方作为偏移量。 h(k,i)=(h′(k)+c1+c2i2)%m,i=0,1,...,m−1
• 双重散列(double hashing): 重新计算 hash 结果。 h(k,i)=(h1(k)+ih2(k))%m

另一种解决冲突的办法。散列到同一位置的元素，不是继续往下探测，而是这个位置是一个链表，这些元素则都放到该链表上。

Python字典对象实现原理 Python 数据结构入门 - 哈希表（Hash Table） 哈希表 HashTable 的 Python 实现