引子

问题：给定一串数字{1,2,5,7,15,24,33,52},如何在时间复杂度为O(1)下,对数据进行CURD？

数组：我创建一个Length为53的数组，将元素插入相同下标处，是不是就可以实现查找复杂度O(1)了？但是添加修改元素时间复杂度为O(n)了。

链表：添加删除复杂度为O(1)，但是查找时间复杂度为O(n)了。

身为.NETer肯定熟练使用Dictionary和HashSet,这两个容器的底层就是HashTable，所以带着对技术浓重的兴趣（面试）,所以就从头到尾梳理一下！

理论

链地址法（拉链法）

回到问题本身，我们用数组可以实现查找复杂度为O(1),链表实现添加删除复杂度为O(1)，如果我们将两个合起来，不就可以实现增删查都为O(1)了么？如何结合呢？

我们先定义一个数组,长度为7（敲黑板，思考下为什么选7？）,将所有元素对7取余，这样所有元素都可以放在数组上了，如下图所示：

如上图，如果我们将数组中每个下标位置都放成一个链条，这样，复杂度不久降下去了么？

有问题么？没问题。真没问题么？有问题......

注意

1. 插入元素是{0,7,14,21,28}怎么办？这样都落在下标为0的链条里，时间复杂度不又上去了？针对这种情况，隔壁Java将链表优化成了红黑书，我们.NET呢？往下看。

2. 如果我的数组长度不是7，是2怎么办？所有数对2取余，不是1就是0,时间复杂度不又上去了？所以我们对数组长度应该取素数。

3. 如果元素超级多或者特别少，我们的数组长度要固定么？就要动态长度

上边这种方法学名就叫拉链法！

开放地址法

上边我们聊过拉链法（为什么老想着裤子拉链......),拉链法是向下开辟新的空间，如果我们横向开辟空间呢？还是刚才的例子，我们这样搞一下试试。

线性探测法

我们插完7以后，在插24时，发现下标为2的地方有元素了，于是向后移动一位，发现有空位，于是就插进去了。

上边这种方法就是线性探测法！

二次聚集（堆积）

聪明的老鸟们，肯定疑惑啦，如果我们继续添加元素{x%11=4},{y%11=5},此时x，y元素都要往下标6插数据。这样就导致了原始哈希地址不同的元素要插入同一个地址。即添加同义词的冲突过程中又添加了非同义词的冲突。这就是二次聚集。

二次探测法

如果在线性探测法中，我们不依次寻找下一个呢？我们针对"下一个"采取{1 ^ 2,-1 ^ 2,2 ^ 2,-2 ^ 2....}（垃圾编辑器，次方样式乱了）这样的步长呢？真聪明！你已经知道二次探测法了！

这......这还能用么？不都乱了么？下标和元素对不上了呀！怎么去查找元素呢？

别急呀，家人们呐，我们按照这个思路查询就好了：

查找算法步骤