The principle of

1. You need to set a fixed size for the cache

2. The cache usage time should be changed each time the cache is read.

3. When the cache is full, delete the earliest cached data and add new elements

LinkedHashMap implementation

This is a constructor for LinkedHashMap, which sorts the LinkedHashMap in accessOrder when accessOrder is true, and in insertion order when accessOrder is false, which is false by default. When accessOrder is set to true, the most recently accessed element is placed first, which satisfies the second point above.

public class LinkedHashMapLRU<K, V> {

    private final int MAX_CACHE_SIZE;

    private final floatDEFAULT_LOAD_FACTORY = 0.75 f; /** * LRU */ private LinkedHashMap<K, V> map; public LinkedHashMapLRU(int cacheSize) { this.MAX_CACHE_SIZE = cacheSize; int capacity = (int) Math.ceil(MAX_CACHE_SIZE / DEFAULT_LOAD_FACTORY) + 1; map = new LinkedHashMap<K, V>(capacity, DEFAULT_LOAD_FACTORY,true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                returnsize() > MAX_CACHE_SIZE; }}; } public synchronized void put(K key, V value) { map.put(key, value); } public synchronized V get(K key) {return map.get(key);
    }

    public synchronized void remove(K key) {
        map.remove(key);
    }

    public synchronized Set<Map.Entry<K, V>> getAll() {
        return map.entrySet();
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        for (Map.Entry<K, V> entry : map.entrySet()) {
            stringBuilder.append(String.format("%s: %s ", entry.getKey(), entry.getValue()));
        }
        returnstringBuilder.toString(); } public static void main(String[] args) { LinkedHashMapLRU<Integer, Integer> lru1 = new LinkedHashMapLRU<>(5); lru1.put(1, 1); lru1.put(2, 2); lru1.put(3, 3); System.out.println(lru1); lru1.get(1); System.out.println(lru1); lru1.put(4, 4); lru1.put(5, 5); lru1.put(6, 6); System.out.println(lru1); }}Copy the code

The results

1: 1  2: 2  3: 3  
2: 2  3: 3  1: 1  
3: 3  1: 1  4: 4  5: 5  6: 6  
Copy the code

Use a HashMap implementation

The data is placed in the head of the linked list every time the data is queried, and also in the HEAD when new data is added. LRUNode is a two-way list structure, so we define LRUNode as follows:

LRUNode.java

class LRUNode<K,V> { K key; V value; LRUNode prev; LRUNode next; public LRUNode(K key, V value) { this.key = key; this.value = value; }}Copy the code

LRUCache.java

Public class LRUCache<K, V> {/** * cache */ private HashMap<K, LRUNode<K, V>> map; /** * private int capacity; /** * private LRUNode head; /** * private LRUNode tail; /** * set cache ** @param key * @param value value */ public voidset(K key, V value) { LRUNode node = map.get(key); // If the node is not empty, update the valueif(node ! = null) { node.value = value; remove(node,false); } // If the node is empty, the node is createdelse {
            node = new LRUNode(key, value);
            if(map.size() >= capacity) {// When the capacity is insufficient, remove the most unused element first.true); } map.put(key, node); } // Set the element you just added to headsetHead(node); } /** * gets the value of the specified key ** @param key * @return
     */
    public V get(K key) {
        LRUNode<K, V> node = map.get(key);
        if(node ! = null) {// Add the element to head remove(node,false);
            setHead(node);
            return node.value;
        }
        returnnull; } /** * add elements to head ** @param node */ private voidsetHead(LRUNode node) {// Remove the element from the list firstif(head ! = null) { node.next = head; head.prev = node; } head = node;if(tail == null) { tail = node; }} /** * Remove this Node from the list, * * @param Node * @param flag */ private void remove(LRUNode Node, Boolean flag) {if(node.prev ! = null) { node.prev.next = node.next; }else {
            head = node.next;
        }
        if(node.next ! = null) { node.next.prev = node.prev; }else {
            tail = node.prev;
        }
        node.next = null;
        node.prev = null;
        if(flag) { map.remove(node.key); } } public LRUCache(int capacity) { this.capacity = capacity; this.map = new HashMap<K, LRUNode<K, V>>(); }}Copy the code