在之前的文章: 什么是哈希算法|散列函数|哈希函数？我们学习了哈希表和哈希函数（散列）的定义，在进行更进一步的解释前我们先复习一下相关概念：
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。键(key)：又称为关键字。唯一的标示要存储的数据，可以是数据本身或者数据的一部分。槽(slot/bucket)：哈希表中用于保存数据的一个单元，也就是数据真正存放的容器。哈希函数(hash function)：将键(key)映射(map)到数据应该存放的槽(slot)所在位置的函数。哈希冲突(hash collision)：哈希函数将两个不同的键映射到同一个索引的情况。
Hash的冲突有两种解决方案，第一种叫做内消解机制，第二种是外消解机制。那么什么是内，什么是外呢？我的理解是，内消解机制代表了在hash函数映射时就将冲突发生的可能隔绝掉了，也就是如果两个f(key)相同后，映射终止，并在内部消解掉这种冲突，最后再重新映射。相应的，外消解就很好理解了：当冲突发生后，直接记录冲突的f(key)并且利用特殊的结构化处理，将冲突在存放区消解掉。我们先来看看内消解机制：
一、内消解
内消解机制主要是用开地址法（开放一个新地址的意思）实现，具体分为两种方法，我们把它们叫做“探查”(Probing)
Closed Hashing 开地址法 （Open Addressing）
名词解释：叫Closed，是因为哈希冲突后，并不会在本身之外开拓新的空间，而是继续顺延下去某个位置来存放，所以是一个密闭的空间，所以叫“Closed”，至于开地址（Open Addressing），这个应该相对于那种通过链表来开拓新空间，它是在本身地址上，另外找个位置。所以叫开地址。
1. 线性探查
定义：通过散列函数hash(key)，找到关键字key在线性序列中的位置，如果当前位置已经有了一个关键字，就长生了哈希冲突，就往后探测i个位置（i小于线性序列的大小），直到当前位置没有关键字存在。
直观理解就是，遇见冲突的地址，就再加一个常数，0不行加1,1不行加2,...一直到找到一个不冲突的地址，或者地址溢出。这个方法很好理解，下面的图摘自算法教材。我想另外谈谈开地址法中线性探查的优点和缺点。
优点：第一，计算简单，开销少。第二，直白，易于实现，最后还有个优点就是对于稀疏的地址序列，线性探查能保证散列后地址的分布不会太分散。
缺点：最坏的情况就是前面所有的线性位置都被占用了，这个时候往后加地址的效率就很低了，而且很容易溢出
2. 双散列探查
再哈希法又叫双哈希法，有多个不同的Hash函数，当发生冲突时，使用第二个，第三个，….，等哈希函数。具体实现取决于散列函数，但思想并不复杂，如果对线性同余发生器熟悉的朋友也许很容易理解双散列的涵义，但不理解也没关系，因为这种方法用的不多。
与线性探查比较，其基本策略相同，唯一不同是：它不是检查冲突位置后的每一个位置，而是采用另一个散列函数产生一个固定的增量。（跳跃式检查和插入)。第二个散列函数要仔细选择，需满足条件
（1）排除散列值是0的情况
（2）产生的散列值必须与表长M互素
一句话评价双散列探查法，就是计算地址，直到无冲突。虽然不易发生聚集，但是增加了计算时间。这是典型的用时间换空间，当然效率还不错就是了。
二、外消解
外消解的第一个方法是建立公共溢出区：，这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。
溢出表可以用不同的数据结构实现，一般来说还是取决于原有地址的保存方式。这种方法也是简单直白，问题是太浪费空间，以及如何处理溢出表的空间分配。实际使用中我们普遍使用下面的这种方法，叫做桶散列，俗称拉链法。
Open Hashing 拉链法
名词解释：叫拉链，是因为哈希冲突后，用链表去延展来解决。
这个图中
h(x) = x mod 10 ;是一个哈希函数，可见代入
x=91和
x=1的时候都会到映射到键值为1的slot，那么这样就会引发冲突，在拉链法中，用链表延展去存储同键值的数据。
优点：
- 拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
- 在用拉链法构造的散列表中，删除结点的操作易于实现
缺点：
- 在对链表进行存储空间分配的时候，会降低整个程序的运行速率
三、如何选择
- 线性探测是三者中最快的（前提是内存足够大保证表稀疏）
- 双重散列法使用内存最高效（需要额外开销计算第二个散列值）
- 链地址法易于实现（假设已经存在好的内存分配），特别对于删除操作；对于固定表长通常选择链地址法。
使用内消解时：选择线性探测还是双重散列主要取决于：计算散列函数的开销和装填因子。αα较小，两者均可；长关键字计算散列函数开销大；装填因子αα接近于1，双重散列性能大于线性探测。
使用外消解时：链地址法需要额外的内存空间存储链接，但是有一些符号表中已经事先分配好了链接字段的元素。虽然不如开放地址法快，但性能仍然比顺序搜索快的多。 当以搜索为主且关键字数目不能精确预测时，动态散列表是可选的。
参考文章：
[1] 哈希算法解决冲突的方法
[2]《数据结构与算法：Python语言描述》
[3]《离散数学及其应用》