散列表(下):为什么散列表和链表经常会一起使用?

散列表虽然支持高效的数据插入、删除和查找操作,但是其中的数据都是通过散列函数打乱之后无规律的。也就是说,它无法按照某种顺序快速地遍历。如果想有序遍历散列表中的数据,那就需要将数据拷贝到数组中,然后排序再遍历。

散列表是动态的数据结构,不停地进行数据的插入、删除,当我们想按顺序遍历散列表时,都需要先排序,这样效率会很低。为了解决这个问题,就将散列表和链表(或者跳表)结合在一起使用。

常见的使用场景:

  • LRU 缓存淘汰算法可以用链表和散列表实现;
  • Redis 有序集合用到了跳表和散列表;
  • Java 的 LinkedHashMap 也用到了散列表和链表。

1. LRU 缓存淘汰算法

实际上,一个缓存(cache)系统主要包含下面这几个操作:

  • 往缓存中添加一个数据;
  • 从缓存中删除一个数据;
  • 在缓存中查找一个数据。

上面三个操作都涉及查找操作,如果单纯地用链表,查找的时间复杂度是 O(n)。如果用散列表和链表,时间复杂度变为 O(1)。

使用双向链表存储数据,链表中的每个结点除了存储数据(data)、前驱指针(prev)、后继指针(next)之外,还新增了一个特殊的字段 hnext。

1
prev|data|next|hnext

每个结点会在两条链中。一个链是双向链表,另一个链是散列表中的拉链。前驱和后继指针是为了将结点串在双向链表中,hnext 指针是为了将结点串在散列表的拉链中。

整个过程涉及的查找操作都可以通过散列表来完成。其他的操作,比如删除头结点、链表尾部插入数据等,都可以在 O(1) 的时间复杂度内完成。所以,这三个操作的时间复杂度都是 O(1)。

2. Redis 有序集合

实际上,在有序集合中,每个成员对象有两个重要的属性,key(键值)和score(分值)。不仅会通过 score 来查找数据,还会通过 key 来查找数据。

如果细化一下 Redis 有序集合的操作,那就是下面这样:

  • 添加一个成员对象;
  • 按照键值来删除一个成员对象;
  • 按照键值来查找一个成员对象;
  • 按照分值区间查找数据,比如查找积分在 [100, 356] 之间的成员对象;
  • 按照分值从小到大排序成员变量;

如果仅仅按照分值将成员对象组织成跳表的结构,那么按照键值来删除、查询成员对象就会很慢。这时可以再按照键值构建一个散列表,按照 key 来删除、查找一个成员对象的时间复杂度就变成了 O(1)。

3. Java LinkedHashMap

LinkedHashMap 是通过双向链表和散列表这两种数据结构组合实现的。LinkedHashMap 中的“Linked”实际上是指的是双向链表,并非指用链表法解决散列冲突。

按照访问时间排序的 LinkedHashMap 本身就是一个支持 LRU 缓存淘汰策略的缓存系统。实际上,它们两个的实现原理也是一模一样。

课后思考

今天讲的几个散列表和链表结合使用的例子里,用的都是双向链表。如果把双向链表改成单链表,还能否正常工作呢?为什么呢?

其实,依然能够工作。但是,插入和删除的时候,需要查找前驱指针,时间复杂度 O(n)。

本文标题:散列表(下):为什么散列表和链表经常会一起使用?

文章作者:落英坠露

发布时间:2019年05月24日 - 09:05

最后更新:2019年05月24日 - 09:05

原始链接:https://isuperqiang.cn/2019/05/24/散列表(下):为什么散列表和链表经常会一起使用?/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

赞赏是一种行为艺术