数据结构与算法之美系列(二):链表(上):如何实现 LRU 缓存淘汰算法

1. 常见的缓存淘汰策略有?

答:

  • 先进先出策略 FIFO (First in, First out)
  • 最少使用策略 LFU (Least Frequently Used)
  • 最近最少使用策略 LRU (Least Recently Used)

2. 怎样实现 LRU 缓存淘汰策略?

答:

思路:

  • 维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时,从链表头开始顺序遍历链表。
  • 如果此数据之前已经被缓存在链表中,遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入到链表的头部。
  • 如果此数据没有缓存在链表中,又可以分为两种情况:
    • 如果此时缓存未满,则将此结点直接插入到链表头部。
    • 如果此时缓存已满,则删除链表尾结点,将新的数据结点插入链表的头部。

基于 Array:

import java.util.HashMap;
import java.util.Map;

/**
* 基于数组的 LRU 缓存淘汰算法
* 1. 空间复杂度为 O(n)
* 2. 时间复杂度为 O(n)
* 3. 不支持 null 的缓存
*/
public class LRUBaesArray<T> {
    private static final int DEFAULT_CAPACITY = (1 << 3); // TODO
    private int capacity;
    private int length;
    private T[] elements;

    private Map<T, Integer> holder;

    public LRUBaseArray() {
        this(DEFAULT_CAPACITY);
    }

    public LRUBaseArray(int capacity) {
        this.capacity = capacity;
        elements = (T[]) new Object[capacity];
        length = 0;
        holder = new HashMap<T, Integer> (capacity);
    }

    // 模拟访问某个值
    public void offer(T object) {
        if(object == null) {
            throw new IllegalArgumentException("该缓存容器暂不支持 null");
        }
        Integer index = holder.get(objcet);
        if(index == null) {
            if(isFull()) {
                removeAndCache(object);
            } else {
                cache(object, length);
            }
        } else {
            update(index);
        }
    }

    // 若缓存中有指定的值,则更新位置
    public void update(int end) {
        T target = elements[end];
        rightShift(end);
        elements[0] = target;
        holder.put(target, 0);
    }

    // 先右移,然后缓存数据到头部
    public void cache(T object, int end) {
        rightShift(end);
        elements[0] = object;
        holder.put(object, 0);
        length++;
    }

    // 缓存满的情况,先删除,再缓存到数组头部
    public void removeAndCache(T object) {
        T key = elements[--length];
        holder.remove(key);
        cache(object, length);
    }

    // end 左边的数据统一右移一位
    private void rightShift(int end) {
        for(int i = end - 1; i >= 0; i--) {
            elements[i + 1] = elements[i];
            holder.put(value[i], i + 1);
        }
    }

    public boolean isContain(T object) {
        return holder.containsKey(object);
    }

    public boolean isEmpty() {
        return length == 0;
    }

    public boolean isFull() {
        return length == capacity;
    }

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

    static class TestLRUBaseArray {
        public static void main(String[] args) {
            testDefaultConstructor();
            testSpecifiedConstructor(4);
            // testWithException();
        }

        private static void testWithException() {
            LRUBaseArray<Integer> lru = new LRUBaseArray<Integer> ();
            lru.offer(null);
        }

        public static void testDefaultConstructor() {
            System.out.println("======无参测试======");
            LRUBaseArray<Integer> lru = new LRUBaseArray<Integer> ();
            for(int i=1; i  <= 5; i++) {
                lru.offer(i);
            }
            System.out.println(lru);
            for(int i=6; i  <= 9; i++) {
                lru.offer(i);
            }
            System.out.println(lru);
        }

        public static void testSpecifiedConstructor(int capacity) {
            System.out.println("======有参测试======");
            LRUBaseArray<Integer> lru = new LRUBaseArray<Integer> (capacity);
            for(int i=1; i <= 9; i++) {
                lru.offer(i);
            System.out.println(lru);
            }

        }
    }
}

基于 LinkedList:

import java.util.Scanner;

/**
* 基于单链表的 LRU 缓存淘汰算法
*/
public class LRUBaseLinkedList<T> {
    private static final Integer DEFAULT_CAPACITY = 10; // 默认链表容量
    private Node<T> headNode; // 头结点
    private Integer length; // 链表长度
    private Integer capacity; // 链表容量

    public LRUBaseLinkedList() {
        this.headNode = new Node<> ();
        this.capacity = DEFAULT_CAPACITY;
        this.length = 0;
    }

    public LRUBaseLinkedList(Integer capacity) {
        this.headNode = new Node<> ();
        this.capacity = capacity;
        this.length = 0;
    }

    public void add(T element) {
        Node preNode = findPreNode(element);

        if(preNode != null) { // 链表中存在,删除原数据,再插入到链表的头部
            deleteNextElemAt(preNode);
            insertElemAtBegin(element);
        } else {
            if(length >= this.capacity) {
                deleteElemAtEnd(); // 删除尾结点
            }
            insertElemAtBegin(element);
        }
    }

