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 7
Colision
问题出现
细心的朋友们发现了,如果我用 Hash(); 函数算出来的 index 值有重复的会怎么办?
还是之前那个数组:
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
0 1 2 3 4 5 6 7
Key 变化了一下:
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