-
Notifications
You must be signed in to change notification settings - Fork 0
/
LFUCache.java
103 lines (86 loc) · 2.78 KB
/
LFUCache.java
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
102
103
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Map;
class LFUCache {
private static class Node {
private int value;
private int freq;
Node(int value, int freq) {
this.value = value;
this.freq = freq;
}
void setValue(int value) {
this.value = value;
}
void access() {
freq += 1;
}
}
private final int capacity;
private final Map<Integer, Node> keyToNode;
private final Map<Integer, LinkedHashSet<Integer>> countToLRUKeySet;
private int lowestFrequency;
public LFUCache(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("Capacity must be >= 0");
}
this.capacity = capacity;
this.countToLRUKeySet = new HashMap<>();
this.keyToNode = new HashMap<>((int) Math.ceil(capacity * 3 / 4));
this.lowestFrequency = 1;
}
public int get(int key) {
Node node = keyToNode.get(key);
if (node == null) {
return -1;
}
access(key, node);
return node.value;
}
public void put(int key, int value) {
if (capacity == 0) {
return;
} else if (keyToNode.containsKey(key)) {
Node node = keyToNode.get(key);
access(key, node);
node.setValue(value);
return;
} else if (keyToNode.size() == capacity) {
evictLeastFrequentlyLeastRecentlyUsedKey();
}
lowestFrequency = 1;
countToLRUKeySet.computeIfAbsent(lowestFrequency, LFUCache::createLRU).add(key);
keyToNode.put(key, new Node(value, lowestFrequency));
}
private void access(int key, Node node) {
LinkedHashSet<Integer> set = countToLRUKeySet.get(node.freq);
set.remove(key);
if (set.isEmpty()) {
countToLRUKeySet.remove(node.freq);
if (lowestFrequency == node.freq) {
lowestFrequency = node.freq + 1;
}
}
node.access();
countToLRUKeySet.computeIfAbsent(node.freq, LFUCache::createLRU).add(key);
}
private void evictLeastFrequentlyLeastRecentlyUsedKey() {
LinkedHashSet<Integer> set = countToLRUKeySet.get(lowestFrequency);
Iterator<Integer> toRemove = set.iterator();
keyToNode.remove(toRemove.next());
toRemove.remove();
if (set.isEmpty()) {
countToLRUKeySet.remove(lowestFrequency);
}
}
private static LinkedHashSet<Integer> createLRU(int i) {
return new LinkedHashSet<>();
}
}
/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache obj = new LFUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/