高级数据结构——LRU Cache、LFU Cache

LRU

LRU介绍

LRU:Least Recent Used,即为最近最少使用,LRU是一种Cache替换算法.Cache的容量是有限的,因此当Cache装满时,如果有新的内容需要添加进来,那么就需要对Cache中的内容进行调整,而LRU算法则是将Cache中最近最少使用的内容剔除掉,也就是最久未使用的内容剔除掉.

LRU代码实现

首先,很容易想到LRU算法的数据结构应该是一个队列.那么对于Cache中的内容,"使用"的概念无非是查询(get)和插入(add).我们可以维护这样一个队列:按照使用的时间先后将元素依次放到队列中,也就是说最近使用的内容放在队尾,最久未使用的内容放在队头.这样在对Cache中的内容作更新时,只需要剔除掉队头的元素即可.
而对于插入而言,因为插入的元素一定是最近使用的元素,所以直接插入到队尾即可.但在插入之前,需要判断队列中的元素是否已经满了,如果满需要先将队头元素剔除掉,然后再插入
而对于查询而言,首先需要判断该元素是否在队列中,如果在,则需要将该元素移至队头,同时对队列结构进行调整.
为了查询的方便,我们规定元素是以键值对的形式出现的,因此我们还需要使用一个哈希表来维护键值对.

public class LRUCache {
	// 元素节点
    static class LinkNode{
        public int key;
        public int value;
        public LinkNode prev;
        public LinkNode next;

        public LinkNode(int key,int val){
            this.key = key;
            this.value = val;
        }
        public LinkNode(){

        }
    }
    // 头结点
    public LinkNode head;
    // 尾结点
    public LinkNode tail;
    // 队列中实际元素个数
    public int usedSize;
    // 队列容量
    public int capacity;
    // 哈希表提高查询效率
    public Map<Integer,LinkNode> cache;
    public LRUCache(int capacity){
        this.head = new LinkNode();
        this.tail = new LinkNode();
        head.next = tail;
        tail.prev = head;
        this.capacity = capacity;
        cache = new HashMap<>();
    }
    public void put(int key,int val){
    	// 首先判断cache中是否已经存在对应的key
        if(cache.get(key) != null){
        	// 存在对应的key,更新cache中的键值对,同时将该节点移动到队尾
        	cache.put(key,new LinkNode(key,val));
            LinkNode node = cache.get(key);
            moveToTail(node);
        }else{
        // 不存在则创建一个新的节点存储到哈希表中,并插入到队尾
            LinkNode node = new LinkNode(key,val);
            cache.put(key,node);
            addToTail(node);
            usedSize++;
            // 如果此时cache中元素个数大于容量,则将队头元素移除
            if(usedSize > capacity){
                cache.remove(key);
                usedSize--;
                removeHead();
            }
        }
    }
    public LinkNode get(int key){
        LinkNode node = cache.get(key);
        if(node == null){
        	// cache中没有该元素存在
            return new LinkNode(-1,-1);
        }else{
        	// 将该元素移动到队尾并返回该节点的val值
            moveToTail(node);
            return node;
        }
    }
    private void moveToTail(LinkNode node){
    	// 将节点移动到队尾是通过先删除该节点,然后再将该节点添加到队尾实现
        removeNode(node);
        addToTail(node);
    }
    private void removeNode(LinkNode node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    private void addToTail(LinkNode node){
        tail.prev.next = node;
        node.prev = tail.prev;
        node.next = tail;
        tail.prev = node;
    }
    private LinkNode removeHead(){
        LinkNode cur = head.next;
        head.next = cur.next;
        cur.next.prev = head;
        return cur;
    }
    public void printNodes(){
        
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

LFU

LFU介绍

LFU和LRU一样,也是一种Cache替换算法.LFU:Least Frequent Used,即为最少频率使用,与LRU最久未使用不同,LFU算法在面对Cache中元素更新时首先更新的是使用频率最少的节点.如果Cache中存在多个频率最少的节点,则优先删除距离当前时间最久的节点.

LFU代码实现

与LRU类似,实现LFU的数据结构也是队列.但因为LFU剔除的是频率使用最少的节点,因此我们需要利用哈希表来存储每个节点的使用频率和该节点的映射.即<频率,该频率下的所有节点(以队列形式排列)>,每次需要剔除时都是删除频率最低的key对应的队列的最后一个节点.
针对添加操作而言,首先需要判断Cache中是否存在该key值对应的节点,如果存在,则将该节点的频率+1,然后从原频率对应的队列中移除加入到新频率下对应的队列的队头;如果不存在,首先判断Cache中元素个数是否已满,如果已满则将最低频率对应的队列的对伪元素删除掉,然后将其添加到频率为1对应的队列的队头
针对查询操作而言,首先查询Cache中是否存在该key值对应的节点,如果存在,则将该节点的频率+1,然后从原频率对应的队列中移除并加入到新频率下对应的队列的队头,否则返回异常

import java.util.*;

/**
 * LFU:淘汰使用次数最少的:freq确定使用频率,双向链表确定频率相同的记录的使用时间的先后
 * @author qiu
 * @version 1.8.0
 */
public class LFU {
	// 元素节点
    static class Node{
    	// 该节点对应的使用频率
        int freq;
        int key;
        int val;

        public Node(int freq,int key,int val){
            this.freq = freq;
            this.key = key;
            this.val = val;
        }
    }
    // 哈希表存储频率与该频率下节点的映射
    Map<Integer,LinkedList<Node>> freq_mq = new HashMap<>();
    // 哈希表存储key和对应的节点的映射
    Map<Integer,Node> mq = new HashMap<>();
    // Cache中实际剩余容量
    int size;
    // 当前情况下的最小频率
    int min_freq = 0;
    public void set(int key,int val){
        //如果mq中存在,那么只是更新freq_mq
        //如果mq中不存在,如果容量为0需要删除频率最小对应的双向链表的尾部节点,然后将新的node放入哈希表中频率为1的双向链表中
        if(mq.containsKey(key)){
            update(mq.get(key),key,val);
        }else{
            if(size == 0){
                int oldKey = freq_mq.get(min_freq).getLast().key;
                freq_mq.get(min_freq).removeLast();
                if(freq_mq.get(min_freq).isEmpty()){
                    freq_mq.remove(min_freq);
                }
                mq.remove(oldKey);
                size++;
            }
            size--;
            min_freq = 1;
            if(!freq_mq.containsKey(1)){
                freq_mq.put(1,new LinkedList<>());
            }
            freq_mq.get(1).addFirst(new Node(1,key,val));

            mq.put(key,freq_mq.get(1).getFirst());
        }
    }
    public void update(Node node,int key,int value){
        //首先把原来freq对应双向链表中的某个node删除掉,然后频率+1,
        // 然后构造一个新频率的node放到新的频率对应的双向链表的头部
        int freq = node.freq;
        freq_mq.get(freq).remove(node);
        if(freq_mq.get(freq).isEmpty()){
            freq_mq.remove(freq);
            if(freq == min_freq){
                min_freq += 1;
            }
        }
        // 新频率对应的队列不存在就创建一个新的键值对
        if(!freq_mq.containsKey(freq+1)){
            freq_mq.put(freq+1,new LinkedList<>());
        }
        freq_mq.get(freq+1).addFirst(new Node(freq+1,key,value));
        mq.put(key,freq_mq.get(freq+1).getFirst());
    }
    public int get(int key){
        int res = -1;
        //如果哈希表中存在更新res和双向链表
        if(mq.containsKey(key)){
            res = mq.get(key).val;
            update(mq.get(key),key,res);
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84