LRU cache design - PrismoSkills
LRU stands for Least Recently Used.
Idea behind such a cache is that it evicts least recently used entries when number of entries put into it exceed the max capacity.
Clearly, some kind of a map is a must for any cache to enable fast look-ups.
Along with that, we need some other data-structure which is able to identify least recently used entries and remove them when required.
When an entry is put, it must be put in the beginning of some list and if that list exceeds the given limit, its last entry should be removed.
A map and a list => both come together in a LinkedHashMap
To do really nothing, one can also override removeEldestEntry(java.util.Map.Entry) method in LinkedHashMap and get LRU out of the box.
Read full article from LRU cache design - PrismoSkills
LRU stands for Least Recently Used.
Idea behind such a cache is that it evicts least recently used entries when number of entries put into it exceed the max capacity.
Clearly, some kind of a map is a must for any cache to enable fast look-ups.
Along with that, we need some other data-structure which is able to identify least recently used entries and remove them when required.
When an entry is put, it must be put in the beginning of some list and if that list exceeds the given limit, its last entry should be removed.
A map and a list => both come together in a LinkedHashMap
To do really nothing, one can also override removeEldestEntry(java.util.Map.Entry) method in LinkedHashMap and get LRU out of the box.
Read full article from LRU cache design - PrismoSkills