LRU-最近最少使用算法

53 阅读 0 评论 35 点赞

我是靠谱客的博主敏感冥王星，最近开发中收集的这篇文章主要介绍LRU-最近最少使用算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

LRU：Least Recently Used 也就是最近最少使用的意思，是一种内存管理算法，该算法最早应用于Linux操作系统。这个算法基于一种假设：长期不被使用的数据，在未来被用到的几率也不大。因此，当数据所占内存达到一定阈值时，我们要移除掉最近最少被使用的数据。

redis中的内存管理算法中也用到了LRU，LinkedHashMap（哈希链表）中也对LRU进行的具体的实现。现在这里也写一个简单的LinkedHashMap实现，这里默认hashmap中的key没有hash冲突。

public class LRUCache {
    //头结点，代表最老的数据，当然也可以反过来。
    private Node head;
    //尾结点，代表最新的数据
    private Node tail;
    //缓存的大小，超过便要清理
    private int limit;
    //真正完成存储操作
    private Map<String, Node> hashMap;

    public LRUCache(int limit) {
        this.limit = limit;
        hashMap = new HashMap<>();
    }

    //获取缓存中的值
    public String get(String key) {
        Node node = hashMap.get(key);
        if (node == null) {
            return null;
        }
        refreshNode(node);
        return node.value;
    }

    //往缓存中添加值
    public void put(String key, String value) {
        Node node = hashMap.get(key);
        if (node == null) {
            if (hashMap.size() >= limit) {
                //如果超过缓存容量则首先删除头结点
                String oldKey = removeNode(head);
                hashMap.remove(oldKey);
            }
            node = new Node(key, value);
            addNode(node);
            hashMap.put(key, node);
        } else {
            node.value = value;
            refreshNode(node);
        }
    }

    //删除缓存中的值
    public void remove(String key) {
        Node node = hashMap.get(key);
        removeNode(node);
        hashMap.remove(key);
    }

    private void refreshNode(Node node) {
        if (node == tail) {
            return;
        }
        //从链表中删除该结点
        removeNode(node);
        //将该结点添加到链表尾部
        addNode(node);
    }

    //删除结点
    private String removeNode(Node node) {
        if (head == node && tail == node) {
            //只有一个结点
            head = null;
            tail = null;
        } else if (head == node) {
            //删除头结点
            head = head.next;
            head.pre = null;
        } else if (tail == node) {
            //删除尾结点
            tail = tail.pre;
            tail.next = null;
        } else {
            //删除中间结点
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }

        return node.key;
    }

    //尾部插入节点
    private void addNode(Node node) {
        if (tail != null) {
            tail.next = node;
            node.pre = tail;
            node.next = null;
        }
        tail = node;
        if (head == null) {
            head = node;
        }
    }

    //打印数据 新->旧
    private void print() {
        Node node = tail;
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.pre;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(4);
        cache.put("a", "111");
        cache.put("b", "222");
        cache.put("c", "333");
        cache.put("d", "444");
        cache.print();
        cache.put("e", "555");
        cache.print();
        cache.remove("b");
        cache.print();
        cache.put("f", "666");
        cache.print();
        cache.get("c");
        cache.print();
    }

    @Data
    class Node {
        public Node(String key, String value) {
            this.key = key;
            this.value = value;
        }

        private Node pre;
        private Node next;
        private String key;
        private String value;
    }
}

缓存大小为4。数据打印为新数据-》老数据

添加四个数据：444 333 222 111
再添加一个数据，删除老数据（头结点）：555 444 333 222
删除一个数据：555 444 333
再添加一个数据：666 555 444 333
查询缓存数据（key为c）：333 666 555 444