Hash表十分方便，时间复杂度无限接近于 O(1)。
普通数组
首先 Hash 表也是存放 Key:Value 这种类型的数据的。
我们创建一个数组，用于存放数据。
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
0 1 2 3 4 5 6 7入门有一些数据，但是为了简便一些，我们只讨论这些数据的 Keys
我们想要插入的 Keys 有:
8, 26, 45 , 23, 17 , 36 , 40 , 19
如果按照我们这是一个普通数组，我们会把以上数据一个个 Push_Back 进去，之后结构会变成这样：
[8] [2 6] [4 5] [2 3] [1 7] [3 6] [4 0] [1 9]
0 1 2 3 4 5 6 7如果我们想要找到 36 这个 Key，我们会从第0个元素开始查找，一直找到第5个元素。如果想要找到 19 这个 Key，我们会从第0个元素开始找，一直找到第7个元素。
这样效率太低了，于是我们就用了Hash表这种结构。
无 Colision Hash 表
还是之前那个数组:
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
0 1 2 3 4 5 6 7还是之前那些 Key：
8, 26, 45 , 23, 17 , 36 , 40 , 19
那么Hash表是怎么插入的呢？
首先我们定义一个 Hash() 函数:
int Hash(int key)
{
return key%8; //计算出 Key 除以 8 得到的余数
}那么这是一个简单的 Hash() 函数，只需要把你需要插入的Key值给它，他就会告诉你需要把这个 Key 插到数组的哪一个地方。
比如说我想插入第一个元素 8，我只需要运行 Hash(8); 我就会得到一个 0， 我们把这个 8 插入到数组的第0个位置就行了，插入完变成这个：
[8] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
0 1 2 3 4 5 6 7接下来我们把26这个元素插入进去，运行 Hash(26); 得到了 2
于是我们把 26 这个元素插入到数组的第2个位置上，插入完成变成：
[8] [ ] [2 6] [ ] [ ] [ ] [ ] [ ]
0 1 2 3 4 5 6 7接下来我们把45这个元素插入进去，运行 Hash(45); 得到了 5
于是我们把 45 这个元素插入到数组的第5个位置上，插入完成变成：
[8] [ ] [2 6] [ ] [ ] [4 5] [ ] [ ]
0 1 2 3 4 5 6 7就这样，每一次重复这个步骤，把一个Key给 Hash() 函数进行计算，得出一个 index 值，再把这个 Key 插入到数组的 index 位置上。最终插入完成就变成了:
[8] [1 7] [2 6] [1 9] [3 6] [4 5] [4 0] [2 3]
0 1 2 3 4 5 6 7Colision
问题出现
细心的朋友们发现了，如果我用 Hash(); 函数算出来的 index 值有重复的会怎么办？
还是之前那个数组:
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
0 1 2 3 4 5 6 7Key 变化了一下：
8, 32, 45 , 23, 17 , 36 , 19
我们想插入 8 这个 Key，于是运行 Hash(8); 得到了 0, 我们将 8 这个 Key 插入到 0 号位置上 As usual：
[8] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
0 1 2 3 4 5 6 7接下来我们想要插入 32 这个 Key ，于是运行 Hash(32); 得到了 0，我们要将 32 插入到 0 号位置上。
但是这时候，我们的0号位置上已经有了一个 8 ，我们怎么办呢。这时候就出现了很多很多的解决方法。
Linear probing
好的，我们还是之前的那个容器
但是我们插入的 Keys 变成了会冲突的Keys：
8, 32 , 45, 61, 16
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
0 1 2 3 4 5 6 7我们先插入 8 ，Hash(8); 得出的结果为 0, 然后把 8插入到位置0里面去：
[8] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
0 1 2 3 4 5 6 7然后我们插入 32，Hash(32); 得出的结果为：0,准备插入 0 位置。
但是发现 0 位置已经有了一个 8 了。这个时候，我们讲 0 这个位置变成一个 链表，在 8 的 *next 下面插入 32 变成这样：
0 1 2 3 4 5 6 7
[8] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
|
v
[3 2]然后我们插入 45， 经过Hash(45); 得到 5. 于是将 45 这个 Key 插入到 第5号位置：
0 1 2 3 4 5 6 7
[8] [ ] [ ] [ ] [ ] [4 5] [ ] [ ]
|
v
[3 2]接下来我们插入 61， 计算 Hash(61); 得出 5，于是将 61 这个 Key 插入到 第5号位置，但是第5号位置已经有了一个 45 了，所以将将第5号位置改成一个 List，插入到他的 *next 里面去。
0 1 2 3 4 5 6 7
[8] [ ] [ ] [ ] [ ] [4 5] [ ] [ ]
| |
v v
[3 2] [6 1]接下来我们插入 16， 计算 Hash(16); 得出 0，于是将 61 这个 Key 插入到 第0号位置，但是第5号位置已经有其他Key了，所以将插入到 第0 号位置的末尾去。
0 1 2 3 4 5 6 7
[8] [ ] [ ] [ ] [ ] [4 5] [ ] [ ]
| |
v v
[3 2] [6 1]
|
V
[1 6]
于是这就是一个使用 Liner Probing 解决冲突问题的 Hash 表。
每次想查找元素，只需要运行 Hash，然后找到元素位置，然后不停地往他的 *next 找下去
Quadratic Probing
基础概念
还是刚刚那组数据和结构：
8, 32 , 45, 61, 16
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
0 1 2 3 4 5 6 7插入 8 之后:
[8] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
0 1 2 3 4 5 6 7当插入 32 的时候，我们发现 0 号位置满了，于是就顺移到下一个位置，也就是1 位置，并且插入32
[8] [3 2] [ ] [ ] [ ] [ ] [ ] [ ]
0 1 2 3 4 5 6 7接下来插入45，Hash(45)出来是5，放到第五号位置：
[8] [3 2] [ ] [ ] [ ] [4 5] [ ] [ ]
0 1 2 3 4 5 6 7接下来插入61，发现算出来也是 5 ，但是6位置上有了45了，于是就顺移到下一个位置，也就是 6 位置并且插入：
[8] [3 2] [ ] [ ] [ ] [4 5] [6 1] [ ]
0 1 2 3 4 5 6 7接下来插入16，计算出来是要插入到 0 位置，但是 0 位置有了 8 ，于是顺移到下一个位置 1， 发现1位置上有了32，于是继续順移到第2个位置并插入：
[8] [3 2] [1 6] [ ] [ ] [4 5] [6 1] [ ]
0 1 2 3 4 5 6 7这样就行了。
查找元素的时候直接计算 Hash，算出一个 index 值，如果那个 index 的格子上不是你想要的 key， 就順移到下一位，如果还是不是想要的 key 值，就继续順移，直到移动到自己需要的 Key 值。
真正的算法
刚刚上面那个只是基础算法，现在正式将高级一些的冲突解决算法，叫做 Quardratic Probing:
我们对之前的 Hash(); 函数进行一些小小的改动：
int Hash(int key, int i)
{
return (key%8 + i*i); //计算出 Key 除以 8 得到的余数并且加上 i的平方
}我们现在来验算一下：
8, 32 , 45, 61, 16
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
0 1 2 3 4 5 6 7插入8，我们运行 Hash(8,0) 得到 0，于是把 8 插入到 0 这个位置：
[8] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
0 1 2 3 4 5 6 7插入32，我们运行 Hash(32,0) 得到 0,于是尝试把 32 插入到0这个位置，但是发现不行，0位置上面有了8，于是我们增加 i 的值，调用 Hash(32,1)。计算出来为 1，于是插入到 1 的位置：
[8] [3 2] [ ] [ ] [ ] [ ] [ ] [ ]
0 1 2 3 4 5 6 7接着插入 45，Hash(45,0); 得到 5，插入到第5个位置：
[8] [3 2] [ ] [ ] [ ] [4 5] [ ] [ ]
0 1 2 3 4 5 6 7接着插入61，Hash(61,0);得到5，准备插入5这个位置，但是发现5这个位置有了45，于是增加 i 的值，运行Hash(61,1)，得到 6，于是插入到第6个位置：
[8] [3 2] [ ] [ ] [ ] [4 5] [6 1] [ ]
0 1 2 3 4 5 6 7接着插入16,运行Hash(16,0)，得到0，准备插入到0这个位置，发现0这个位置有了8，于是运行Hash(16,1); 得到 1，准备插入 16 到第1个位置，但是发现第1个格子有了 32， 于是运行 Hash(16,2); 得到 4,插入到第4个位置。
[8] [3 2] [ ] [ ] [1 6] [4 5] [6 1] [ ]
0 1 2 3 4 5 6 7倘若对此还是一知半解，想进一步了解Hash表，欢迎点击下面几个视频：
https://www.youtube.com/watch?v=MfhjkfocRR0
https://www.youtube.com/watch?v=mFY0J5W8Udk
https://www.youtube.com/watch?v=BoZbu1cR0no