• 2

  • 395

算法数据结构:散列表

云哥

关注云计算

6天前

1、什么是散列表

散列表(Hash Table)是实现字典操作的一种有效数据结构。用的是数组支持按照下标随机访数据的时候,时间复杂度为O(1)特性,所以散列表其实就是数组的一种扩展,由数组演化而来。一般我们也叫「哈希表」或者「Hash 表」

我们通过散列函数把元素的键值映射为下标,然后将数据存储在数组中,对应下标的位置;当我们按照键值查询元素时,我们用同样的散列函数,将键值转化数组下标,从对应的数组下标的位置取数据。

2、散列函数

散列函数,顾名思义,是一个函数。我们可以把它定义成 hash(key),其中 key 表示元素的键值,hash(key) 的值表示经过散列函数计算所得到的散列值。

构造散列函数的三个基本要求:

  1. 散列函数计算所得到的散列值是一个非负整数
  2. 如果 key1 = key2,则 hash(key1) == hash(key2)

  3. 如果 key1 != key2,则 hash(key1) != hash(key2)

「第一点」,因为数组下标是从 0 开始的,所以散列函数生成的散列值也要是非负整数。

「第二点」,相同的 key,经过同一个散列函数得到的散列值必须是相同的。

「第三点」,不同的 key,经过同一个散列韩式布得到的散列值,理论上应该是不一样的;但是在真实情况下,想要找到一个不同的 key 对应的散列值不一样的散列函数,几乎是不可能的。即便像业界著名的 MD5、SHA、CRC 等哈希算法,也无法避免这种散列冲突。而且因为数组的存储空间有限,也会加大散列冲突的概率。

3、散列冲突

再好的散列函数也无法避免散列冲突。常用的散列冲突解决方法有两类,开发寻址(open addressing)和链表法(chaining)

3.1、开放寻址法

开放寻址法的核心思想是,如果出现了散列冲突,我们就重新探测一个空闲位置,将其插入。那如何探测新的位置呢?常用方法有「线性探测」(Linear Probing)、「二次探测」(Quadratic Probing)和「双重探测」(Double Hashing)。

3.1.1、线性探测

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

如上图所示,散列表大小为 10,在元素 x 插入散列表之前,已经有 6 个元素插入到散列表中。x 经过哈希函数之后,被散列到位置下标为 7 的位置,但是这个位置已经有数据了,所以就产生了冲突。于是我们就顺序地往后一个一个找,看有没有空闲的位置,遍历到尾部都没有找到空闲的位置,于是我们再从表头开始找,直到找到空闲位置 2,并将 x 插入到这个位置。

在散列表中「查找元素」的过程有点类似插入过程。先通过散列函数求出要查找元素的键值对应的散列值,然后比较数组中下标为散列指的元素和要查找的元素;如果相等,则说明是我们要找的元素,否则就顺序往后依次查找;如果遍历到数组中的空闲位置,还没有找到,就说明要查找的元素并没有在散列表中。

散列表跟数组一样,不仅支持插入、查找操作,还支持删除操作。对于使用线性探测法解决冲突的散列表,删除操作稍微复杂,我们不能单纯地把要删除的元素设置为空。这是因为在查找的时候,一旦我们通过线性探测法,找到一个空闲位置,我们就可以判定散列表中不存在这个数据。但是,如果这个空闲位置是我们后来删除的,就会导致原来查找的算法失效。本来存在的数据,会被认定为不存在。如何解决呢?

我们可以将删除的元素,特殊标记为 deleted。当线性探测查找的时候,遇到标记为 deleted 的位置时,继续往下探测。

从上图我们会发现,当散列表中插入的数据越来越多时,散列冲突发生的可能性就会越来越大,空闲位置会越来越少,线性探测的时间就会越来越久。极端情况下,我们可能需探测整个散列表,所以最坏情况下的时间复杂度为O(n)。同理,在删除和查找时,也有可能会线性探测整张散列表,才能找到要查找或者删除的数据。

3.1.2、二次探测

所谓二次探测,跟线性探测很像,线性探测每次探测的步长为 1,那它探测的下标序列就是

二次探测的步长就变成了原来的「二次方」,即它探测的下标序列就是

3.1.2、双重散列

所谓双重散列,就是会使用一组散列函数

我们先用第一个散列函数,如果计算得到的数组下标已经被占用,再用第二个散列函数,依次类推,直到找到空闲的存储位置。

不管采用哪种探测方法,当散列表中空闲位置不多的时候,散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率,一般情况下,我们会尽可能保证散列表中有一定比例的空闲槽位。我们用「装载因子」(load factor)来表示空位的多少。

3.2、链表法

链表法是一种更加常用的散列冲突解决方案,相比开放寻址法,它要简单很多。如图所示,在散列表中,每个「桶」(bucket)或者「槽」(slot)会对应一条链表,所有散列值相同的元素都会放在相同槽位对应的链表中。

当插入的时候,我们只要通过散列函数计算出对应的散列槽位,将其插入到对应链表中即可,所以插入的时间复杂度是O(1)。当查找、删除一个元素时,通过同一个散列函数计算出对应的槽位,然后遍历链表查找或者删除。

删除或查找操作的时间复杂度跟链表的长度 k 成正比,也就是O(k)。对于散列比较均匀的散列函数来说,理论上讲,k = n / m,其中 n 表示散列表中数据的个数,m 表示散列表中槽的个数。

4、小结

散列表来源于数组,它借助函数对数组这种数据结构进行扩展,利用的是数组支持按照下标随机访问元素的特性。散列表两个核心问题是「散列函数设计」「散列冲突解决」。散列冲突有两种常用的解决方法,开放寻址法和链表法。散列函数设计的好坏决定了散列冲突的概率,也就决定散列表的性能。

免责声明:文章版权归原作者所有,其内容与观点不代表Unitimes立场,亦不构成任何投资意见或建议。

云计算

395

相关文章推荐

未登录头像

暂无评论