I have the following implementation of an LFU - least frequently used - cache. In case there is a tie between elements which have the same use count then the timestamp is used as a tie breaker to evict the least recently used element
public class LFUCache {
class CacheKey {
private int counter;
private long timestamp;
private int value;
public CacheKey(int counter, long timestamp, int value) {
this.counter = counter;
this.timestamp = timestamp;
this.value = value;
}
long getTimestamp() {
return this.timestamp;
}
int getCounter() {
return this.counter;
}
void incrementCounter() {
this.counter++;
}
void setTimestamp(long timestamp) {
this.timestamp = timestamp;
}
void setValue(int value) {
this.value = value;
}
public boolean equals(Object o) {
CacheKey other = (CacheKey) o;
return other.counter == this.counter && other.timestamp == this.timestamp && this.value == other.value;
}
public int hashCode() {
return Objects.hash(this.counter, this.timestamp, this.value);
}
@Override
public String toString() {
return "CacheKey{" +
"counter=" + counter +
", timestamp=" + timestamp +
", value=" + value +
'}';
}
}
/**
* Map from cache key to its corresponding key
*/
TreeMap<CacheKey, Integer> timeKeeper;
/**
* Map from keys to the keys of th timekeeper map
*/
Map<Integer, CacheKey> cache;
/**
* Total capacity of the cache
*/
int capacity;
/**
* Compare first on the least frequently used, so we are keeping the elements of the cache with the smallest
* counters in the first entries of the tree map.
* <p>
* In case of a tie we have to evict the least recently used, so we are using the timestamp entry, and we are keeping
* the ones with the smaller
*/
public LFUCache(int capacity) {
this.timeKeeper = new TreeMap(Comparator.comparingInt(CacheKey::getCounter).thenComparingLong(CacheKey::getTimestamp));
this.cache = new HashMap();
this.capacity = capacity;
}
public int get(int key) {
if (this.cache.containsKey(key)) {
CacheKey searchKey = this.cache.get(key);
// We have to remove the old entry from the timekeeper map and re add it to the tree map
// since if we update only the reference the sorting will not take place again
this.timeKeeper.remove(searchKey);
// Update the entry in the timekeeper map with an updated counter and a new last used timestamp
searchKey.incrementCounter();
searchKey.setTimestamp(System.currentTimeMillis());
this.timeKeeper.put(searchKey, key);
return this.cache.get(key).value;
} else return -1;
}
public void put(int key, int value) {
// Check if we have to remove something from the map
if (this.cache.size() == this.capacity) {
// Remove the least frequently used OR - in case of a tie - least recently used element
Map.Entry<CacheKey, Integer> lfuEntry = this.timeKeeper.pollFirstEntry();
CacheKey lfuKey = lfuEntry.getKey();
Integer lfuValue = lfuEntry.getValue();
// Remove elements from both cache and timekeeper
this.timeKeeper.remove(lfuKey);
this.cache.remove(lfuValue);
}
// Check if it is present
if (this.cache.containsKey(key)) {
CacheKey searchKey = this.cache.get(key);
// Remove the old entry from the timekeeper map. Again here we remove the old entry from the timekeeper map
// and re add it to the tree map since if we update only the reference the sorting will not take place
this.timeKeeper.remove(searchKey);
// Update the entry in the timekeeper map with an updated counter and a new last used timestamp
searchKey.incrementCounter();
searchKey.setTimestamp(System.currentTimeMillis());
searchKey.setValue(value);
this.timeKeeper.put(searchKey, key);
this.cache.put(key, searchKey);
} else {
// Now add the new element
doPut(key, value);
}
}
private void doPut(int key, int value) {
CacheKey cacheKey = new CacheKey(1, System.currentTimeMillis(), value);
this.timeKeeper.put(cacheKey, key);
this.cache.put(key, cacheKey);
}
}
I have the following test to verify that everything is working as expected
public static void main(String[] args) {
LFUCache lfuCache = new LFUCache(2);
lfuCache.put(1, 1);
lfuCache.put(2, 2);
System.out.println(lfuCache.get(1));
lfuCache.put(3, 3);
System.out.println(lfuCache.get(2));
System.out.println(lfuCache.get(3));
lfuCache.put(4, 4);
System.out.println(lfuCache.get(1));
System.out.println(lfuCache.get(3));
System.out.println(lfuCache.get(4));
}
The results I am getting are random. I would expect to get
1
-1
3
-1
3
4
and I do get this sometimes but I also get
1
2
3
-1
3
4
or
1
-1
3
-1
3
4
and all sorts of other results. I tried to create synchronized methods
public synchronized int get(int key) {...}
public synchronized void put(int key, int value) {...}
and I still get random results I tried to synchronize blocks inside methods e.g.
public int get(int key) {
if (this.cache.containsKey(key)) {
synchronized(this){
CacheKey searchKey = this.cache.get(key);
// Remove the old entry from the timekeeper map
this.timeKeeper.remove(searchKey);
// Create a new entry in the timekeeper map with an updated counter and a new last used timestamp
CacheKey updatedKey = new CacheKey(searchKey.getCounter() + 1, System.currentTimeMillis(), searchKey.value);
this.timeKeeper.put(updatedKey, key);
return this.cache.get(key).value;
}
} else return -1;
}
I still get random results
I tried to synchronized on the timeKeeper and cache objects e.g.
public int get(int key) {
if (this.cache.containsKey(key)) {
synchronized(this.timeKeeper){
synchronized(this.cache){
CacheKey searchKey = this.cache.get(key);
// Remove the old entry from the timekeeper map
this.timeKeeper.remove(searchKey);
// Create a new entry in the timekeeper map with an updated counter and a new last used timestamp
CacheKey updatedKey = new CacheKey(searchKey.getCounter() + 1, System.currentTimeMillis(), searchKey.value);
this.timeKeeper.put(updatedKey, key);
return this.cache.get(key).value;
}
}
} else return -1;
}
but I still get random results
I also tried to use a SyncronizedMap instead of a HashMap but I still get random results.
I cannot really use Collections.synchronizedMap(TreeMap) because this will yield a Map and I cannot use the TreeMap API on it.
So what other options do I have here?
This is a single threaded environment. It's just a main method. How can I have random results being produced?
