Реализация кэша LRU в Java

Что такое кэш LRU?

Кэш LRU означает Наименее недавно использованный кэш. Размер кэша фиксирован, и он поддерживает операции get() и put (). Когда кэш заполнен, операция put() удаляет наименее недавно использованный кэш.

Как реализовать кэш LRU в Java?

Кэш LRU может быть реализован на Java с использованием двух структур данных – HashMap и двусвязного списка для хранения данных.

Идея состоит в том, чтобы всегда располагать элементы в следующем порядке.

Вот реализация кэша LRU в Java.

package com.journaldev.examples;

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

public class LRUCache {

	private Node lru;
	private Node mru;
	private Map> container;
	private int capacity;
	private int currentSize;

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

	public V get(K key) {
		Node 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 nextNode = tempNode.next;
		Node 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 myNode = new Node(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 key;
		U value;
		Node prev;
		Node next;

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

}

Некоторые важные моменты, касающиеся реализации.

Класс Node используется для реализации структуры двусвязного списка. Он содержит ссылки на предыдущий и следующий узлы.
Когда мы получаем значение с помощью метода get (), элемент перемещается в крайнее правое положение, потому что он становится элементом MRU.
Когда мы помещаем элемент в кэш, он добавляется в крайнюю правую часть. Если контейнер заполнен, то элемент LRU удаляется.
Мы используем универсальные методы, чтобы мы могли использовать реализацию с любыми типами данных.

Программа тестирования кэша LRU

Я использую JUnit тестовые примеры для запуска некоторых сценариев из вопроса LeetCode .

package com.journaldev.examples;

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

import org.junit.jupiter.api.Test;

class LRUCacheTest {

	private LRUCache 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);
	}

}

Тест кэша LRU

Вывод

Существует множество способов реализации кэша LRU. Но если мы сохраним элементы кэша в порядке их использования, то сможем повысить производительность операции put ().

Что такое кэш LRU?

Как реализовать кэш LRU в Java?

Программа тестирования кэша LRU

Вывод

Рекомендации