带有泛型和 O(1) 操作的 Java 中的 LRU 缓存

LRU cache in Java with Generics and O(1) operations

提问by liarspocker

This is a question that comes up a lot in job interviews. The idea is to define a data structure instead of using Java's built in LinkedHashMap.

这是求职面试中经常出现的问题。这个想法是定义一个数据结构，而不是使用 Java 内置的 LinkedHashMap。

An LRU cache deletes the least recently usedentry to insert a new one. So, given the following scenario:

LRU 缓存删除最近最少使用的条目以插入新条目。因此，鉴于以下场景：

 A - B - C - D - E

Where A is the least recently used item, if we were to insert F, we need to remove A.

其中 A 是最近最少使用的项目，如果我们要插入 F，我们需要删除 A。

This can be easily implemented if we keep a HashMap with the cache entries by (key,value) and a separate list that contains the elements' key and time of use. However, we would need to query the list to find the least recently used item, with a potential O(n) time complexity.

如果我们通过 (key,value) 保留一个带有缓存条目的 HashMap 和一个包含元素的键和使用时间的单独列表，这可以很容易地实现。但是，我们需要查询列表以找到最近最少使用的项目，时间复杂度为 O(n)。

How can this structure be implemented in Java for Generic objects and O(1) operations?

如何在 Java 中为泛型对象和 O(1) 操作实现这种结构？

This is different from the possible duplicate in that it focuses on efficiency (O(1) ops) and implementing the data structure itself, not extending Java's.

这与可能的重复不同，因为它侧重于效率（O(1) 操作）和实现数据结构本身，而不是扩展 Java 的。

采纳答案by liarspocker

From the question itself, we can see that the problem of O(n) operations arises when querying the linked list. Therefore, we need an alternative data structure. We need to be able to update the items' last access time from the HashMap without searching.

从问题本身可以看出，查询链表时出现了O(n)运算的问题。因此，我们需要一种替代的数据结构。我们需要能够在不搜索的情况下从 HashMap 更新项目的最后访问时间。

We can keep two separate data structures. A HashMap with (Key,Pointer)pairs and a doubly linked listwhich will work as the priority queue for deletion and store the Values. From the HashMap, we can point to an element in the doubly linked list and update its' retrieval time. Because we go directly from the HashMap to the item in the list, our time complexity remains at O(1)

我们可以保留两个独立的数据结构。带有 (Key,Pointer)对和双向链表的HashMap将用作删除和存储值的优先级队列。从 HashMap 中，我们可以指向双向链表中的一个元素并更新其检索时间。因为我们直接从 HashMap 到列表中的项目，所以我们的时间复杂度保持在 O(1)

For example, our doubly linked list can look like:

例如，我们的双向链表可以是这样的：

least_recently_used  -> A <-> B <-> C <-> D <-> E <- most_recently_used

We need to keep a pointer to the LRU and MRU items. The entries' values will be stored in the list and when we query the HashMap, we will get a pointer to the list. On get(), we need to put the item at the right-most side of the list. On put(key,value), if the cache is full, we need to remove the item at the left-most side of the list from both, the list and the HashMap.

我们需要保留一个指向 LRU 和 MRU 项的指针。条目的值将存储在列表中，当我们查询 HashMap 时，我们将获得一个指向列表的指针。在 get() 上，我们需要将项目放在列表的最右侧。在 put(key,value) 上，如果缓存已满，我们需要从列表和 HashMap 中删除列表最左侧的项目。

The following is an example implementation in Java:

以下是 Java 中的示例实现：

public class LRUCache<K, V>{

    // Define Node with pointers to the previous and next items and a key, value pair
    class Node<T, U> {
        Node<T, U> previous;
        Node<T, U> next;
        T key;
        U value;

        public Node(Node<T, U> previous, Node<T, U> next, T key, U value){
            this.previous = previous;
            this.next = next;
            this.key = key;
            this.value = value;
        }
    }

    private HashMap<K, Node<K, V>> cache;
    private Node<K, V> leastRecentlyUsed;
    private Node<K, V> mostRecentlyUsed;
    private int maxSize;
    private int currentSize;

    public LRUCache(int maxSize){
        this.maxSize = maxSize;
        this.currentSize = 0;
        leastRecentlyUsed = new Node<K, V>(null, null, null, null);
        mostRecentlyUsed = leastRecentlyUsed;
        cache = new HashMap<K, Node<K, V>>();
    }

