Ten lines of Java code implementation were recently used (LRU) cache

In recent interviews, I have been asked several times how to implement a least recently used (LRU) cache. The cache can be implemented with a hash table, but adding a size limit to this cache becomes another interesting issue. Now let’s see how we do that.

The collection that has used the cache least recently

To implement cache reclamation, we need to do it easily:

Linked lists can do both. To detect the least recently used item, simply return to the end of the list. To mark an item as recently used simply remove it from its current position and place the item in the header. The hard part is how to quickly find the item in the list.

Hash table help

Looking at the data structures in our toolbox, a hash table can be indexed to an object in constant time. If we create a hash table that looks like a key-> linked list node, we can find the most recently used node in constant time. What’s more, we can also determine the existence (or absence) of nodes in constant time;

Once we find this node, we can move it to the top of the list and mark it as the most recently used item.

A shortcut to Java

To my knowledge, few programming languages have a common data structure in the standard library that provides this functionality. This is a hybrid data structure, and we need to build a linked list based on the hash table. But Java already provides us with this form of data structure -LinkedHashMap! It even provides methods to override the recycle policy (see the removeEldestEntry documentation). The only thing we need to note is that the list is changed in the order of insertion, not access. However, one constructor provides an option to use the order of access (see documentation).

Needless to say:

import java.util.LinkedHashMap; import java.util.Map; public LRUCache extends LinkedHashMap { private int cacheSize; Public LRUCache(int cacheSize) {super(16, 0.75, true); this.cacheSize = cacheSize; } protected boolean removeEldestEntry(Map.Entry eldest) { return size() >= cacheSize; }}

Original link:
ChriswuTranslation:
ImportNew.com –
paddx


Translation link:
www.importnew.com/16264.html


[
Please keep the source, translator and translation link for reprinting.]