LFU cache in O(1) in Java

LFU cache is nothing but removing least frequently used item from the cache to put the new data into the cache. Most of the solution outside is not O(1). Here is a research paper to make it possible. Requirements are to put(K, V) and get(K) is to be done in O(1).

To put and get data in Java in O(1), We need to use Map or more specifically HashMap.

• HashMap<K, V>

Since we need to find the least frequently used item to remove it for putting new data, we need a counter to keep track number of times a Key(K) has been accessed. Access could get or put. To achieve that we need another Map<K, C>; K is the key of the item to put and C is the counter.

• HashMap<K, C>

From the above two data structure, we can put and get data in O(1). We can also get the counter of an item has been used.

Another thing, we need, is a list where we can store the information of count and items key. Lets elaborate that in details, assume A has been used 5times, B also has been used 5times. We need to store that information such a way that will hold the items in a list based on their insertion order. (FIFO). To achieve that we can use HashSet<K> and more precisely LinkedHashSet<K>. But we want to keep track of the counter as well(in our example 5 times or 5). So we need another map.