动画: 什么是散列表? (Hash Table 哈希表)

Love The Way You Lie 2022-03-20 08:20 367阅读 0赞

本文来自**算法爱好者**! (部分详细介绍)

## 散列表 ##

**散列表**（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

### 散列函数 ###

散列函数，顾名思义，它是一个函数。如果把它定义成 **hash(key)**，其中 key 表示元素的键值，则 **hash(key)**的值表示经过散列函数计算得到的散列值。

对于一个大小为 M 的散列表，散列函数能够把任意键转换为 \[0, M-1\] 内的正整数，该正整数即为 hash 值。

散列表存在冲突，也就是两个不同的键可能有相同的 hash 值。

散列函数应该满足以下三个条件：

*  一致性：相等的键应当有相等的 hash 值，两个键相等表示调用 equals() 返回的值相等。
 *  高效性：计算应当简便，有必要的话可以把 hash 值缓存起来，在调用 hash 函数时直接返回。
 *  均匀性：所有键的 hash 值应当均匀地分布到 \[0, M-1\] 之间，如果不能满足这个条件，有可能产生很多冲突，从而导致散列表的性能下降。

除留余数法可以将整数散列到 \[0, M-1\] 之间，例如一个正整数 k，计算 k%M 既可得到一个 \[0, M-1\] 之间的 hash 值。注意 M 必须是一个素数，否则无法利用键包含的所有信息。例如 M 为 10k，那么只能利用键的后 k 位。

对于其它数，可以将其转换成整数的形式，然后利用除留余数法。例如对于浮点数，可以将其的二进制形式转换成整数。

对于多部分组合的类型，每个部分都需要计算 hash 值，这些 hash 值都具有同等重要的地位。为了达到这个目的，可以将该类型看成 R 进制的整数，每个部分都具有不同的权值。

例如，字符串的散列函数实现如下：

int hash = 0;
    for (int i = 0; i < s.length(); i++)
        hash = (R * hash + s.charAt(i)) % M;

再比如，拥有多个成员的自定义类的哈希函数如下：

int hash = (((day * R + month) % M) * R + year) % M;

R 通常取 31

**散列冲突**

理想中的一个散列函数，希望达到

> 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)

这种效果，然而在真实的情况下，要想找到一个不同的 key 对应的散列值都不一样的散列函数，几乎是不可能的，即使是 **MD5**或者 由美国国家安全局设计的 **SHA-1**算法也无法实现。

**事实上，再好的散列函数都无法避免散列冲突。**

为什么呢？

这涉及到数学中比较好理解的一个原理：**抽屉原理**。

抽屉原理：桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面至少放两个苹果。这一现象就是我们所说的“抽屉原理”。

![5dc56e7293474913bdfd4f2fc177e9e8.gif][]

抽屉原理

对于散列表而言，无论设置的存储区域（n）有多大，当需要存储的数据大于 n 时，那么必然会存在哈希值相同的情况。这就是所谓的**散列冲突**。

![90b457d976614a65826199b1f41f3d28.gif][]

### 散列冲突 ###

那应该如何解决散列冲突问题呢？

常用的散列冲突解决方法有两类，**开放寻址法**（open addressing）和**链表法**（chaining）。

###  ###

### 开放寻址法 ###

> 定义：将散列函数扩展定义成探查序列，即每个关键字有一个探查序列h(k,0)、h(k,1)、…、h(k,m-1)，这个探查序列一定是0….m-1的一个排列（一定要包含散列表全部的下标，不然可能会发生虽然散列表没满，但是元素不能插入的情况），如果给定一个关键字k，首先会看h(k,0)是否为空，如果为空，则插入；如果不为空，则看h(k,1)是否为空，以此类推。

开放寻址法是一种解决碰撞的方法，对于开放寻址冲突解决方法，比较经典的有**线性探测方法**（Linear Probing）、**二次探测**（Quadratic probing）和 **双重散列**（Double hashing）等方法。

**线性探测方法**

![96331f4d9d5c4e6cb052bdb8e51da2b1.gif][]

开放寻址法之线性探测方法

当我们往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。

以上图为例，散列表的大小为 8 ，黄色区域表示空闲位置，橙色区域表示已经存储了数据。目前散列表中已经存储了 4 个元素。此时元素 7777777 经过 Hash 算法之后，被散列到位置下标为 7 的位置，但是这个位置已经有数据了，所以就产生了冲突。

于是按顺序地往后一个一个找，看有没有空闲的位置，此时，运气很好正巧在下一个位置就有空闲位置，将其插入，完成了数据存储。

