雨落无声

Hash 表入门
Hash表是真的方便,时间复杂度无限接近于 O(1)这就写一篇简单的Hash表入门,希望大部分人能看懂。
扫描右侧二维码阅读全文
19
2018/04

Hash 表入门

Hash表是真的方便,时间复杂度无限接近于 O(1)
这就写一篇简单的Hash表入门,希望大部分人能看懂。

普通数组

首先 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表教程,教授上课貌似还讲了其他东西,建议看完这个文档再去看看教授的PDF。

如果读到这里还是不懂,或者一知半解,欢迎点击下面几个视频:

https://www.youtube.com/watch?v=MfhjkfocRR0
https://www.youtube.com/watch?v=mFY0J5W8Udk
https://www.youtube.com/watch?v=BoZbu1cR0no

Last modification:April 19th, 2018 at 02:30 am
If you think my article is useful to you, please feel free to appreciate

3 comments

  1. Vel

    很棒!

  2. Halulu

    大佬啊,这个是学校里讲的吗

  3. 葛一速

    解释得很详细,细看了一下,初步有个概念

Leave a Comment