    public V get(K key){
        Node<K, V> tempNode = cache.get(key);
        if (tempNode == null){
            return null;
        }
        // If MRU leave the list as it is
        else if (tempNode.key == mostRecentlyUsed.key){
            return mostRecentlyUsed.value;
        }

        // Get the next and previous nodes
        Node<K, V> nextNode = tempNode.next;
        Node<K, V> previousNode = tempNode.previous;

        // If at the left-most, we update LRU 
        if (tempNode.key == leastRecentlyUsed.key){
            nextNode.previous = null;
            leastRecentlyUsed = nextNode;
        }

        // If we are in the middle, we need to update the items before and after our item
        else if (tempNode.key != mostRecentlyUsed.key){
            previousNode.next = nextNode;
            nextNode.previous = previousNode;
        }

        // Finally move our item to the MRU
        tempNode.previous = mostRecentlyUsed;
        mostRecentlyUsed.next = tempNode;
        mostRecentlyUsed = tempNode;
        mostRecentlyUsed.next = null;

        return tempNode.value;

    }

    public void put(K key, V value){
        if (cache.containsKey(key)){
            return;
        }

        // Put the new node at the right-most end of the linked-list
        Node<K, V> myNode = new Node<K, V>(mostRecentlyUsed, null, key, value);
        mostRecentlyUsed.next = myNode;
        cache.put(key, myNode);
        mostRecentlyUsed = myNode;

        // Delete the left-most entry and update the LRU pointer
        if (currentSize == maxSize){
            cache.remove(leastRecentlyUsed.key);
            leastRecentlyUsed = leastRecentlyUsed.next;
            leastRecentlyUsed.previous = null;
        }

        // Update cache size, for the first added entry update the LRU pointer
        else if (currentSize < maxSize){
            if (currentSize == 0){
                leastRecentlyUsed = myNode;
            }
            currentSize++;
        }
    }
}

回答by Venkat Kondeti

Idea

主意

cache is nothing but circular arrayList. This list contains Entry. when ever new entries are coming add at the end of the list. That means least recently used element at the first. Suppose if you are reusing any element then unlink from the list and add at the end.

缓存只不过是循环数组列表。此列表包含条目。当有新条目出现时，将其添加到列表末尾。这意味着首先使用最近最少使用的元素。假设如果您要重用任何元素，则从列表中取消链接并在最后添加。

In order get any element we need to traverse the list which takes O(n) time complexity. In order to avoid this i'm maintaining HashMap>. Here k is key and IndexNode will contain a pointer to the Entry in the list. so we can get the O(1) time complexity.

为了获得任何元素，我们需要遍历需要 O(n) 时间复杂度的列表。为了避免这种情况，我正在维护 HashMap>。这里 k 是键，IndexNode 将包含一个指向列表中条目的指针。所以我们可以得到 O(1) 的时间复杂度。

working solution

工作解决方案

package lrucache;

import java.util.HashMap;

public class LRUCache<K, V> {

    private transient Entry<K, V> header = new Entry<K, V>(null, null, null, null);
    public HashMap<K,IndexNode<Entry<K,V>>> indexMap = new HashMap<K,IndexNode<Entry<K,V>>>();
    private final int CACHE_LIMIT = 3;
    private int size;

    public LRUCache() {
        header.next = header.previous = header;
        this.size = 0;
    }

    public void put(K key,V value){
        Entry<K,V> newEntry = new Entry<K,V>(key,value,null,null);
        addBefore(newEntry, header);
    }

    private void addBefore(Entry<K,V> newEntry,Entry<K,V> entry){
        if((size+1)<(CACHE_LIMIT+1)){
            newEntry.next=entry;
            newEntry.previous=entry.previous;
            IndexNode<Entry<K,V>> indexNode = new IndexNode<Entry<K,V>>(newEntry);
            indexMap.put(newEntry.key, indexNode);
            newEntry.previous.next=newEntry;
            newEntry.next.previous=newEntry;
            size++;
        }else{
            Entry<K,V>  entryRemoved = remove(header.next);
            indexMap.remove(entryRemoved.key);
            addBefore(newEntry, entry);
        }
    }

    public void get(K key){
        if(indexMap.containsKey(key)){
            Entry<K,V> newEntry = remove(indexMap.get(key).pointer);
            addBefore(newEntry,header);
        }else{
            System.out.println("No such element was cached. Go and get it from Disk");
        }
    }

    private Entry<K,V> remove(Entry<K,V> entry){
        entry.previous.next=entry.next;
        entry.next.previous = entry.previous;
        size--;
        return entry;
    }