    // 删除 preNode 的下一个结点
    private void deleteNextElemAt(Node preNode) {
        Node temp = preNode.getNext();
        preNode.setNext(temp.getNext());
        temp = null;
        length--;
    }

    // 在链表头部插入结点
    private void insertElemAtBegin(T element) {
        Node next = head.getNext();
        headNode.setNext(new Node(element, next));
        length++;
    }

    // 获取参数结点的前一个结点
    private Node findPreNode(T element) {
        Node node = headNode;
        while(node.getNext() != null) {
            if(element.equals(node.getNext().getElement())) {
                return node;
            }
            node = node.getNext();
        }
        return null;
    }

    // 删除尾结点
    private void deleteElemAtEnd() {
        Node node = headNode;
        // 空链表直接返回
        if(node.getNext() == null) {
            return;
        }

        // 定位到倒数第二个结点
        while(node.getNext().getNext() != null) {
            node = node.getNext();
        }

        Node temp = node.getNext();
        node.setNext(null);
        temp = null;
        length--;
    }

    private void printAll() {
        Node node = headNode.getNext();
        while(node != null) {
            System.out.print(node.getElement() + ", ");
            node = node.getNext();
        }
        System.out.println();
    }

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

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

        public Node(T element) {
            this.element = element;
        }

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

        public T getElement() {
            return element;
        }

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

        public Node getNext() {
            return next;
        }

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

    public static void main(String[] args) {
        LRUBaseLinkedList list = new LRUBaseLinkedList();
        Scanner in = new Scanner(System.in);
        while(true) {
            list.add(in.nextInt());
            list.printAll();
        }
    }
}

基于 LinkedHashMap:

// 参考站内博客:《Java Map 和 Set (六):剖析 LinkedHashMap》之问题 11
public class LRUBaseLinkedHashMap<K, V> extends LinkedHashMap<K, V> {
    private int maxEntries;

    // 在构造方法中传递一个容量限制
    public LRUBaseLinkedHashMap(int maxEntries) {
        super(16, 0.75f, true);
        this.maxEntryies = maxEntries;
    }

    @Override
    protected boolean removeEldestEntry(Entry<K, V> eldest) {
        return size() > maxEntries;
    }
}

// 使用这个缓存容器
LRUBaseLinkedHashMap<String, Object> cache = new LRUBaseLinkedHashMap<> (3);
cache.put("a", "abstract");
cache.put("b", "basic");
cache.put("c", "call");
cache.put("a");
cache.put("d", "call");
System.out.print(cache);

// 因为限定缓存容量为 3, 这里先后添加了 4 个键值对
// 最久没被访问(最近最少使用)的键是 b,会被删除。所以,输出为:{c=call a=abstract, d=call}

3. 如果字符串是通过单链表存储的,怎样判断给定字符串是不是回文字符串?

答:

// TODO: confirmed it by Zheng
// 1)单链表的插入、删除、查找操作;
// 2)链表中存储的是int类型的数据;
public class SinglyLinkedList {
    private Node head = null;

    public Node findByValue(int value) {
        Node p = head;
        while (p != null && p.data != value) {
            p = p.next;
        }
        return p;
    }

    public Node findByIndex(int index) {
        Node p = head;
        int pos = 0;
        while (p != null && pos != index) {
            p = p.next;
            ++pos;
        }
        return p;
    }

    //无头结点
    //表头部插入
    //这种操作将于输入的顺序相反,逆序
    public void insertToHead(int value) {
        Node newNode = new Node(value, null);
        insertToHead(newNode);
    }

    public void insertToHead(Node newNode) {
        if (head == null) {
            head = newNode;
        } else {
            newNode.next = head;
            head = newNode;
        }
    }

    //顺序插入
    //链表尾部插入
    public void insertTail(int value){
        Node newNode = new Node(value, null);
        //空链表,可以插入新节点作为head,也可以不操作
        if (head == null){
            head = newNode;

        }else{
            Node q = head;
            while(q.next != null){
                q = q.next;
            }
            newNode.next = q.next;
            q.next = newNode;
        }
    }

    public void insertAfter(Node p, int value) {
        Node newNode = new Node(value, null);
        insertAfter(p, newNode);
    }

    public void insertAfter(Node p, Node newNode) {
        if (p == null) return;

        newNode.next = p.next;
        p.next = newNode;
    }

    public void insertBefore(Node p, int value) {
        Node newNode = new Node(value, null);
        insertBefore(p, newNode);
    }

    public void insertBefore(Node p, Node newNode) {
        if (p == null) return;
        if (head == p) {
            insertToHead(newNode);
            return;
        }

        Node q = head;
        while (q != null && q.next != p) {
            q = q.next;
        }

        if (q == null) {
            return;
        }

        newNode.next = p;
        q.next = newNode;
    }

