用Java写一个最近最少使用算法

### 回答1：
以下是用Java实现最近最少使用算法的示例代码：

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

public class LRUCache {

    private int capacity;
    private Map<Integer, Node> map = new HashMap<Integer, Node>();
    private Node head;
    private Node tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        if(map.containsKey(key)) {
            Node node = map.get(key);
            remove(node);
            setHead(node);
            return node.value;
        }
        return -1;
    }

    public void put(int key, int value) {
        if(map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            remove(node);
            setHead(node);
        } else {
            Node newNode = new Node(key, value);
            if(map.size() >= capacity) {
                map.remove(tail.key);
                remove(tail);
            }
            setHead(newNode);
            map.put(key, newNode);
        }
    }

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

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

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

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

在该实现中，我们使用一个哈希表来存储缓存中的键值对，同时使用双向链表来维护缓存中最近最少使用的键值对。具体地，我们将缓存中最近访问的键值对放在链表头部，而最久未被访问的键值对放在链表尾部。当缓存已满时，我们删除链表尾部的键值对，并在哈希表中同时删除对应的键值对。当访问某个键值对时，我们先在哈希表中查找该键是否存在，如果存在，则将对应的节点移到链表头部，如果不存在，则返回-1。当插入某个键值对时，我们先判断键是否已经存在。如果存在，则更新对应的节点，并将其移到链表头部。如果不存在，则新建一个节点，并将其插入到链表头部。如果缓存已满，则删除链表尾部的键值对，并在哈希表中同时删除对应的键值对。

### 回答2：
最近最少使用（Least Recently Used，LRU）算法是一种常用的缓存替换算法，用于在缓存满时选择替换哪个元素。以下是使用Java实现LRU算法的示例代码：

import java.util.*;

class LRUCache<K, V> {
    private final int capacity;
    private LinkedHashMap<K, V> cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new LinkedHashMap<>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
                return size() > capacity;
            }
        };
    }

    public V get(K key) {
        return cache.getOrDefault(key, null);
    }

    public void put(K key, V value) {
        cache.put(key, value);
    }

    public int size() {
        return cache.size();
    }
}

public class Main {
    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);

        cache.put(1, "apple");
        cache.put(2, "banana");
        cache.put(3, "cherry");

        System.out.println(cache.get(2));  // 输出：banana

        cache.put(4, "date");

        System.out.println(cache.size());  // 输出：3
        System.out.println(cache.get(1));  // 输出：null（1已被替换）
    }
}

以上代码中，我们定义了一个`LRUCache`类，该类使用Java内置的`LinkedHashMap`实现。在构造方法中，我们指定了缓存的容量，并覆写了`removeEldestEntry`方法，用于判断当缓存超过容量时是否需要移除最近最少使用的元素。

主程序中我们首先创建了一个容量为3的缓存，插入了3个键值对。然后调用`get`方法获取键2对应的值，然后再插入一个键值对，此时容量已满，根据LRU算法，最近最少使用的键1被替换。最后输出缓存大小和键1对应的值（为空，因为已被替换）。

### 回答3：
最近最少使用（LRU）算法是一种缓存淘汰策略，它根据数据访问的时间来淘汰最久未使用的数据。在Java中实现LRU算法可以通过以下步骤进行：

1. 创建一个双向链表和一个哈希表。
2. 双向链表用于存储数据节点，每个节点包含键值对和前后指针。
3. 哈希表用于记录每个键对应的节点位置，以实现O(1)时间复杂度的访问和更新操作。
4. 当访问某个键时，先通过哈希表定位到节点位置，并将该节点从链表中移动到链表头部，表示最近使用过。
5. 如果缓存已满，当需要插入新数据时，将链表尾部的节点淘汰，并从哈希表中移除对应的键，再将新节点插入链表头部。
6. 需要注意的是，在步骤4和步骤5中都要更新哈希表和链表的指针。

以下是一个简单的Java代码实现LRU算法的示例：

import java.util.HashMap;

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

    private HashMap<Integer, Node> map;
    private int capacity;
    private Node head;
    private Node tail;

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

    public int get(int key) {
        Node node = map.get(key);
        if (node != null) {
            moveToHead(node);
            return node.value;
        }
        return -1;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node == null) {
            node = new Node();
            node.key = key;
            node.value = value;
            map.put(key, node);
            addToHead(node);
            if (map.size() > capacity) {
                Node last = removeTail();
                map.remove(last.key);
            }
        } else {
            node.value = value;
            moveToHead(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 void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

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

这段代码定义了一个LRU缓存类`LRUCache`，其中`get()`方法用于获取缓存中某个键的值，`put()`方法用于将某个键值对存入缓存。具体实现就是根据上述步骤，通过双向链表和哈希表来维护缓存的数据结构，并且通过`get()`和`put()`方法来操作缓存数据。