    public void display(){
        for(Entry<K,V> curr=header.next;curr!=header;curr=curr.next){
            System.out.println("key : "+curr.key+" value : " + curr.value);
        }
    }

    private static class IndexNode<Entry>{
        private Entry pointer;
        public IndexNode(Entry pointer){
            this.pointer = pointer;
        }
    }

    private static class Entry<K, V> {
        K key;
        V value;
        Entry<K, V> previous;
        Entry<K, V> next;

        Entry(K key, V value, Entry<K, V> next, Entry<K, V> previous) {
            this.key = key;
            this.value = value;
            this.next = next;
            this.previous = previous;
        }
    }

    public static void main(String[] args) {
        LRUCache<String, Integer> cache = new LRUCache<String, Integer>();
        cache.put("abc", 1);
        //cache.display();
        cache.put("def", 2);
        cache.put("ghi", 3);
        cache.put("xyz", 4);
        cache.put("xab", 5);
        cache.put("xbc", 6);
        cache.get("xyz");
        cache.display();
        System.out.println(cache.indexMap);
    }
}

output

输出

key : xab value : 5
key : xbc value : 6
key : xyz value : 4
{xab=lrucache.LRUCache$IndexNode@c3d9ac, xbc=lrucache.LRUCache$IndexNode@7d8bb, xyz=lrucache.LRUCache$IndexNode@125ee71}

回答by Prashant Gautam

we can use LinkedHashMap .. it has feature to remove the eldest entry

我们可以使用 LinkedHashMap .. 它具有删除最旧条目的功能

import java.util.LinkedHashMap;
import java.util.Map;

public LRUCache<K, V> extends LinkedHashMap<K, V> {
  private int cacheSize;

  public LRUCache(int cacheSize) {
  super(16, 0.75, true);
  this.cacheSize = cacheSize;
}

  protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
  return size() >= cacheSize;
 }
}

The only catch is that by default the linked list order is the insertion order, not access. However one of the constructor exposes an option use the access order instead.

唯一的问题是默认情况下，链表顺序是插入顺序，而不是访问顺序。然而，其中一个构造函数公开了一个选项，而是使用访问顺序。

回答by craftsmannadeem

Here is the java implementation

这是java实现

import java.util.HashMap;
import java.util.Map;

import com.nadeem.app.dsa.adt.Cache;
// Kind of linkedHashMap
public class LRUCache <K, V> implements Cache<K, V> {

private int capacity;
private Node<K, V> head, tail;
private Map<K, Node<K, V>> map;

private static final int DEFAULT_CAPACITY = 10;

public LRUCache(int capacity) {
    this.capacity = capacity;
    this.map = new HashMap<K, Node<K,V>>();
}

public LRUCache() {
    this(DEFAULT_CAPACITY);
}

@Override
public V get(K key) {
    V result = null;
    Node<K, V> node = this.map.get(key);
    if (node != null) {
        result = node.value;
        remove(node);
        addAsHead(node);
    }
    return result;
}

@Override
public void set(K key, V value) {
    Node<K, V> node = this.map.get(key);
    if (node == null) {
        Node<K, V> temp = new Node<K, V>(key, value);
        if (this.map.size() < this.capacity) {
            addAsHead(temp);
        } else {
            this.map.remove(this.tail.key);
            remove(this.tail);
            addAsHead(temp);
        }
        this.map.put(key, temp);
    } else {
        node.value = value;
        remove(node);
        addAsHead(node);
    }
}

private void remove(Node<K, V> node) {

    if (node.pre == null) {
        this.head = node.next;
    } else {
        node.pre.next = node.next;
    }

    if (node.next == null) {
        this.tail = node.pre;
    } else {
        node.next.pre = node.pre;
    }       
}

private void addAsHead(Node<K, V> node) {
    if (this.head == null) {
        this.head = node;
        this.tail = node;
    } else {
        this.head.pre = node;
        node.next = this.head;
        this.head = node;
    }
}

@Override
public void remove(K key) {
    Node<K, V> node = this.map.get(key);
    if (node != null) {
        this.remove(node);
    }       
}

private static class Node <S, T> {
    public S key;
    public T value;
    Node<S, T> pre;
    Node<S, T> next;

    Node(S key, T value) {
        this.key = key;
        this.value = value;
    }       
}

@Override
public int size() {
    return this.map.size();
}

}

}

Here is the unit test

这是单元测试

