Java笔记 ·

单链表实现LRU缓存淘汰算法

LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是如果数据最近被访问过,那么将来被访问的几率也更高,相反如果很长时间未被访问,则它在最近一段时间内也不会被访问。实现方式有很多种,这里先介绍基于数组和单链表的实现方式。

基于数组的LRU

首位置保存最新访问数据,末尾位置优先清理。

  1. 如果此数据之前已经被缓存在数组中了,查找到其位置并从原位置中删除该数据,将位置之前的数据依次右移一位,保存此数据到数组第一个元素位置上。
  2. 如果此数据没有在缓存数组中,又可以分为两种情况:
    • 如果此时缓存未满,将数组中数据全部右移一位,保存此数据到数组第一个元素位置上。
    • 如果此时缓存已满,将数组最后一位数据删除,再将数组中数据全部右移一位,保存此数据到数组第一个元素位置上。
public class LRUBasedArray<T> {
    private final int DEFAUL_CAPACITY = 10;
    private Integer capacity;
    private Integer count;
    private T[] value;
    /**
     * 用于元素记录所在数组位置
     */
    private Map<T, Integer> holder;

    public LRUBasedArray() {
        this.capacity = this.DEFAUL_CAPACITY;
        this.value = (T[]) new Object[capacity];
        this.count = 0;
        this.holder = new HashMap<T, Integer>(capacity);
    }

    public LRUBasedArray(Integer capacity) {
        this.capacity = capacity;
        this.value = (T[]) new Object[capacity];
        this.count = 0;
        this.holder = new HashMap<T, Integer>(capacity);
    }

    /**
     * 缓存数据
     * @param data
     */
    public void add(T data){
        if (data == null){
            throw new IllegalArgumentException("该缓存容器不支持null!");
        }
        Integer index = holder.get(data);
        if (index != null){
            // 向右移动
            update(index);
        }else {
            // 是否已满
            if (isFull()){
                // 删除,更新
                removeAndCache(data);
            }else {
                // 右移元素更新
                cache(data, count);
            }
        }
    }

    /**
     * 数据之前已在数组中,将数组中的对应数据更新到数组开始。
     * @param index
     */
    private void update(Integer index){
        T key = value[index];
        rightOffer(index);
        value[0] = key;
        holder.put(key,0);
    }

    /**
     * 向数组插入新数据
     * @param data
     * @param end
     */
    private void cache(T data, Integer end){
        rightOffer(end);
        value[0] = data;
        holder.put(data,0);
        count++;
    }

    /**
     * 删数组最后一位,并将新数据保存到数组开始
     * @param data
     */
    private void removeAndCache(T data){
        T key = value[--count];
        holder.remove(key);
        cache(data, count);
    }


    /**
     * index左侧的统一向右移动一位
     * @param index
     */
    private void rightOffer(Integer index){
        for (int i=index;i>0;i--){
            value[i] = value[i-1];
            holder.put(value[i],i);
        }
    }

    /**
     * 判断数组是否已满
     * @return
     */
    private boolean isFull(){
        return count == capacity;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < count; i++) {
            sb.append(value[i]);
            sb.append(" ");
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        LRUBasedArray<Integer> array = new LRUBasedArray();
        Random random = new Random(20);
        int num = 0;
        for (int i=0;i<20;i++){
            num = random.nextInt(20);
            array.add(num);
            PrintUtill.println("插入"+ num + ":");
            PrintUtill.println(array.toString());
        }
    }

}

当然也可以首位置优先清理,末尾位置保存最新访问数据,思想类似,这里就不再赘述。

基于单链表

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

  1. 如果此数据之前已经被缓存在链表中了,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入到链表的头部。
  2. 如果此数据没有在缓存链表中,又可以分为两种情况:
    • 如果此时缓存未满,则将此结点直接插入到链表的头部;
    • 如果此时缓存已满,则链表尾结点删除,将新的数据结点插入链表的头部。
public class LRUBaseLinkedList<T> {
    /**
     * 默认容量
     */
    private final int DEFAUL_CAPACITY = 10;

    /**
     * 头结点
     */
    private SNode<T> head;
    /**
     * 链表长度
     */
    private Integer length;
    /**
     * 链表容量
     */
    private Integer capacipy;

    public LRUBaseLinkedList() {
        this.head = new SNode<>();
        this.length = 0;
        this.capacipy = DEFAUL_CAPACITY;
    }

    public LRUBaseLinkedList(Integer capacipy) {
        this.head = new SNode<>();
        this.length = 0;
        this.capacipy = capacipy;
    }

    /**
     *  缓存数据
     * @param data
     */
    public void add(T data){
        SNode preNode = findPreNode(data);
        if (preNode != null){
            // 删除节点
            deleteElemOptim(preNode);
        }else {
            // 节点不存在,队列是否已满
            if (length>=capacipy){
                // 已满,删除队尾
                deleteElemAtEnd();
            }
        }
        // 将节点插入到头
        intsertElemAtBegin(data);
    }

