数据结构与算法之美-散列表

数据结构与算法之美-散列表

散列表的英文名叫 HashTable,我们平时也叫它哈希表。散列表用的是数组支持按照下标进行随机访问的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。

散列函数

顾名思义,它是一个函数。我们可以把它定义为hash(key),其中key表示元素的键值,hash(key)值表示经过散列函数计算得到的散列值。
散列函数的设计需要满足三点基本要求:

  1. 散列函数得到的散列值是一个非负整数。
  2. 如果key1=key2,那么hash(key1)=hash(key2)。
  3. 如果key1!=key2,那么hash(key1)!=hash(key2)。

第三点理解起来可能会有问题,这个要求看起来合情合理,但在实际情况下,要想找到一个不同的key对应散列值都不一样的散列函数几乎是不可能的。

如何解决散列冲突

  • 开放寻址法的核心思想是如果遇到散列冲突,就重新探测一个空闲位置,将其插入。删除数据的时候比较麻烦,需要特殊标记已经删除掉的数据,当数据量比较小、装载因子小的时候,适合此方法。常见的探测方法有线性探测二次探测双重散列。ThreadLocalMap就是采用的该方法来解决散列冲突。
  • 拉链法是在散列表每个数组元素位置对应一条链表,将散列值相同的元素放入同一条链表中即可。当链表长度过大时,可将链表转换为跳表或红黑树,将表内查询时间复杂度从O(n)降到O($log^n$)。

装载因子过大该怎么办

装载因子越大说明散列表中的元素越多,空闲位置越少,出现散列冲突的概率就越大。不仅插入元素时要多次寻址或拉很长的链,查找过程也会变得很慢。针对这种情况,我们可以通过动态扩容的方式解决。但是,针对散列表的扩容,数据搬移操作要复杂一些。因为散列表的大小变了,数据的存储位置也就变了,所以我们需要通过散列函数重新计算每个数据的存储位置。

大部分情况下,动态扩容的散列表插入一个数据都很快,但是在特殊情况下,当装载因子已经到达阈值,需要先进行扩容,再插入数据。这个时候,插入数据就会变得很慢,甚至会无法接受。举个例子,如果散列表当前大小为1GB,要想扩容为原来的两倍大小,那就需要对1GB的数据重新计算哈希值,并且从原来的散列表搬移到新的散列表,听起来就很耗时,是不是?

为了解决一次性扩容耗时过多的情况,我们可以将扩容操作穿插在插入操作的过程中,分批完成。当装载因子触达阈值之后,我们只申请新空间,但并不将老的数据搬移到新散列表中。当有新数据要插入时,我们将新数据插入新散列表中,并且从老的散列表中拿出一个数据放入到新散列表。每次插入一个数据到散列表,我们都重复上面的过程。经过多次插入操作之后,老的散列表中的数据就一点一点全部搬移到新散列表中了。这样没有了集中的一次性数据搬移,插入操作就都变得很快了。

对于查询操作,为了兼容新、老散列表中的数据,我们先从新散列表中查找,如果没有找到,再去老的散列表中查找。

为啥散列表和链表经常会一起使用

不知道你有没有注意到散列表和链表经常会结合在一起来使用,例如用链表来实现LRU缓存淘汰算法的时间复杂度为O(n),结合散列表可以将时间复杂度降到O(1)。Redis有序集合通过散列表和跳表(算是一种改进版的链表)来实现有序集合。Java中的LinkedHashMap容器也是通过散列表和链表来实现的。

1.LRU缓存淘汰算法

针对于缓存系统,常见的往缓存中添加一个数据、从缓存中删除一个数据、在缓存中查找一个数据这三个操作都会涉及到查找操作,如果单纯的采用链表的话,时间复杂度只能是O(n)。如果我们将散列表和链表两种数据结构组合使用,可以将这三个操作的时间 复杂度都降低到O(1)。具体的结构就是下面这个样子:
散列表结合链表结构图
使用双向链表存储数据,链表中的每个节点包含数据(data)、前驱指针(prev)、后继指针(next)。使用散列表通过拉链法解决散列冲突,所以节点还额外包含一个hnext指针。查找元素的时候通过散列表以O(1)的时间复杂度查找到目标元素,然后通过双向链表的以O(1)的时间复杂度完成插入、删除操作即可,所以总的时间复杂度也就是O(1)。

2.Redis有序集合

实际上,在Redis有序集合中,每个成员对象有两个属性,key(键值)和score(分值)。我们不仅会通过score来查询数据,还会通过key来查询数据。如果想通过键值来查找或删除一个元素,单是通过跳表是很难实现的。如果我们按照键值构建一个散列表,这样按照key来查找或删除一个元素的时间复杂度就变成O(1)了,同时借助跳表结构,其他操作也很高效。

3.Java LinkedHashMap

LinkedHashMap在HashMap基础上结合一个双向链表支持按照数据的插入顺序遍历数组。除此之外,还可通过构造函数设置accessOrder为true来支持按照访问顺序来遍历数据,所以可以通过LinkedHashMap来实现一个LRU算法。

总结一下其实就是:数组占据随机访问的优势,却有需要连续内存的缺点。链表具有可不连续存储的优势,但访问查找是线性的。散列表和链表、跳表的混合使用,是为了结合数组和链表的优势,规避它们的不足。