    public void deleteByNode(Node p) {
        if (p == null || head == null) return;

        if (p == head) {
            head = head.next;
            return;
        }

        Node q = head;
        while (q != null && q.next != p) {
            q = q.next;
        }

        if (q == null) {
            return;
        }

        q.next = q.next.next;
    }

    public void deleteByValue(int value) {
        if (head == null) return;

        Node p = head;
        Node q = null;
        while (p != null && p.data != value) {
            q = p;
            p = p.next;
        }

        if (p == null) return;

        if (q == null) {
            head = head.next;
        } else {
            q.next = q.next.next;
        }

        // 可重复删除指定value的代码
        /*
           if (head != null && head.data == value) {
               head = head.next;
           }
           Node pNode = head;
           while (pNode != null) {
               if (pNode.next.data == data) {
               pNode.next = pNode.next.next;
               continue;
           }
           pNode = pNode.next;
           }
         */
    }

    public void printAll() {
        Node p = head;
        while (p != null) {
            System.out.print(p.data + " ");
            p = p.next;
        }
        System.out.println();
    }

    //判断true or false
    public boolean TFResult(Node left, Node right){
        Node l = left;
        Node r = right;

        System.out.println("left_:"+l.data);
        System.out.println("right_:"+r.data);
        while(l != null && r != null){
           if (l.data == r.data){
               l = l.next;
               r = r.next;
               continue;
           }else{
               break;
           }
        }

        System.out.println("什么结果");
        if (l==null && r==null){
           System.out.println("什么结果");
           return true;
        }else{
           return false;
        }
    }

    //判断是否为回文 
    public boolean palindrome(){
       if (head == null){
           return false;
       } else {
           System.out.println("开始执行找到中间节点");
           Node p = head;
           Node q = head;
           if (p.next == null){
               System.out.println("只有一个元素");
               return true;
           }
           while( q.next != null && q.next.next != null){
               p = p.next;
               q = q.next.next;

           }

           System.out.println("中间节点" + p.data);
           System.out.println("开始执行奇数节点的回文判断");
           Node leftLink = null;
           Node rightLink = null;
           if(q.next == null) {
               // p一定为整个链表的中点,且节点数目为奇数
               rightLink = p.next;
               leftLink = inverseLinkList(p).next;
               System.out.println("左边第一个节点"+leftLink.data);
               System.out.println("右边第一个节点"+rightLink.data);
           } else {
               //p、q均为中点
               rightLink = p.next;
               leftLink = inverseLinkList(p);
           }
           return TFResult(leftLink, rightLink);
        }
    }

    //带结点的链表翻转
    public Node inverseLinkList_head(Node p){
        // Head 为新建的一个头结点
        Node Head = new Node(9999,null);
        // p 为原来整个链表的头结点,现在Head指向 整个链表
        Head.next = p;
        /*
        带头结点的链表翻转等价于
        从第二个元素开始重新头插法建立链表
        */
        Node Cur = p.next;
        p.next = null;
        Node next = null;

        while(Cur != null){
            next = Cur.next;
            Cur.next = Head.next;
            Head.next = Cur;
            System.out.println("first " + Head.data);

            Cur = next;
        }

        // 返回左半部分的中点之前的那个节点
        // 从此处开始同步像两边比较
        return Head;
    }

    //无头结点的链表翻转
    public Node inverseLinkList(Node p){
        Node pre = null;
        Node r = head;
        System.out.println("z---" + r.data);
        Node next= null;
        while(r !=p){
            next = r.next;

            r.next = pre;
            pre = r;
            r = next;
        }

        r.next = pre;
        // 返回左半部分的中点之前的那个节点
        // 从此处开始同步像两边比较
        return r;

    }

    public static Node createNode(int value) {
        return new Node(value, null);
    }

    public static class Node {
        private int data;
        private Node next;

        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }

        public int getData() {
            return data;
        }
    }

    public static void main(String[]args){
        SinglyLinkedList link = new SinglyLinkedList(); 
        System.out.println("hello");
        //int data[] = {1};
        //int data[] = {1,2};
        //int data[] = {1,2,3,1};
        //int data[] = {1,2,5};
        //int data[] = {1,2,2,1};
       // int data[] = {1,2,5,2,1};
        int data[] = {1,2,5,3,1};

        for(int i =0; i < data.length; i++){
            //link.insertToHead(data[i]);
            link.insertTail(data[i]);
        }

       // link.printAll();
       // Node p = link.inverseLinkList_head(link.head);
       // while(p != null){
       //     System.out.println("aa"+p.data);
       //     p = p.next;
       // }

        System.out.println("打印原始:");
        link.printAll();
        if (link.palindrome()){
            System.out.println("回文");
        }else{
            System.out.println("不是回文");
        }
    }
}
-------------本文结束感谢您的阅读-------------