缓存淘汰 最近最少使用算法 Java

最近最少使用（Least Recently Used, LRU）算法是一种常用于缓存管理的算法。如果您希望在Java中实现LRU缓存算法，您可以考虑以下几个步骤：

1. 创建一个双向链表来维护缓存中的键值对，其中最近使用的项位于链表的前面，最久未使用的项位于链表的末尾。
2. 使用一个HashMap来快速查找缓存中的键值对，其中键是缓存的键，值是链表节点的引用。
3. 当需要访问一个缓存项时，首先在HashMap中查找对应的节点。如果存在，则将该节点移动到链表的头部，表示它是最近使用的项；如果不存在，则根据缓存容量的限制，可能需要删除链表末尾的节点来腾出空间。
4. 当需要插入一个新的缓存项时，首先检查HashMap中是否存在相同的键。如果存在，则更新对应节点的值，并将该节点移动到链表头部；如果不存在，则创建新的节点并将其插入到链表头部，同时在HashMap中添加对应的键值对。
5. 这样，每次访问缓存项时，都可以通过HashMap快速定位到对应的节点，并将其移动到链表头部。同时，当缓存容量达到上限时，可以从链表末尾删除最久未使用的节点。

通过以上步骤，您可以在Java中实现LRU缓存算法。请注意，这只是一种基本的实现方式，您可以根据实际需求和性能要求进行进一步的优化和调整。

Java代码

以下是一个简单的Java代码示例，演示如何实现LRU缓存算法：

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

class LRUCache {
    private final int capacity;
    private final Map<Integer, Node> cache;
    private final Node head;
    private final Node tail;

    class Node {
        int key;
        int value;
        Node prev;
        Node next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>();
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            moveToHead(node);
            return node.value;
        }
        return -1;
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            node.value = value;
            moveToHead(node);
        } else {
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
            if (cache.size() > capacity) {
                Node tailNode = removeTail();
                cache.remove(tailNode.key);
            }
        }
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private Node removeTail() {
        Node tailNode = tail.prev;
        removeNode(tailNode);
        return tailNode;
    }
}

这是一个LRUCache类，它使用双向链表和HashMap来实现LRU缓存。您可以使用该类来创建一个LRU缓存对象，并使用get(key)和put(key, value)方法来获取和插入缓存项。请注意，此代码示例仅为演示目的，您可能需要根据具体需求进行适当的修改和扩展。

基于链表实现

如果您希望基于链表实现LRU缓存算法，以下是一个基于链表的简单Java代码示例：

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

class LRUCache {
    private final int capacity;
    private final Map<Integer, Node> cache;
    private Node head;
    private Node tail;

    class Node {
        int key;
        int value;
        Node prev;
        Node next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>();
        head = null;
        tail = null;
    }

    public int get(int key) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            updateNode(node);
            return node.value;
        }
        return -1;
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            node.value = value;
            updateNode(node);
        } else {
            if (cache.size() >= capacity) {
                evictTail();
            }
            Node newNode = new Node(key, value);
            addToHead(newNode);
            cache.put(key, newNode);
        }
    }

    private void updateNode(Node node) {
        if (node == head) {
            return;
        }
        removeNode(node);
        addToHead(node);
    }

    private void addToHead(Node node) {
        if (head == null) {
            head = node;
            tail = node;
        } else {
            node.next = head;
            head.prev = node;
            head = node;
        }
    }

    private void removeNode(Node node) {
        if (node == head) {
            head = node.next;
        } else if (node == tail) {
            tail = node.prev;
        } else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
    }

    private void evictTail() {
        if (tail != null) {
            cache.remove(tail.key);
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                tail = tail.prev;
                tail.next = null;
            }
        }
    }
}

这个实现基于双向链表，使用head和tail节点来追踪链表的头部和尾部。cache是一个HashMap，用于快速查找缓存项。在get(key)方法中，如果缓存中存在键，则更新对应节点的位置并返回值；否则，返回-1表示缓存项不存在。在put(key, value)方法中，如果缓存中存在键，则更新对应节点的值并将节点移动到链表头部；如果缓存已满，则从尾部移除最久未使用的节点，并插入新节点到链表头部。请注意，这个简单的实现不考虑并发性和线程安全，适用于单线程环境下的LRU缓存场景。