数据结构与算法--LFU算法

一、简介

LFU 的全称是 Least Frequently Used(最近不经常使用)，是一种缓存淘汰策略，它是根据频率维度来选择将要淘汰的元素，即删除访问频率最低的元素。如果两个元素的访问频率相同，则淘汰最久没被访问的元素。它的底层是 两个哈希表 + N个双链表 实现的，查找和添加的时间复杂度都是O(1)。

460. LFU 缓存 (opens new window)

二、LFU算法的代码实现

2.1、双链表的节点类

class DLinkedNode{//双链表节点类
        int key,val,freq;
        DLinkedNode pre,next;
        public DLinkedNode(int _key,int _val,int _freq){
            this.key = _key;
            this.val = _val;
            this.freq = _freq;
        }
}

2.2、双链表的实现类

class DLinkedList{//双链表
        DLinkedNode head,tail;//链表首尾结点

        public DLinkedList(){
            this.head = new DLinkedNode(-1,-1,-1);
            this.tail = new DLinkedNode(-1,-1,-1);
            head.next = tail;
            tail.pre = head;
        }

        public void addToHead(DLinkedNode node){//将节点添加到头部
            node.pre = head;
            node.next = head.next;
            head.next.pre = node;
            head.next = node;
        }

        public void removeNode(DLinkedNode node){//删除某个节点
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }

        public boolean isEmpty(){//判断链表是否为空
            return head.next == tail;
        }

}

2.3、完整实现

package com.offer;

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

class LFUCache {

    private Map<Integer,DLinkedNode> keyCache = new HashMap<>();

    private Map<Integer,DLinkedList> freqCache = new HashMap<>();

    int capacity;//容量

    int minFreq = 0;//记录缓存中最低频率

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

    public int get(int key) {
        DLinkedNode node = keyCache.get(key);
        if(node == null) return -1;
        //频率+1
        freqInc(node);
        return node.val;
    }

    public void put(int key, int value) {
        if(capacity == 0) return;
        DLinkedNode node = keyCache.get(key);
        if(node != null){
            node.val = value;//更改值
            freqInc(node);
        }else{
            //容量满了
            if(keyCache.size() == capacity){
                DLinkedList linkedList = freqCache.get(minFreq);
                keyCache.remove(linkedList.tail.pre.key);//删除keyCache
                linkedList.removeNode(linkedList.tail.pre);//删除DLinkedList尾部结点
                if(linkedList.isEmpty()){
                    //处理后，若此时minFreq的双链表为空
                    freqCache.remove(minFreq);
                }
            }
            //创建新节点
            DLinkedNode newNode = new DLinkedNode(key,value,1);
            keyCache.put(key,newNode);
            DLinkedList linkedList = freqCache.getOrDefault(newNode.freq,new DLinkedList());
            linkedList.addToHead(newNode);
            freqCache.put(newNode.freq,linkedList);
            minFreq = 1;

        }
    }

    public void freqInc(DLinkedNode node){
        //在当前频率(freq)链表中删除此结点
        int freq = node.freq;
        DLinkedList linkedList = freqCache.get(freq);
        linkedList.removeNode(node);
        if(linkedList.isEmpty()){
            //如果删除后，双链表为空，那么删除对应的频率
            freqCache.remove(freq);
            if(minFreq == freq){
                minFreq = freq + 1;
            }
        }
        //频率+1
        node.freq++;
        //在当前频率(freq+1)链表中插入此结点
        linkedList = freqCache.getOrDefault(node.freq,new DLinkedList());
        linkedList.addToHead(node);
        freqCache.put(node.freq,linkedList);

    }

    class DLinkedNode{//双链表节点类
        int key,val,freq;
        DLinkedNode pre,next;
        public DLinkedNode(int _key,int _val,int _freq){
            this.key = _key;
            this.val = _val;
            this.freq = _freq;
        }
    }

    class DLinkedList{//双链表
        DLinkedNode head,tail;//链表首尾结点

        public DLinkedList(){
            this.head = new DLinkedNode(-1,-1,-1);
            this.tail = new DLinkedNode(-1,-1,-1);
            head.next = tail;
            tail.pre = head;
        }

        public void addToHead(DLinkedNode node){//将节点添加到头部
            node.pre = head;
            node.next = head.next;
            head.next.pre = node;
            head.next = node;
        }

        public void removeNode(DLinkedNode node){//删除某个节点
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }

        public boolean isEmpty(){//判断链表是否为空
            return head.next == tail;
        }

    }

    public static void main(String[] args) {
        LFUCache obj = new LFUCache(3);
        obj.put(1,11);
        obj.put(2,12);
        obj.put(3,13);
        obj.get(1);
        obj.get(2);
        obj.get(2);
        obj.get(2);
        obj.get(3);
        obj.get(3);
        obj.get(3);
        obj.put(4,14);
        System.out.println("args = " + Arrays.deepToString(args));
    }
}