线性探测法一个很大的弊端就是当散列表中插入的数据越来越多时，散列冲突发生的可能性就会越来越大，空闲位置会越来越少，线性探测的时间就会越来越久。极端情况下，需要从头到尾探测整个散列表，所以最坏情况下的时间复杂度为 O(n)。

![f6f0f68e476146218cdacaaf5d914636.gif][]

开放寻址法之线性探测方法的弊端

**二次探测方法**

二次探测是二次方探测法的简称。顾名思义，使用二次探测进行探测的步长变成了原来的“二次方”，也就是说，它探测的下标序列为 hash(key)+0，hash(key)+1^2或\[hash(key)-1^2\]，hash(key)+2^2或\[hash(key)-2^2\]。

![b658b87ea304495392a16f1274833305.gif][]

二次探测方法

以上图为例，散列表的大小为 8 ，黄色区域表示空闲位置，橙色区域表示已经存储了数据。目前散列表中已经存储了 7 个元素。此时元素 7777777 经过 Hash 算法之后，被散列到位置下标为 7 的位置，但是这个位置已经有数据了，所以就产生了冲突。

按照**二次探测方法**的操作，有冲突就先 + 1^2，8 这个位置有值，冲突；变为 - 1^2，6 这个位置有值，还是有冲突；于是 - 2^2， 3 这个位置是空闲的，插入。

**双重散列方法**

所谓双重散列，意思就是不仅要使用一个散列函数，而是使用一组散列函数 hash1(key)，hash2(key)，hash3(key)。。。。。。先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。

![dd213eaf845048f0b06ecebe4b81b3f4.gif][]

双重散列方法

此时，再将数据进行一次哈希算法处理，经过另外的 Hash 算法之后，被散列到位置下标为 3 的位置，完成操作。

事实上，不管采用哪种探测方法，只要当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率，一般情况下，需要尽可能保证散列表中有一定比例的空闲槽位。

一般使用**加载因子**（load factor）来表示空位的多少。

**加载因子**是表示 Hsah 表中元素的填满的程度，若加载因子越大，则填满的元素越多,这样的好处是：空间利用率高了,但冲突的机会加大了。反之,加载因子越小,填满的元素越少,好处是冲突的机会减小了，但空间浪费多了。

###  ###

### 链表法 ###

链表法使用链表来存储 hash 值相同的键，从而解决冲突。

查找需要分两步，首先查找 Key 所在的链表，然后在链表中顺序查找。

对于 N 个键，M 条链表 (N>M)，如果哈希函数能够满足均匀性的条件，每条链表的大小趋向于 N/M，因此未命中的查找和插入操作所需要的比较次数为 ~N/M。

![b4252c85-6fb0-4995-9a68-a1a5925fbdb1.png][]

链表法是一种更加常用的散列冲突解决办法，相比开放寻址法，它要简单很多。如下动图所示，在散列表中，每个位置对应一条链表，所有散列值相同的元素都放到相同位置对应的链表中。

![ea5c5b1fe98b4eef90eef97250c4ee58.gif][]

链表法

[5dc56e7293474913bdfd4f2fc177e9e8.gif]: http://5b0988e595225.cdn.sohucs.com/images/20190108/5dc56e7293474913bdfd4f2fc177e9e8.gif
[90b457d976614a65826199b1f41f3d28.gif]: http://5b0988e595225.cdn.sohucs.com/images/20190108/90b457d976614a65826199b1f41f3d28.gif
[96331f4d9d5c4e6cb052bdb8e51da2b1.gif]: http://5b0988e595225.cdn.sohucs.com/images/20190108/96331f4d9d5c4e6cb052bdb8e51da2b1.gif
[f6f0f68e476146218cdacaaf5d914636.gif]: http://5b0988e595225.cdn.sohucs.com/images/20190108/f6f0f68e476146218cdacaaf5d914636.gif
[b658b87ea304495392a16f1274833305.gif]: http://5b0988e595225.cdn.sohucs.com/images/20190108/b658b87ea304495392a16f1274833305.gif
[dd213eaf845048f0b06ecebe4b81b3f4.gif]: http://5b0988e595225.cdn.sohucs.com/images/20190108/dd213eaf845048f0b06ecebe4b81b3f4.gif
[b4252c85-6fb0-4995-9a68-a1a5925fbdb1.png]: https://github.com/CyC2018/CS-Notes/raw/master/docs/notes/pics/b4252c85-6fb0-4995-9a68-a1a5925fbdb1.png
[ea5c5b1fe98b4eef90eef97250c4ee58.gif]: http://5b0988e595225.cdn.sohucs.com/images/20190108/ea5c5b1fe98b4eef90eef97250c4ee58.gif