LFU缓存机制

发表于

算法：LFU缓存机制-淘汰最近访问频率最小的元素



题目—— LFU缓存机制

url：https://leetcode-cn.com/problems/lfu-cache/

设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get 和 put。

get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，最近最少使用的键将被去除。

进阶：
你是否可以在 O(1) 时间复杂度内执行两项操作？

示例:

1
2
3
4
5
6
7
8
9
10
11
12
LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回 1
cache.put(3, 3);    // 去除 key 2
cache.get(2);       // 返回 -1 (未找到key 2)
cache.get(3);       // 返回 3
cache.put(4, 4);    // 去除 key 1
cache.get(1);       // 返回 -1 (未找到 key 1)
cache.get(3);       // 返回 3
cache.get(4);       // 返回 4

分析

LFU(Least Frequently Used)：淘汰最近访问频率最小的元素。

缺点：1. 最新加入的数据常常会被踢除，因为其起始方法次数少。 2. 如果频率时间度量是1小时，则平均一天每个小时内的访问频率1000的热点数据可能会被2个小时的一段时间内的访问频率是1001的数据剔除掉；

实现方式：

一个k-v字典存储 数据，同时存储每个item的上次访问时间time 和 累计访问次数 cnt，当容量满时，淘汰最cnt最小的，cnt相同的情况下，淘汰time最早的；


Java解法

使用HashMap存储数据，使用优先级队列PriorityQueue存储累计访问次数 和 最近访问时间

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
93
94
95
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

class LfuObj {
	Integer key;
	Integer val;
	Integer cnt;
	Long time;
	public LfuObj(int key, int val, int cnt, long time) {
		this.key = key;
		this.val = val;
		this.cnt = cnt;
		this.time = time;
	}
	@Override
	public int hashCode() {
		return this.key.hashCode();
	}
	@Override
	public boolean equals(Object obj) {
		if(null == obj) return false;
		if(!(obj instanceof LfuObj)) return false;
		return key.equals(((LfuObj) obj).key);
	}
}
class LFUCache {
	HashMap<Integer, LfuObj> hashMap;
	PriorityQueue<LfuObj> heap = new PriorityQueue<>(new Comparator<LfuObj>() {
		@Override
		public int compare(LfuObj a, LfuObj b) {
			int c = a.cnt - b.cnt;
			return (0==c ? (int)((a.time-b.time)%65536):c);
		}
	});
	Integer capacity;
	public LFUCache(int capacity) {
		this.hashMap = new HashMap<>(capacity);
		this.capacity = capacity;
	}
	public int get(int key) {
		LfuObj lfuObj = hashMap.getOrDefault(key, null);
		if(null == lfuObj) {
			return -1;
		}
		heap.remove(lfuObj);
		lfuObj.cnt++;
		lfuObj.time = System.nanoTime();
		heap.offer(lfuObj);
		hashMap.put(key, lfuObj);
		return lfuObj.val;
	}
	public void put(int key, int value) {
		if(capacity <= 0) return;
		LfuObj lfuObj = hashMap.get(key);
		boolean isUpdate = true;
		if(null == lfuObj) {
			isUpdate = false;
			lfuObj = new LfuObj(key, value, 1, System.nanoTime());
		} else {
			lfuObj.val = value;
			lfuObj.cnt++;
			lfuObj.time = System.nanoTime();
		}
		if(hashMap.size() < capacity || isUpdate) {
			hashMap.put(key, lfuObj);
			heap.remove(lfuObj);
			heap.offer(lfuObj);
		} else {
			LfuObj tmp = heap.poll();
			hashMap.remove(tmp.key);
			heap.offer(lfuObj);
			hashMap.put(key, lfuObj);
		}
	}
}
public class App {
	public static void main(String[] agrs) {
		LFUCache cache = new LFUCache(3);
		cache.put(1, 1);
		cache.put(2, 2);
		cache.put(3, 3);
		cache.put(4, 4);
		System.out.println(cache.get(4));
		System.out.println(cache.get(3));
		System.out.println(cache.get(2));
		System.out.println(cache.get(1));
		cache.put(5, 5);
		System.out.println(cache.get(1));
		System.out.println(cache.get(2));
		System.out.println(cache.get(3));
		System.out.println(cache.get(4));
		System.out.println(cache.get(5));
	}
}