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 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169
| public class LFUCache {
private final Map cache;
private final LinkedHashSet[] frequencyList;
private int lowestFrequency;
private int maxFrequency;
private final int maxCacheSize;
// @param capacity, an integer
public LFUCache(int capacity) {
// Write your code here
this.cache = new HashMap(capacity);
this.frequencyList = new LinkedHashSet[capacity * 2];
this.lowestFrequency = 0;
this.maxFrequency = capacity * 2 - 1;
this.maxCacheSize = capacity;
initFrequencyList();
}
// @param key, an integer
// @param value, an integer
// @return nothing
public void set(int key, int value) {
// Write your code here
CacheNode currentNode = cache.get(key);
if (currentNode == null) {
if (cache.size() == maxCacheSize) {
doEviction();
}
LinkedHashSet nodes = frequencyList[0];
currentNode = new CacheNode(key, value, 0);
nodes.add(currentNode);
cache.put(key, currentNode);
lowestFrequency = 0;
} else {
currentNode.v = value;
}
addFrequency(currentNode);
}
public int get(int key) {
// Write your code here
CacheNode currentNode = cache.get(key);
if (currentNode != null) {
addFrequency(currentNode);
return currentNode.v;
} else {
return -1;
}
}
public void addFrequency(CacheNode currentNode) {
int currentFrequency = currentNode.frequency;
if (currentFrequency int nextFrequency = currentFrequency + 1;
LinkedHashSet currentNodes = frequencyList[currentFrequency];
LinkedHashSet newNodes = frequencyList[nextFrequency];
moveToNextFrequency(currentNode, nextFrequency, currentNodes, newNodes);
cache.put(currentNode.k, currentNode);
if (lowestFrequency == currentFrequency && currentNodes.isEmpty()) {
lowestFrequency = nextFrequency;
}
} else {
// Hybrid with LRU: put most recently accessed ahead of others:
LinkedHashSet nodes = frequencyList[currentFrequency];
nodes.remove(currentNode);
nodes.add(currentNode);
}
}
public int remove(int key) {
CacheNode currentNode = cache.remove(key);
if (currentNode != null) {
LinkedHashSet nodes = frequencyList[currentNode.frequency];
nodes.remove(currentNode);
if (lowestFrequency == currentNode.frequency) {
findNextLowestFrequency();
}
return currentNode.v;
} else {
return -1;
}
}
public int frequencyOf(int key) {
CacheNode node = cache.get(key);
if (node != null) {
return node.frequency + 1;
} else {
return 0;
}
}
public void clear() {
for (int i = 0; i <= maxFrequency; i++) {
frequencyList[i].clear();
}
cache.clear();
lowestFrequency = 0;
}
public int size() {
return cache.size();
}
public boolean isEmpty() {
return this.cache.isEmpty();
}
public boolean containsKey(int key) {
return this.cache.containsKey(key);
}
private void initFrequencyList() {
for (int i = 0; i <= maxFrequency; i++) {
frequencyList[i] = new LinkedHashSet();
}
}
private void doEviction() {
int currentlyDeleted = 0;
double target = 1; // just one
while (currentlyDeleted LinkedHashSet nodes = frequencyList[lowestFrequency];
if (nodes.isEmpty()) {
break;
} else {
Iterator it = nodes.iterator();
while (it.hasNext() && currentlyDeleted++ CacheNode node = it.next();
it.remove();
cache.remove(node.k);
}
if (!it.hasNext()) {
findNextLowestFrequency();
}
}
}
}
private void moveToNextFrequency(CacheNode currentNode, int nextFrequency,
LinkedHashSet currentNodes,
LinkedHashSet newNodes) {
currentNodes.remove(currentNode);
newNodes.add(currentNode);
currentNode.frequency = nextFrequency;
}
private void findNextLowestFrequency() {
while (lowestFrequency <= maxFrequency && frequencyList[lowestFrequency].isEmpty()) {
lowestFrequency++;
}
if (lowestFrequency > maxFrequency) {
lowestFrequency = 0;
}
}
private class CacheNode {
public final int k;
public int v;
public int frequency;
public CacheNode(int k, int v, int frequency) {
this.k = k;
this.v = v;
this.frequency = frequency;
}
}
} |