当散列表遇上链表会发生什么呢?

2021年7月23日 1点热度 0条评论 来源: 公众号程序员学长

      在数据结构中,散列表和链表经常会组合在一块使用,如果你对java很熟悉,你会发现LinkedHashMap这样一个常用的容器,也把散列表和链表组合起来使用。那散列表和链表是如何组合使用的,他们组合在一起能碰撞出什么火花,请跟随我的脚步,一起一探究竟。

     我们先思考这么一个问题,如何使用链表来实现LRU缓存呢?如果对LRU不熟,可以看这篇文章。页面置换算法你学会了吗?

     我们可以维护一个有序的单链表,越靠近链表尾部的结点是越早访问的。当有一个新的数据被访问时,我们从链表头开始顺序遍历。遍历的结果有两种情况。

  1. 如果此数据之前就已经被缓存在链表中,我们遍历得到这个数据对应的结点,然后将其从这个位置移动到链表的头部。

  2. 如果此数据不在链表中,又会分为两种情况。如果此时缓存链表没有满,我们直接将该结点插入链表头部。如果此时缓存链表已经满了,我们从链表尾部删除一个结点,然后将新的数据结点插入到链表头部。

      这样我们就用链表实现了一个LRU缓存,我们接下来分析一下缓存访问的时间复杂度。因为不管缓存有没有满,我们都需要遍历一遍链表,所以基于链表实现的LRU缓存,缓存访问的时间复杂度是O(n)。

 

 

        那有没有什么方法可以减低时间复杂度呢?我们先来分析一下缓存的常用操作。对于一个缓存来说,主要涉及以下三种操作:

  1. 往缓存添加一个元素。

  2. 从缓存中删除一个元素。

  3. 在缓存中查找一个元素。

 

      这三个操作都会涉及到查找的操作,如果单纯的使用链表,时间复杂度只能是O(n)。大家都知道散列表的查找操作是O(1),那我们能不能把散列表和链表结合起来使用,将缓存的这三个常用操作的时间复杂度减低到O(1)呢?答案是肯定的,我们来看一下他们是如何组合在一起的。

       如图所示,我们使用双向链表来存储数据,链表中的每个结点除了数据(data)、前驱指针(pre)、后继指针(next)之外,还新增了一个特殊的字段 hnext。这个hnext有什么作用呢?因为我们的散列表是通过链表法解决散列冲突的,所以每个结点会在两条链中。一个链是刚刚我们提到的双向链表,另一个链是散列表中的拉链。前驱和后继指针是为了将结点串在双向链表中,hnext 指针是为了将结点串在散列表的拉链中。

      了解了这个散列表和双向链表的组合存储结构之后,我们再来看,前面讲到的缓存的三个操作,是如何做到时间复杂度是 O(1) 的?

       首先,我们来看如何查找一个数据。我们前面讲过,散列表中查找数据的时间复杂度接近 O(1),所以通过散列表,我们可以很快地在缓存中找到一个数据。当找到数据之后,我们还需要将它移动到双向链表的尾部。

       其次,我们来看如何删除一个数据。我们需要找到数据所在的结点,然后将结点删除。借助散列表,我们可以在 O(1) 时间复杂度里找到要删除的结点。因为我们的链表是双向链表,双向链表可以通过前驱指针 O(1) 时间复杂度获取前驱结点,所以在双向链表中,删除结点只需要 O(1) 的时间复杂度。

      最后,我们来看如何添加一个数据。添加数据到缓存稍微有点麻烦,我们需要先看这个数据是否已经在缓存中。如果已经在其中,需要将其移动到双向链表的头部;如果不在其中,还要看缓存有没有满。如果满了,则将双向链表尾部的结点删除,然后再将数据放到链表的头部;如果没有满,就直接将数据放到链表的头部。这整个过程涉及的查找操作都可以通过散列表来完成。

       其他的操作,比如删除头结点、链表尾部插入数据等,都可以在 O(1) 的时间复杂度内完成。所以,这三个操作的时间复杂度都是 O(1)。至此,我们就通过散列表和双向链表的组合使用,实现了一个高效的、支持 LRU 缓存淘汰算法的缓存系统原型。

       所以,可以通过散列表和链表结合的方式,实现一个时间复杂度为O(1)的LRU缓存。

       更多硬核知识,请关注公众号”程序员学长"。

 

    原文作者:公众号程序员学长
    原文地址: https://www.cnblogs.com/laohanshuibi/p/15046540.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。