FLU Cache

In this blogpost we will se how we can implement a LFU cache in Java.

package com.test.lfucache;

public class CacheEntry<T> {

private T data;

private int frequency;

public CacheEntry() {

}

public CacheEntry(T data, int frequency) {

super();

this.data = data;

this.frequency = frequency;

}

public T getData() {

return data;

}

public void setData(T data) {

this.data = data;

}

public int getFrequency() {

return frequency;

}

public void setFrequency(int frequency) {

this.frequency = frequency;

}

}

The above class represents the cache entry. Each entry has a frequency associated with it which will help us evicting cache object.

package com.test.lfucache;

import java.util.LinkedHashMap;

import java.util.Map;

public class LFUCache<K,V> {

private int maxSize = 10;

private Map<K, CacheEntry<V>> cacheMap;

public LFUCache(int maxSize) {

this.maxSize = maxSize;

cacheMap = new LinkedHashMap<>();

}

public void putCacheEntry(K key, V value) {

if (isFull()) {

K cacheKey = evictCache();

cacheMap.remove(cacheKey);

}

CacheEntry<V> entry = new CacheEntry<>();

entry.setData(value);

entry.setFrequency(0);

cacheMap.put(key, entry);

}

public V getCacheEntry(K key) {

if (cacheMap.containsKey(key)) {

CacheEntry<V> temp = cacheMap.get(key);

temp.setFrequency(temp.getFrequency() + 1);

cacheMap.put(key, temp);

return temp.getData();

}

return null;

}

private boolean isFull() {

return cacheMap.size() == maxSize ? true : false;

}

private K evictCache() {

int minFrequency = Integer.MAX_VALUE;

K key = null;

for (Map.Entry<K, CacheEntry<V>> entry : cacheMap.entrySet()) {

if (entry.getValue().getFrequency() < minFrequency) {

key = entry.getKey();

}

}

return key;

}

}

The above class is the main cache class. We have used a LinkedHashMap to store key and cache entry. We can use ConcurrentHashMap also for storing the key and cache entry. Finally the main class looks like

package com.test.lfucache;

public class MainClass {

public static void main(String[] args) {

LFUCache<String, String> cache = new LFUCache<>(3);

cache.putCacheEntry("1", "One");

cache.putCacheEntry("2", "Two");

cache.putCacheEntry("3", "Three");

System.out.println(cache.getCacheEntry("1"));

System.out.println(cache.getCacheEntry("2"));

cache.putCacheEntry("4", "Four");

System.out.println(cache.getCacheEntry("3"));

System.out.println(cache.getCacheEntry("4"));

}

}

Output :

One

Two

null

Four

The above LFU cache has an O(n) runtime complexity for eviction so worst case data insertion into cache. We can improve the performance with the help of another Map and LinkedList.