    /**
     * 删除某个结点
     * @param node
     */
    public void deleteElemOptim(SNode node){
        node.setNext(node.getNext().getNext());
        length--;
    }

    /**
     * 删除链表尾部的结点
     */
    public void deleteElemAtEnd(){
        SNode node = head;

        if (node.getNext() == null) return;

        while (node.getNext().getNext() != null){
            node = node.getNext();
        }
        node.getNext().setNext(null);
        length--;

    }

    /**
     * 在头部插入结点
     * @param data
     */
    public void intsertElemAtBegin(T data){
        SNode node = new SNode(data, head.getNext());
        head.setNext(node);
        length++;
    }



    /**
     * 获取查找到元素的前一个节点
     * @param data
     * @return
     */
    private SNode findPreNode(T data){
       SNode node = head;
       while (node.getNext() != null){
           if (node.getNext().element.equals(data)){
               return node;
           }
           node = node.getNext();
       }
       return null;
    }

    private void printAll(){
        SNode node = head.getNext();
        while (node!=null){
            PrintUtill.print(node.element+">");
            node = node.getNext();
        }
        PrintUtill.printlnRule();

    }



    public class SNode<T> {
        private T element;
        private SNode next;

        public SNode() {
            this.next = null;
        }

        public SNode(T element, SNode next) {
            this.element = element;
            this.next = next;
        }

        public T getElement() {
            return element;
        }

        public void setElement(T element) {
            this.element = element;
        }

        public SNode getNext() {
            return next;
        }

        public void setNext(SNode next) {
            this.next = next;
        }
    }


    public static void main(String[] args) {
        LRUBaseLinkedList<Integer> list = new LRUBaseLinkedList<Integer>();
        Random random = new Random(20);
        int num = 0;
        for (int i=0;i<20;i++){
            num = random.nextInt(20);
            list.add(num);
            PrintUtill.println("插入"+ num + ":");
            list.printAll();
        }

    }
}

延伸

什么是缓存

缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非常广泛的应用,比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。

缓存的大小有限,当缓存被用满时,哪些数据应该被清理出去,哪些数据应该被保留?这就需要缓存淘汰策略来决定。

有哪些缓存淘汰策略?

常见的策略有三种:先进先出策略 FIFO(First In,First Out)、最少使用策略 LFU(Least Frequently Used)、最近最少使用策略 LRU(Least Recently Used)。

什么是链表

  • 和数组一样是一种线性表。
  • 从内存结构来看,链表的内存结构是不连续的内存空间,是将一组零散的内存块串联起来,从而进行数据存储的数据结构
  • 链表中的每一个内存块被称为结点Node。结点除了存储数据外,还需记录链上的下一个结点的地址,即后继指针next。

常用链表

单链表、循环链表、双向链表、双向循环链表

单链表

  • 每个结点只包含一个指针,即后继指针。
  • 单链表有两个特殊结点,即头结点尾结点。头结点用来记录链表的基地址,可以遍历得到整条链表。尾结点指向一个空地址 NULL,表示这是链表上最后一个结点。
  • 插入和删除结点的时间复杂度为O(1),查找的时间复杂度为O(n)。

循环链表

一种特殊的单链表。

  • 它跟单链表唯一的区别是尾结点指针是指向链表的头结点。
  • 循环链表的优点是从链尾到链头比较方便。适用于处理具有环型结构特点的数据,比如著名的约瑟夫问题。

双向链表

  • 结点除了存储数据外,还有两个指针分别指向前一个结点地址(前驱指针prev)和下一个结点地址(后继指针next)。
  • 头结点的前驱指向为空,尾结点指向为空。
  • 给定数据值查询/删除对应结点,双向和单链表的时间复杂度均是O(n);给定结点的查询/删除,双向O(1),单链表O(n)。

双向循环链表

首节点的前驱指针指向尾节点,尾节点的后继指针指向首节点。

用空间换时间的设计思想

对于执行较慢的程序,可以通过消耗更多的内存(空间换时间)来进行优化。
消耗过多内存的程序,可以通过消耗更多的时间(时间换空间)来降低内存的消耗。

数组和链表比较:

  • 链表插入、删除数据效率高,时间复杂度O(1),随机访问效率低,时间复杂度O(n)。
  • 数组插入、删除数据效率低,时间复杂度O(n),随机访问效率高,时间复杂度O(1)。

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

链表本身没有大小的限制,天然地支持动态扩容。

如果代码对内存的使用非常苛刻,那数组就更适合。

数组缺点

内存中没有足够的连续空间时,数组申请空间会失败,导致内存不足(out of memory)。

数组大小固定,当不够用时,需要扩容,一旦扩容就要进行数据复制,而这时非常费时。

链表缺点

内存消耗大,因为要消耗额外的空间存储指针信息。

对链表进行频繁的插入和删除操作,会导致频繁的内存申请和释放,容易造成内存碎片。Java语言中还可能会造成频繁的GC(Garbage Collection,垃圾回收)。

参考资料

数据结构与算法之美

参与评论