LFU实现:
复制代码
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
96
97
98
99
100
101
102import java.util.LinkedHashMap; import java.util.Map; public class LFUCache { class CacheEntry { private String data; private int frequency; // default constructor private CacheEntry() {} public String getData() { return data; } public void setData(String data) { this.data = data; } public int getFrequency() { return frequency; } public void setFrequency(int frequency) { this.frequency = frequency; } } private static int initialCapacity = 10; private static LinkedHashMap<Integer, CacheEntry> cacheMap = new LinkedHashMap<Integer, CacheEntry>(); /* LinkedHashMap is used because it has features of both HashMap and LinkedList. * Thus, we can get an entry in O(1) and also, we can iterate over it easily. * */ public LFUCache(int initialCapacity) { this.initialCapacity = initialCapacity; } public void addCacheEntry(int key, String data) { if(!isFull()) { CacheEntry temp = new CacheEntry(); temp.setData(data); temp.setFrequency(0); cacheMap.put(key, temp); } else { int entryKeyToBeRemoved = getLFUKey(); cacheMap.remove(entryKeyToBeRemoved); CacheEntry temp = new CacheEntry(); temp.setData(data); temp.setFrequency(0); cacheMap.put(key, temp); } } public int getLFUKey() { int key = 0; int minFreq = Integer.MAX_VALUE; for(Map.Entry<Integer, CacheEntry> entry : cacheMap.entrySet()) { if(minFreq > entry.getValue().frequency) { key = entry.getKey(); minFreq = entry.getValue().frequency; } } return key; } public String getCacheEntry(int key) { if(cacheMap.containsKey(key)) // cache hit { CacheEntry temp = cacheMap.get(key); temp.frequency++; cacheMap.put(key, temp); return temp.data; } return null; // cache miss } public static boolean isFull() { if(cacheMap.size() == initialCapacity) return true; return false; } }
https://stackoverflow.com/questions/21117636/how-to-implement-a-least-frequently-used-lfu-cache
最后
以上就是重要冬日最近收集整理的关于Least Frequently Used (LFU) LinkedHashMap的全部内容,更多相关Least内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复