手写LRU、LFU

LRU

Least Recently Used

借助链表，表尾是最近访问的数据，表头是最近最久未使用的数据。

class LRUCache {
    // 思路，构造新的数据结构 哈希链表
    // 也就是hash表加上双向链表 
    // 尾部是最近存放的元素，头部是最近最久未使用的元素

    private HashMap<Integer,Node> map;
    private DoubleList cache;
    int cap;
    public LRUCache(int capacity) {
        this.map=new HashMap<Integer,Node>();
        this.cache=new DoubleList();
        this.cap=capacity;
    }

    // 提升某个key为最近使用
    private void makeRecently(int key){
        Node x=map.get(key);
        // 将该k移动到队尾
        cache.remove(x);
        cache.addLast(x);
    }

    // 添加一个元素，要将其放在队尾
    private void addRecently(int key,int val){
        Node x=new Node(key,val);
        map.put(key,x);
        cache.addLast(x);
    }

    // 删除某个key
    private void deleteKey(int key){
        Node x=map.remove(key);
        cache.remove(x);
    }

    // 删除最近最久未使用的key
    private void deleteRecently(){
        Node x=cache.removeFirst();
        map.remove(x.getKey());
    }
    
    public int get(int key) {
        if(!map.containsKey(key)){
            return -1;
        }
        makeRecently(key);
        return map.get(key).getValue();
    }
    
    public void put(int key, int value) {
        if(map.containsKey(key)){
            deleteKey(key);
            addRecently(key,value);
        }else{ //不存在key
            if(map.size()>=cap){
                deleteRecently();
            }
            addRecently(key,value);
        }
    }

    static class Node{
        int k;
        int v;
        Node pre;
        Node next;
        public Node(int k,int v){
            this.k=k;
            this.v=v;
        }
        public int getKey(){
            return k;
        }
        public int getValue(){
            return v;
        }
    }

    static class DoubleList{
        // 头尾结点
        Node head,tail;
        // 链表的元素数量
        int size;
        public DoubleList(){
            head=new Node(-1,-1);
            tail=new Node(-1,-1);
            head.next=tail;
            tail.pre=head;
            size=0;
        }

        // 在链表尾部添加结点x
        public void addLast(Node x){
            tail.pre.next=x;
            x.pre=tail.pre;
            tail.pre=x;
            x.next=tail;
            size++;
        }

        // 删除结点x
        public void remove(Node x){
            x.pre.next=x.next;
            x.next.pre=x.pre;
            size--;
        }

        // 删除链表的第一个结点，并返回该结点
        public Node removeFirst(){
            if(head.next==tail){
                return null;
            }
            Node first=head.next;
            remove(first);
            return first;
        }

        // 返回结点的长度
        public int size(){
            return size();
        }
    }
}

Java内置类型类型LinkedHashMap

class LRUCache {
    // 思路，构造新的数据结构 哈希链表
    // 也就是hash表加上双向链表
    // 尾部是最近存放的元素，头部是最近最久未使用的元素
    private LinkedHashMap<Integer,Integer> cache;
    int cap;
    public LRUCache(int capacity) {
        this.cache = new LinkedHashMap<>();
        this.cap=capacity;
    }

    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        makeRecently(key);
        return cache.get(key);
    }

    public void put(int key, int value) {
        if(cache.containsKey(key)){  //该key存在更改其value内容
            cache.remove(key);
            cache.put(key, value);
        }else{
            if(cache.size()==cap){  //达到容量
                // 删除队首元素
                Integer oldestKey = cache.keySet().iterator().next();
                cache.remove(oldestKey);
            }
            cache.put(key, value);
        }
    }

    // 将指定key变为最近可用
    private void makeRecently(int key){
        Integer value = cache.get(key);
        // 删除该key
        cache.remove(key);
        // 加入到队尾
        cache.put(key, value);
    }
}

LFU

Least Frequently Used

将数据按照访问频次排序，淘汰访问频次最低的数据，如果存在多个相同访问频次，淘汰最旧的数据。

未调试成功

class LFUCache {
    // 有问题：调试非常困难。

    // 要求：get和put操作都是O(1)
    // key映射到value   KV
    private HashMap<Integer,Integer> keyToVal;
    // key映射到Freq   KF
    private HashMap<Integer,Integer> keyToFreq;
    // 最小频率映射key 【可能多个key】   FK
    private HashMap<Integer,LinkedHashSet<Integer>> freqToKeys;
    // 最小频率
    private Integer minFreq;
    // 最大容量
    private Integer cap;

    public LFUCache(int capacity) {
        this.keyToVal=new HashMap<>();
        this.keyToFreq=new HashMap<>();
        this.freqToKeys=new HashMap<>();
        this.minFreq=0;
        this.cap=capacity;
    }
    
    public int get(int key) {
        if(!keyToVal.containsKey(key)){
            return -1;
        }
        increaseFreq(key);
        return keyToVal.get(key);
    }
    
    public void put(int key, int value) {
        if(this.cap<=0){  //没有容量
            return;
        }
        if(keyToVal.containsKey(key)){  // key已经存在
            // 修改key对应的value
            keyToVal.put(key,value);
            increaseFreq(key);
            return;
        }
        // key不存在
        if(cap==keyToVal.size()){ //容量已满
            removeMinFreqKey(); //淘汰freq最小的key
        }
        //插入  KV KF FK表
        keyToVal.put(key,value);
        keyToFreq.put(key,1);
        freqToKeys.putIfAbsent(1,new LinkedHashSet<>());
        freqToKeys.get(1).add(key);
        minFreq=1;
    }

    /** 淘汰freq最小的key,有多个淘汰最久未使用的 */
    private void removeMinFreqKey() {
        LinkedHashSet<Integer> keys=freqToKeys.get(minFreq);
        Integer oldest=keys.iterator().next();
        if(keys.size()>1){  //多个freq最小的key
            keys.remove(oldest);
        }else{  // 有一个freq最小的key
            freqToKeys.remove(minFreq);
        }
        keyToVal.remove(oldest);
        keyToFreq.remove(oldest);
    }

    /** 增加key对应的Freq  主要修改KF表和FK表 */
    private void increaseFreq(int key) {
        int freq=keyToFreq.get(key);
        // 修改KF表
        keyToFreq.put(key,freq+1);
        // 修改FK表
        LinkedHashSet<Integer> keys= freqToKeys.get(freq);
        keys.remove(key);
        if(keys.size()==0){
            freqToKeys.remove(freq);
            minFreq=freq+1;
        }
        freqToKeys.putIfAbsent(freq+1,new LinkedHashSet<>());
        freqToKeys.get(freq+1).add(key);
    }
}