0. 基础概念

在Python中，字典是通过散列表或说哈希表实现的。字典本质上也是一个数组，但数组的索引是键经过哈希函数处理后得到的散列值，所以接下来好好咱们聊聊hash这个东西。
hash函数翻译过来叫做散列函数，又称哈希函数。通过把关键码值(key-value对)映射到表中一个位置来访问记录，以加快查找的速度。HashTable 的核心思想是对于每一个数据，根据某种给定的 Hash 函数，计算出数据的散列值，然后根据散列值来进行查找。但是不同的数据仍有一定记录产生相同的散列值的，这种状况称作“哈希碰撞”，优秀的哈希函数应该尽可能的降低产生数据碰撞的几率。

一般情况下普通的顺序表数组存储结构也可以认为是简单的哈希表，虽然没有采用哈希函数（取余），但同样可以在O(1)时间内进行查找和修改。但是这种方法存在两个问题：扩展性不强；浪费空间。

1. 常见的哈希碰撞解决方法：

1.1 开放寻址法（open addressing）

开放寻址法中，所有的元素都存放在散列表里，当产生哈希冲突时，通过一个探测函数计算出下一个候选位置，如果下一个获选位置还是有冲突，那么不断通过探测函数往下找，直到找个一个空槽来存放待插入元素。
开放地址的意思是除了哈希函数得出的地址可用，当出现冲突的时候其他的地址也一样可用，常见的开放地址思想的方法有线性探测再散列，二次探测再散列等，这些方法都是在第一选择被占用的情况下的解决方法。

1.2 再哈希法

这个方法是按顺序规定多个哈希函数，每次查询的时候按顺序调用哈希函数，调用到第一个为空的时候返回不存在，调用到此键的时候返回其值。

1.3 链地址法

将所有关键字哈希值相同的记录都存在同一线性链表中，这样不需要占用其他的哈希地址，相同的哈希值在一条链表上，按顺序遍历就可以找到，即数组和链表的结合，这种方法也是java的hash table实现方法，最新的java方法中把链表改进为了红黑树来实现。