什么是LRU缓存？

LRU缓存代表"最近最少使用的缓存"。
缓存的大小是固定的，并且支持get()和put()操作。
当缓存已满时，put()操作将删除最近最少使用的缓存。

如何在Java中实现LRU Cache？

LRU缓存可以使用两种数据结构在Java中实现-HashMap和用于存储数据的双向链接列表。

想法是始终按以下顺序排列元素。

最近使用最少(LRU)-> A <-> B <-> C <-> D <-> E <-最近使用(MRU)

这是Java中的LRUCache实现。

package com.theitroad.examples;

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

public class LRUCache<K, V> {

	private Node<K, V> lru;
	private Node<K, V> mru;
	private Map<K, Node<K, V>> container;
	private int capacity;
	private int currentSize;

	public LRUCache(int capacity) {
		this.capacity = capacity;
		this.currentSize = 0;
		lru = new Node<K, V>(null, null, null, null);
		mru = lru;
		container = new HashMap<K, Node<K, V>>();
	}

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

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

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

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

		//Finally move our item to the MRU
		tempNode.prev = mru;
		mru.next = tempNode;
		mru = tempNode;
		mru.next = null;

		return tempNode.value;

	}

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

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

		//Delete the left-most entry and update the LRU pointer
		if (currentSize == capacity) {
			container.remove(lru.key);
			lru = lru.next;
			lru.prev = null;
		}

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

	//Node for doubly linked list
	class Node<T, U> {
		T key;
		U value;
		Node<T, U> prev;
		Node<T, U> next;

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

}

有关实施的一些重要点。

• Node类用于实现双向链表结构。
  它具有对上一个和下一个节点的引用。

• 当我们使用get()方法获取值时，该元素将移动到最右边的位置，因为它成为MRU元素。

• 当我们将元素放入缓存时，它会添加到最右侧。
  如果容器已满，则将删除LRU元素。

• 我们正在使用泛型，以便我们可以将实现与任何类型的数据一起使用。

LRUCache测试程序

我正在使用JUnit测试用例来运行LeetCode问题中的某些方案。

package com.theitroad.examples;

import static org.junit.jupiter.api.Assertions.assertEquals;

import org.junit.jupiter.api.Test;

class LRUCacheTest {

	private LRUCache<Integer, Integer> c;

	public LRUCacheTest() {
		this.c = new LRUCache<>(2);
	}

	@Test
	public void testCacheStartsEmpty() {
		assertEquals(c.get(1), null);
	}

	@Test
	public void testSetBelowCapacity() {
		c.put(1, 1);
		assertEquals(c.get(1), 1);
		assertEquals(c.get(2), null);
		c.put(2, 4);
		assertEquals(c.get(1), 1);
		assertEquals(c.get(2), 4);
	}

	@Test
	public void testCapacityReachedOldestRemoved() {
		c.put(1, 1);
		c.put(2, 4);
		c.put(3, 9);
		assertEquals(c.get(1), null);
		assertEquals(c.get(2), 4);
		assertEquals(c.get(3), 9);
	}

	@Test
	public void testGetRenewsEntry() {
		c.put(1, 1);
		c.put(2, 4);
		assertEquals(c.get(1), 1);
		c.put(3, 9);
		assertEquals(c.get(1), 1);
		assertEquals(c.get(2), null);
		assertEquals(c.get(3), 9);
	}

}