美文网首页Android开发程序员Android技术知识
链表(上)—— LRU 缓存淘汰算法的实现

链表(上)—— LRU 缓存淘汰算法的实现

作者: Android架构 | 来源:发表于2019-04-25 16:13 被阅读8次

    经典的链表应用场景就是 LRU 缓存淘汰算法。

    1. 链表结构

    数组需要一块连续的内存空间来存储,对内存的要求比较高。而链表不需要,它通过“指针”将一组零散的内存块串联起来使用。

    三种常见的链表结构:单链表双向链表循环链表

    单链表:头结点记录链表的基地址,可以用来遍历整条链表。尾结点的指针指向空地址 NULL,表示最后的结点。每个结点存储数据 data 和后继指针 next,如下:

    针对链表的插入和删除操作,只需要考虑相邻结点的指针改变,所以对应的时间复杂度是 O(1)。但是,随机访问需要从头结点开始遍历,所以时间复杂度是 O(n)。

    循环链表是一种特殊的单链表,它的尾结点指针指向链表的头结点,优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时,就特别适合采用循环链表,比如约瑟夫问题。

    双向链表支持两个方向,每个结点有个后继指针 next 指向后面的结点和一个前驱指针 prev 指向前面的结点。它支持双向遍历,带来了操作的灵活性。双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点,这使得它在某些情况下的插入、删除等操作比单链表简单高效。对于一个有序链表,双向链表的按值查询的效率也要比单链表高一些。

    在实际的软件开发中,双向链表尽管比较费内存,但比单链表的应用更加广泛。Java 语言中的 LinkedHashMap 就用到了双向链表,这是用空间换时间的设计思想。

    2. 链表、数组性能比较

    时间复杂度 数组 链表
    插入、删除 O(n) O(1)
    随机访问 O(1) O(n)

    数组简单易用,在实现上使用的是连续的内存空间,可以借助 CPU 的缓存机制,预读数组中的数据,所以访问效率更高。而链表在内存中并不是连续存储,所以对 CPU 缓存不友好,没办法有效预读。(此处是局部性原理)

    数组的缺点是大小固定,要占用整块连续内存空间。如果数组过大,容易导致 OOM。扩容时需要拷贝数组,非常耗时。链表本身没有大小的限制,天然地支持动态扩容。

    如果代码对内存的使用非常苛刻,那数组就是更适合的选择。链表需要额外存储指针结点,频繁的增删操作容易造成内存碎片,如果用 Java 语言,就可能导致频繁 GC。

    如何用链表实现 LRU 缓存呢?

    维护一个有序单链表,靠近尾部的结点是最早访问的。当有数据被访问时,从头开始遍历链表。

    1. 如果数据被缓存过,遍历得到对应的结点,把它从原来位置删除,插入到链表头部。
    2. 如果没有缓存过,那么分两种情况:
      • 如果缓存没满,那么直接把新数据插入链表尾部;
      • 如果缓存已满,那么把尾结点删除,新数据插入链表头部。

    基于链表的实现思路,缓存访问的时间复杂度为 O(n)。考虑一下优化,比如引入散列表老记录每个数据的位置,使访问时间复杂度降到 O(1)。

    思考题:

    如何判断一个字符串是否是回文字符串?如果字符串是通过单链表来存储的,那该如何来判断是一个回文串呢?

    自己是从事了七年开发的Android工程师,不少人私下问我,2019年Android进阶该怎么学,方法有没有?

    没错,年初我花了一个多月的时间整理出来的学习资料,希望能帮助那些想进阶提升Android开发,却又不知道怎么进阶学习的朋友。【包括高级UI、性能优化、架构师课程、NDK、Kotlin、混合式开发(ReactNative+Weex)、Flutter等架构技术资料】,希望能帮助到您面试前的复习且找到一个好的工作,也节省大家在网上搜索资料的时间来学习。

    资料获取方式:加入Android架构交流QQ群聊:513088520 ,进群即领取资料!!!

    点击链接加入群聊【Android移动架构总群】:加入群聊

    资料大全

    相关文章

      网友评论

        本文标题:链表(上)—— LRU 缓存淘汰算法的实现

        本文链接:https://www.haomeiwen.com/subject/jyyzgqtx.html