LRU缓存算法怎么用

这篇文章主要介绍了LRU缓存算法怎么用，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。

LRU（Least Recently Used），即最近最少使用，是一种内存管理算法，该算法基于一个假设：长期不被使用的数据，未来会被使用的概率也很低。当缓存占用达到某个值的时候，应该移除最近最少被使用的数据。

1、LRU 的存储结构

LRU 存储结构是哈希链表，哈希表的数据存储是无序的，但查找效率比较高，而双链表通过前驱和后继指针使其在逻辑上有序。

• [ ] TODO ：LinkedHashMap 的源码。

• 通过 Hash 表快速找到所需要节点

• 通过双链表的特性，可以快速增加和删除节点

• 通过双链表，使其在逻辑上有序

对于缓存中没有的数据，会将其加入到链表的尾部：

对于缓存中已经有的数据，会更新数据值，并把节点移动到链表的尾部

当缓存容量不够时候，会将头节点移除

2、代码实现简单的 LRUCache

双链表的数据结构：

public class Node {
    public String Key;
    public String value;
    public Node pre;
    public Node next;

    public Node(String key, String value) {
        Key = key;
        this.value = value;
    }
}

LRUCache 的简单实现

ublic class LRUCache {
    // 头结点和尾部结点
    private Node head;
    private Node end;
    // LRU Cache 容量
    private int limit;
    // HashMap 用来存储
    public Map<String, Node> hashMap;

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

    // 根据 key 获取 value
    public String get(String key) {
        Node node = hashMap.get(key);
        if (node != null) {
            // 更新
            refreshNode(node);
            return node.value;
        }
        return null;
    }

    // 添加
    public void put(String key, String value) {
        // 检查是否存在 key
        Node node = hashMap.get(key);
        if (node != null) {
            // 如果 key 已经存在，则直接更新 value，并刷新链表
            node.value = value;
            refreshNode(node);
        } else {
            // 判断是否大于 LRU 长度
            if (hashMap.size() >= limit) {
                // 移除头部节点
                String oldKey = removeNode(head);
                // 从 hashMap 中移除
                hashMap.remove(oldKey);
            }
            // key 不存在 ，直接插入
            node = new Node(key, value);
            // 添加到链表尾部
            addNode(node);
            // 添加到 hashMap
            hashMap.put(key, node);
        }
    }

    public String remove(String key) {
        Node node = hashMap.get(key);
        if (node != null) {
            // 移除这个节点
            removeNode(node);
            hashMap.remove(key);
            return node.value;
        }
        return null;
    }


    private void refreshNode(Node node) {
        // 如果是尾部节点，无需移动
        // 如果不是尾部节点，先移除，再添加到尾部节点
        if (node != end) {
            // 移除
            removeNode(node);
            // 添加到尾部
            addNode(node);
        }
    }

    // 尾部添加结点
    private void addNode(Node node) {
        // 尾部插入
        if (end != null) {
            end.next = node;
            node.pre = end;
            node.next = null;
        }
        // 新的节点变为尾部
        end = node;
        // 如果头部为空，既是尾部也是头部
        if (head == null) {
            head = node;
        }
    }

    // 移除节点
    private String removeNode(Node node) {
        // 如果只有一个节点
        if (node == head && node == end) {
            // 移除唯一节点
            head = null;
            end = null;
        } else if (node == end) {
            // 移除尾部节点
            end = end.pre;
            end.next = null;
        } else if (node == head) {
            // 移除头部节点
            head = head.next;
            head.pre = null;
        } else {
            // 移除中间的节点
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        return node.Key;
    }

    // 测试
    public static void main(String[] args) {
        LRUCache cache = new LRUCache(5);
        cache.put("key1", "value1");
        cache.put("key2", "value2");
        cache.put("key3", "value3");
        cache.put("key4", "value4");
        cache.put("key5", "value5");
        cache.put("001", "001 的 value");
      	// 会输出 null，因为已经从缓存中移除
        System.out.println(cache.get("key1"));

        Map<String,String> map = new LinkedHashMap<>();
        map.put("ddd","ddd");
    }
}

感谢你能够认真阅读完这篇文章，希望小编分享的“LRU缓存算法怎么用”这篇文章对大家有帮助，同时也希望大家多多支持亿速云，关注亿速云行业资讯频道，更多相关知识等着你来学习!