缓存的艺术：LRU与LFU策略的实现与比较

在计算机科学中，缓存是提高数据访问速度的关键技术。LRU（Least Recently Used）和LFU（Least Frequently Used）是两种常见的缓存替换策略。本文将深入探讨这两种策略的实现细节，并通过实例展示它们的差异。

LRU缓存：简单高效的策略

LRU缓存基于一个核心思想：最近使用的数据很可能在未来也会被使用。因此，当缓存满时，最久未使用的数据会被移除。

实现步骤：

1. 使用双向链表和哈希表的组合来实现O(1)时间复杂度的get和put操作。
2. 每次访问缓存中的数据时，将其移动到链表头部。
3. 当缓存满时，移除链表尾部的数据。

代码示例：

class LRUCache {
    private Map<Integer, DoubleNode> map;
    private DoubleNode head, end;
    private int capacity, count;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new DoubleNode(-1, -1);
        end = new DoubleNode(-1, -1);
        head.next = end;
        end.prev = head;
    }

    public int get(int key) {
        if (map.get(key) == null) return -1;
        DoubleNode node = map.get(key);
        moveToHead(node);
        return node.val;
    }

    public void put(int key, int value) {
        if (map.get(key) == null) {
            DoubleNode node = new DoubleNode(key, value);
            if (count >= capacity) {
                map.remove(end.prev.key);
                linkPreAndNext(end.prev);
                count--;
            }
            map.put(key, node);
            moveToHead(node);
            count++;
        } else {
            DoubleNode node = map.get(key);
            node.val = value;
            moveToHead(node);
        }
    }

    private void moveToHead(DoubleNode node) {
        linkPreAndNext(node);
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void linkPreAndNext(DoubleNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}

LFU缓存：基于频率的智能策略

LFU缓存不仅考虑了数据的使用时间，还考虑了数据的使用频率。当缓存满时，最不经常使用的数据会被移除。

实现步骤：

1. 使用一个哈希表来存储数据，并使用一个TreeSet来维护数据的使用频率。
2. 每次访问缓存中的数据时，更新其使用频率。
3. 当缓存满时，移除使用频率最低的数据。

代码示例：

class LFUCache {
    private int capacity, globalTime;
    private Map<Integer, Node> map;
    private TreeSet<Node> set;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        globalTime = 0;
        map = new HashMap<>();
        set = new TreeSet<>();
    }

    public int get(int key) {
        if (map.get(key) == null) return -1;
        Node cur = map.get(key);
        set.remove(cur);
        cur.cnt++;
        cur.time = globalTime;
        globalTime++;
        set.add(cur);
        map.put(key, cur);
        return cur.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node cur = map.get(key);
            set.remove(cur);
            cur.value = value;
            cur.cnt++;
            cur.time = globalTime;
            globalTime++;
            map.put(key, cur);
            set.add(cur);
        } else {
            if (set.size() >= capacity) {
                Node deleteNode = set.first();
                set.remove(deleteNode);
                map.remove(deleteNode.key);
            }
            Node cur = new Node(1, globalTime, key, value);
            globalTime++;
            set.add(cur);
            map.put(key, cur);
        }
    }

    class Node implements Comparable<Node> {
        int cnt, time, key, value;

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

        public int compareTo(Node other) {
            if (cnt == other.cnt) return time - other.time;
            else return cnt - other.cnt;
        }
    }
}

结论

LRU和LFU是两种不同的缓存策略，各有其适用场景。LRU策略简单高效，适用于大多数情况。而LFU策略则考虑了数据的使用频率，更适合处理突发流量和热点数据。在实际应用中，根据具体需求选择合适的策略可以显著提高系统性能。