a_lc_设计 LRU 和 LFU 缓存结构（双向链表+map | ）

设计 LRU 缓存结构

LRU（Least Recently Use）最近最少使用，实现要求：

• set和get方法的时间复杂度为O(1)
• 某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的。
• 当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。

思路：
Q：为什么需要双向链表？
因为我需要O(1)完成set操作（其中可能存在删除x结点的操作，假如我使用的是单链表，在删除完链表后，需要O(n)时间遍历到x结点的上一个结点才能实现删除）

class Node {
    int k,v;
    Node prev,next;
    Node() {}
    Node(int k,int v) {this.k=k; this.v=v;}
}
class LRUCache {
    int cap;
    Map<Integer, Node> map;
    Node head,tail;         //不动的头结点与尾节点
    public LRUCache(int capacity) {
        cap=capacity;
        map=new HashMap<>();
        head=new Node(); tail=new Node();
        head.next=tail;  tail.prev=head;
    }
    
    /**
     * 两种情况：
     *  1. 访问的key存在：返回对应的val，且将该结点设置为链表新头部
     *  2. 访问的key不存在：返回-1
     */
    public int get(int key) {
        Node node=map.get(key);
        if (node==null) 
            return -1;
        setFirst(node);
        return node.v;
    }
    /**
     * 两种情况：
     *  1. 访问的key存在：覆盖对应的val，且在链表中删除对应的结点之后在设置为新头部
     *  2. 访问的key不存在：判断容量是否达到超过：(1)超过k，则移除最不经常使用的结点；(2)
     */
    public void put(int key, int val) {
        Node node=map.get(key);
        if (node!=null) { //重复key
            node.v=val;
            setFirst(node); //将该结点设置为第一个结点
        } else {         //不存在该key
            if (map.size()==cap) { //放不下
                Node del=tail.prev;
                map.remove(del.k);
                remove(del);
            } 
            node=new Node(key,val);
            map.put(key,node);
            moveToFirst(node);
        }
    }
    
    private void setFirst(Node node) {
        remove(node);
        moveToFirst(node);
    }

    private void moveToFirst(Node node) { //注这里建议不要取head.next的方式来插入结点
        node.prev=head;
        node.next=head.next;
        head.next.prev=node;
        head.next=node;
    }

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

设计 LFU 缓存结构

LFU（Least Frequency Use）最近最频繁使用，实现要求：

• int get(int key) - 不存在key，返回-1。
• void put(int key, int value)
    - 如果键已存在，则变更其值；如果键不存在，请插入键值对。
  • 当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。当多个键具有相同使用频率时，应该去除 最久未使用 的键。

思路：

a_lc_设计 LRU 和 LFU 缓存结构（双向链表+map | ）

原文：https://www.cnblogs.com/wdt1/p/14088910.html