public class LRUCacheTest {

private LRUCache<Integer, Integer> cache;

@Before
public void doBeforeEachTestCase() {
    this.cache = new LRUCache<Integer, Integer>(2);
}

@Test
public void setTest() {
    this.cache.set(1, 1);
    assertThat(this.cache.size(), equalTo(1));
    assertThat(this.cache.get(1), equalTo(1));

    this.cache.set(2, 2);
    assertThat(this.cache.size(), equalTo(2));
    assertThat(this.cache.get(2), equalTo(2));

    this.cache.set(3, 3);
    assertThat(this.cache.size(), equalTo(2));
    assertThat(this.cache.get(3), equalTo(3));

    this.cache.set(1, 3);
    assertThat(this.cache.size(), equalTo(2));
    assertThat(this.cache.get(1), equalTo(3));

    assertThat(this.cache.get(4), equalTo(null));
}

}

}

回答by K''

The LinkedHashMapdesigned with that in mind

该LinkedHashMap的设计考虑到这一点

From the javadocs:

从javadocs：

A special constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order). This kind of map is well-suited to building LRU caches. Invoking the put, putIfAbsent, get, getOrDefault, compute, computeIfAbsent, computeIfPresent, or merge methods results in an access to the corresponding entry (assuming it exists after the invocation completes). The replace methods only result in an access of the entry if the value is replaced. The putAll method generates one entry access for each mapping in the specified map, in the order that key-value mappings are provided by the specified map's entry set iterator. No other methods generate entry accesses. In particular, operations on collection-views do not affect the order of iteration of the backing map.

The removeEldestEntry(Map.Entry) method may be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map.

提供了一个特殊的构造函数来创建一个链接的哈希映射，其迭代顺序是其条目上次访问的顺序，从最近最少访问到最近（访问顺序）。这种映射非常适合构建 LRU 缓存。调用 put、putIfAbsent、get、getOrDefault、compute、computeIfAbsent、computeIfPresent 或 merge 方法会导致对相应条目的访问（假设它在调用完成后存在）。如果值被替换，替换方法只会导致对条目的访问。putAll 方法为指定映射中的每个映射生成一个条目访问，按照指定映射的条目集迭代器提供键值映射的顺序。没有其他方法生成入口访问。特别是，

removeEldestEntry(Map.Entry) 方法可能会被覆盖，以在新映射添加到映射时自动删除陈旧映射。

回答by Kodebetter

public class LeastRecentlyUsed {

    public static <K, V> Map<K, V> leastRecentlyUsedCache(final int maxSize) {
        return new LinkedHashMap<K, V>(maxSize , 0.7f, true) {
            private static final long serialVersionUID = -3588047435434569014L;
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > maxSize;
            }
        };
    }

    public static void main(String[] args) {
        Map<Object, Object> leastRecentlyUsed = LeastRecentlyUsed.leastRecentlyUsedCache(3);
        leastRecentlyUsed.put("Robert", "Raj");
        leastRecentlyUsed.put("Auzi", "Aiz");
        leastRecentlyUsed.put("Sandy", "S");
        leastRecentlyUsed.put("Tript", "tty");  
        System.out.println(leastRecentlyUsed);
    }
  }

回答by Droid Teahouse

@templatetypedef

@templatetypedef

public LinkedHashMap(int initialCapacity,
         float loadFactor,
         boolean accessOrder)

accessOrder - the ordering mode - true for access-order, false for insertion-order

accessOrder - 排序模式 - 访问顺序为真，插入顺序为假

回答by roottraveller

I just write this very simple Generic solution though this one is not Threadsafe.

我只是写了这个非常简单的通用解决方案，尽管这个解决方案并不Thread安全。

LRUCacheDemo.java(public class)

LRUCacheDemo.java （公共类）

import java.io.*;
import java.util.*;

