How to implement a Least Frequently Used (LFU) cache?

Question

Least Frequently Used (LFU) is a type of cache algorithm used to manage memory within a computer. The standard characteristics of this method involve the system keeping track of the number of times a block is referenced in memory. When the cache is full and requires more room the system will purge the item with the lowest reference frequency.

What would be the best way to implement a most-recently-used cache of objects, say in Java?

I've already implemented one using LinkedHashMap(by maintaining the no. of times objects are accessed) But I'm curious if any of the new concurrent collections would be better candidates.

Consider this case : Suppose cache is full and we need to make space for another one. Say two objects are noted in cache which are accessed for one time only. Which one to remove if we come to know that other(which is not in cache)object is being accessed for more than once ?

Thanks!

Answer 1

You might benefit from the LFU implementation of ActiveMQ: LFUCache

They have provided some good functionality.