前言
散列表虽然支持高效的数据插入、删除和查找操作,但是其中的数据都是通过散列函数打乱之后无规律的。也就是说,它无法按照某种顺序快速地遍历。如果想有序遍历散列表中的数据,那就需要将数据拷贝到数组中,然后排序再遍历。
散列表是动态的数据结构,不停地进行数据的插入、删除,当我们想按顺序遍历散列表时,都需要先排序,这样效率会很低。为了解决这个问题,就将散列表和链表(或者跳表)结合在一起使用。
常见的使用场景:
- LRU 缓存淘汰算法可以用链表和散列表实现;
- Redis 有序集合用到了跳表和散列表;
- Java 的 LinkedHashMap 也用到了散列表和链表。
1. LRU 缓存淘汰算法
实际上,一个缓存(cache)系统主要包含下面这几个操作:
- 往缓存中添加一个数据;
- 从缓存中删除一个数据;
- 在缓存中查找一个数据。
上面三个操作都涉及查找操作,如果单纯地用链表,查找的时间复杂度是 O(n)。如果用散列表和链表,时间复杂度变为 O(1)。
使用双向链表存储数据,链表中的每个结点除了存储数据(data)、前驱指针(prev)、后继指针(next)之外,还新增了一个特殊的字段 hnext。
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)。
自己是从事了七年开发的Android工程师,不少人私下问我,2019年Android进阶该怎么学,方法有没有?
没错,年初我花了一个多月的时间整理出来的学习资料,希望能帮助那些想进阶提升Android开发,却又不知道怎么进阶学习的朋友。【包括高级UI、性能优化、架构师课程、NDK、Kotlin、混合式开发(ReactNative+Weex)、Flutter等架构技术资料】,希望能帮助到您面试前的复习且找到一个好的工作,也节省大家在网上搜索资料的时间来学习。
网友评论