这两种算法广泛应用于缓存系统优化，能在缓存空间不足时高效地淘汰数据项。

1. LRU 原理

        LRU 算法基于时间局部性原理，淘汰最近最少使用的数据项。其核心思想是：当缓存满时，优先移除最近未被访问的项。实现上，LRU 通常维护一个访问顺序队列：

• 当一个数据项被访问（get 或 put）时，它被移动到队列头部。
• 当缓存满时，队列尾部的项（即最近最少使用的）被淘汰。 时间复杂度：get 和 put 操作通常为 O(1)，使用哈希表和双向链表实现。

LRU Java 实现代码

以下是一个手动实现的 LRU 缓存类，使用双向链表和哈希表来保证高效操作：

public class LRUCache {
    private static class Node {
        int key;
        int value;
        Node prev;
        Node next;
        
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    private final int capacity;
    private final HashMap<Integer, Node> map;
    private final Node head;
    private final Node tail;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            removeNode(node);     // 移除节点
            addToHead(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;   // 更新值
            removeNode(node);
            addToHead(node);
        } else {
            if (map.size() >= capacity) {
                map.remove(tail.prev.key); // 移除尾部节点（LRU项）
                removeNode(tail.prev);
            }
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            addToHead(newNode);   // 添加到头部
        }
    }
    
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    private void addToHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
}

// 使用示例
public class Main {
    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2); // 容量为2
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1)); // 返回1
        cache.put(3, 3); // 淘汰key=2
        System.out.println(cache.get(2)); // 返回-1（未找到）
    }
}

代码说明：

• Node 类表示双向链表节点，存储键值对。
• LRUCache 类使用 HashMap 快速查找节点，双向链表维护访问顺序。
• get 操作：如果键存在，移动节点到头部并返回值；否则返回-1。
• put 操作：如果键存在，更新值并移动节点；否则添加新节点，如果缓存满则淘汰尾部节点。
• 时间复杂度：get 和 put 均为 $O(1)$。

2. LFU 原理

        LFU 算法基于频率局部性原理，淘汰使用频率最低的数据项。其核心思想是：当缓存满时，优先移除访问次数最少的项。实现更复杂，需要跟踪每个项的频率：

• 当一个数据项被访问时，其频率增加。
• 维护频率队列：每个频率对应一个队列（如双向链表），存储该频率的所有项。
• 当缓存满时，从最小频率的队列中淘汰一个项（通常是最旧的或任一个）。 时间复杂度：get 和 put 操作通常为 O(1) 或 O(log n)，使用哈希表和最小堆或嵌套链表实现。

LFU Java 实现代码

以下是一个手动实现的 LFU 缓存类，使用哈希表和双向链表来管理频率：

import java.util.HashMap;
import java.util.LinkedHashSet;

public class LFUCache {
    private static class Node {
        int key;
        int value;
        int frequency;
        
        Node(int key, int value) {
            this.key = key;
            this.value = value;
            this.frequency = 1; // 初始频率为1
        }
    }
    
    private final int capacity;
    private final HashMap<Integer, Node> keyMap; // key -> Node
    private final HashMap<Integer, LinkedHashSet<Integer>> freqMap; // freq -> keys set
    private int minFrequency;
    
    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.keyMap = new HashMap<>();
        this.freqMap = new HashMap<>();
        this.minFrequency = 1; // 初始最小频率
        freqMap.put(1, new LinkedHashSet<>()); // 初始化频率1的集合
    }
    
    public int get(int key) {
        if (keyMap.containsKey(key)) {
            Node node = keyMap.get(key);
            updateFrequency(node); // 更新频率
            return node.value;
        }
        return -1; // 未找到
    }
    
    public void put(int key, int value) {
        if (capacity == 0) return;
        
        if (keyMap.containsKey(key)) {
            Node node = keyMap.get(key);
            node.value = value; // 更新值
            updateFrequency(node);
        } else {
            if (keyMap.size() >= capacity) {
                evict(); // 淘汰一个项
            }
            Node newNode = new Node(key, value);
            keyMap.put(key, newNode);
            freqMap.get(1).add(key); // 添加到频率1集合
            minFrequency = 1; // 最小频率重置为1
        }
    }
    
    private void updateFrequency(Node node) {
        int oldFreq = node.frequency;
        freqMap.get(oldFreq).remove(node.key); // 从旧频率集合移除
        node.frequency++;
        int newFreq = node.frequency;
        
        if (!freqMap.containsKey(newFreq)) {
            freqMap.put(newFreq, new LinkedHashSet<>());
        }
        freqMap.get(newFreq).add(node.key); // 添加到新频率集合
        
        if (oldFreq == minFrequency && freqMap.get(oldFreq).isEmpty()) {
            minFrequency++; // 更新最小频率
        }
    }
    
    private void evict() {
        LinkedHashSet<Integer> minFreqSet = freqMap.get(minFrequency);
        int evictKey = minFreqSet.iterator().next(); // 淘汰一个项（如最先加入的）
        minFreqSet.remove(evictKey);
        keyMap.remove(evictKey);
        
        if (minFreqSet.isEmpty()) {
            freqMap.remove(minFrequency);
            // 寻找新的最小频率（可能需遍历）
            if (!freqMap.isEmpty()) {
                minFrequency = freqMap.keySet().iterator().next();
            } else {
                minFrequency = 1;
            }
        }
    }
}

// 使用示例
public class Main {
    public static void main(String[] args) {
        LFUCache cache = new LFUCache(2); // 容量为2
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1)); // 返回1，频率增至2
        cache.put(3, 3); // 淘汰key=2（频率最低）
        System.out.println(cache.get(2)); // 返回-1（未找到）
        System.out.println(cache.get(3)); // 返回3，频率为1
    }
}

代码说明：

• Node 类存储键、值和频率。
• keyMap 映射键到节点；freqMap 映射频率到键集合（使用 LinkedHashSet 维护插入顺序）。
• get 操作：如果键存在，更新频率并返回值。
• put 操作：如果键存在，更新值和频率；否则添加新节点，如果缓存满则淘汰最小频率的一个项。
• updateFrequency 方法：增加节点频率，并移动到新频率集合。
• evict 方法：从最小频率集合中淘汰一个项（如最先加入的）。
• 时间复杂度：get 和 put 平均 O(1)，但在某些情况下可能退化，但通过优化可接近 O(1)。

3.总结

        LRU 和 LFU 是常见的缓存淘汰算法：LRU 基于时间顺序，适合访问模式有局部性的场景；LFU 基于频率，适合访问模式稳定的场景。