/* We can keep two separate data structures. A HashMap with (Key,Pointer) pairs and a doubly linked
  list which will work as the priority queue for deletion and store the Values. From the HashMap, 
  we can point to an element in the doubly linked list and update its' retrieval time. Because we
  go directly from the HashMap to the item in the list, our time complexity remains at O(1) 
*/
public class LRUCacheDemo {
    public static void main(String args[]) {
        LRUCache<Integer, Integer> lru = new LRUCache<>(3);
        for(int i=1; i<=9; ++i) {
            lru.put(i, 100*i+10*i+i); //i   iii
        }

        lru.get(8);
        /* for(Map.Entry<Integer, Integer> entry : lru.entrySet()) {
            System.out.printf("\n%1$-5s  %2$-5s", entry.getKey(), entry.getValue());
        } */

        System.out.println("LRU  : " + lru);
    }
} 

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int CACHE_SIZE;

    //NOTE : LinkedHashMap have already given implementation for LRU, this class has just used those method
    //See http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/LinkedHashMap.java#LinkedHashMap

    // LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
    // accessOrder - to maintain in order of elements from least-recently accessed to most-recently.
    LRUCache(final int sizeIn) {
        super(sizeIn, 0.75F, true);
        this.CACHE_SIZE = sizeIn;
    }

    @Override 
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return size() > this.CACHE_SIZE; 
        /* Returns true if this map should remove its eldest entry. This method is invoked by put and putAll after 
           inserting a new entry into the map. It provides the implementor with the opportunity to remove the eldest 
           entry each time a new one is added. This is useful if the map represents a cache.
        */
    }
}

O/P :

开/关：

LRU : {7=777, 9=999, 8=888}

回答by Joe

/*Java implementation using Deque and HashMap    */

interface Cache<K,V> {
    V get(K key) ;
    void set(K key, V value);
}

class Node <K,V>{
    K key;
    V value;

    public Node (K key, V value) {
        this.key = key;
        this.value = value;
    }
}

public class LRUCache <K,V> implements Cache<K,V>{
    Deque<Node<K,V>> dq = new LinkedList<>();
    Map<K, Node<K, V>> map = new HashMap<>();
    static int SIZE;

    public LRUCache(int size) {
        this.SIZE = size;
    }

    public V get(K key) {
        Node<K,V> result = map.get(key);
        if(result != null) {
            dq.remove(result);
            dq.addFirst(result);
            System.out.println("Get " +key +" : " +result.value);
            return result.value;
        }
        else {
            System.out.println("Cache miss");
            return null;
        }
    }

    public void set(K key, V value) {
        System.out.println("Set " +key +" : " +value);
        Node<K,V> result = map.get(key);
        if(result != null) {
            result.value = value;
            map.put(key, result);
            dq.remove(result);
            dq.addFirst(result);
            System.out.println("Updated frame " +key+" as " + value);
        }
        else {
            if(dq.size() == SIZE) {
                Node<K,V> toRemove = dq.removeLast();
                map.remove(toRemove);
                System.out.println("Frame removed " +toRemove.key +" : " +toRemove.value);
            }
            Node<K,V> newNode = new Node(key, value);
            dq.addFirst(newNode);
            map.put(key, newNode);
            System.out.println("Frame added " + key + " : " +value);
        }
    }

    public static void main(String[] args) {
        Cache<Integer, Integer> lru = new LRUCache<>(5);
        lru.get(2);
        lru.set(1, 11);
        lru.set(2, 22);
        lru.get(2);
        lru.set(3, 33);
        lru.set(4, 44);
        lru.set(5, 55);
        lru.get(2);
        lru.get(1);
        lru.set(6, 66);
    }
}

回答by Gil Beyruth

Using a Stack and a HashMap:

使用堆栈和 HashMap：

import java.util.HashMap;
import java.util.Stack;
public class LRU {
    private HashMap<String,Object> lruList;
    private Stack<String> stackOrder;
    private int capacity;
    LRU(int capacity){
      this.capacity = capacity;
      this.lruList = new HashMap<String, Object>(capacity);
      this.stackOrder = new Stack<String>();
    }
    public void put(String key, Object value){
      if(lruList.containsKey(key) || this.capacity < lruList.size() + 1) {
        if(lruList.containsKey(key)){
            String remove = key;
        }else{
            String remove = this.stackOrder.firstElement();
        }
        this.stackOrder.removeElement(remove);
        this.lruList.remove(remove);
      }
      this.lruList.put(key, value);
      this.stackOrder.add(key);
    }
    public Stack<String> get(){
      return this.stackOrder;
    }
    public Object get(String key){
      Object value = lruList.get(key);
      put(key, value);
      return value;
    }
}

public static void main(String[] args) {
    LRU lru = new LRU(3);
    lru.put("k1","v1");
    lru.put("k2","v2");
    lru.put("k3","v3");
    System.out.println(lru.get());
    lru.get("k1");
    System.out.println(lru.get());
    lru.put("k4","v4");
    System.out.println(lru.get());
}

Output:

输出：

[k1, k2, k3]

[k1, k2, k3]

[k2, k3, k1]

[k2, k3, k1]

[k3, k1, k4]

[k3, k1, k4]