在本教程中，我们将在Java中看到LRU缓存实现。

问题

在Java中设计最近使用最近使用的缓存实现。
它应该有以下属性。
bounded size:它应该有界大小来照顾记忆范围。
Fast access:在我们设计缓存时，我们应该能够更快地获取或者更新条目。
Evict least recently used entry:缓存应拒绝最近最近使用的条目如果达到容量。

解决方案

使用HashMap和双链接列表

我们需要做查询 O(1)然后，Hashmap是显而易见的选择，但我们也需要照顾最近的最近使用的条目。

如果我们已经知道节点，我们需要找到一个数据结构，该数据结构可以在O(1)时间内删除/添加。
我们可以为此目的使用双重链接列表，因为如果已经了解节点，它会在O(1)时间内提供删除/添加。

HashMap将获得操作 O(1) time和 Doube linked list将删除/加入 O(1) time。

这是Java中LRU缓存实现的简单程序。

package org.igi.theitroad;
 
import java.util.HashMap;
 
class Node{
	int key;
	int value;
	Node prev;
	Node next;
 
	public Node(int key, int value){
		this.key = key;
		this.value = value;
	}
}
public class LRUCache {
	int capacity;
	HashMap<Integer, Node> map = new HashMap<Integer, Node>();
	Node head=null;
	Node end=null;
 
	public LRUCache(int capacity) {
		this.capacity = capacity;
	}
 
	public int get(int key) {
		if(map.containsKey(key)){
			Node n = map.get(key);
			delete(n);
			setHead(n);
			return n.value;
		}
 
		return -1;
	}
 
	/*This method will delete node*/
	public void delete(Node node){
		if(node.prev!=null){
			node.prev.next = node.next;
		}else{
			head = node.next;
		}
 
		if(node.next!=null){
			node.next.prev = node.prev;
		}else{
			end = node.prev;
		}
 
	}
 
	/*This method will make passed node as head*/
	public void setHead(Node node){
		node.next = head;
		node.prev = null;
 
		if(head!=null)
			head.prev = node;
 
		head = node;
 
		if(end ==null)
			end = head;
	}
 
	public void set(int key, int value) {
		if(map.containsKey(key)){
			//update the old value
			Node old = map.get(key);
			old.value = value;
			delete(old);
			setHead(old);
		}else{
			Node newNode = new Node(key, value);
			if(map.size()>=capacity){
				
				map.remove(end.key);
				//remove last node
				delete(end);
				setHead(newNode);
 
			}else{
				setHead(newNode);
			}    
 
			map.put(key, newNode);
		}
	}	
	
	public static void main(String[] args) throws java.lang.Exception {
		LRUCache lrucache = new LRUCache(4);
		lrucache.set(1, 100);
		lrucache.set(10, 99);
		lrucache.set(15, 98);
		lrucache.set(10, 97);
		lrucache.set(12, 96);
		lrucache.set(18, 95);
		lrucache.set(1, 94);
 
		System.out.println(lrucache.get(1));
		System.out.println(lrucache.get(10));
		System.out.println(lrucache.get(15));
 
	}
}

运行上面的程序时，我们将得到以下输出：

94
97
-1

正如我们所看到的，在过去的4个条目中，我们没有 15作为关键。
这是我们获得的原因 -1为了它。

使用linkedhashmap.

我们可以使用LinkedHashMap创建LRU缓存。

LinkedHashMap有一个构造函数，我们可以其中指定访问顺序。

如果你通过了 accessOrder作为真，LinkedHashMap将基于访问订单而不是插入顺序工作。

/**
     * Constructs an empty <tt>LinkedHashMap</tt> instance with the
     * specified initial capacity, load factor and ordering mode.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @param  accessOrder     the ordering mode - <tt>true</tt> for
     *         access-order, <tt>false</tt> for insertion-order
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

我们还将覆盖命名的方法 removeEldestEntry()它会返回 true以防万一 size()大于 capacity。

让我们创建一个名为的程序 LRUCache

package org.igi.theitroad;
import java.util.LinkedHashMap; 
import java.util.Map; 
  
class LRUCache { 
    private LinkedHashMap<Integer, Integer> cacheMap; 
    public LRUCache(int capacity) 
    { 
        cacheMap = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) { 
            protected boolean removeEldestEntry(Map.Entry eldest) 
            { 
                return size() > capacity; 
            } 
        }; 
    } 
  
    //This method works in O(1) 
    public int get(int key) 
    { 
        return cacheMap.getOrDefault(key, -1); 
    } 
  
    //This method works in O(1) 
    public void set(int key, int value) 
    { 
        cacheMap.put(key, value); 
    } 
} 
  
public class LRUUsingLinkedHashMapMain { 
  
    public static void main(String[] args) 
    { 
    	LRUCache lrucache = new LRUCache(4);
		lrucache.set(1, 100);
		lrucache.set(10, 99);
		lrucache.set(15, 98);
		lrucache.set(10, 97);
		lrucache.set(12, 96);
		lrucache.set(18, 95);
		lrucache.set(1, 94);
 
		System.out.println(lrucache.get(1));
		System.out.println(lrucache.get(10));
		System.out.println(lrucache.get(15));
  
    } 
}

如您所见，在最后4个条目中，我们没有键“ 15”。 这就是我们为此得到-1的原因。