Кэш LRU в Java с операциями Generics и O(1)
Этот вопрос часто возникает на собеседованиях. Идея состоит в том, чтобы определить структуру данных вместо использования встроенного в LinkedHashMap Java.
Кэш LRU удаляет наименее недавно использованную запись для вставки новой. Итак, учитывая следующий сценарий:
A - B - C - D - E
Где A - наименее использованный элемент, если мы должны были вставить F, нам нужно удалить A.
Это может быть легко реализовано, если мы сохраним HashMap с записями кэша (ключ, значение) и отдельным списком, который содержит ключ и время использования элементов. Однако нам потребуется запросить список, чтобы найти наименее недавно использованный элемент с потенциальной O(n) временной сложностью.
Как эта структура может быть реализована в Java для универсальных объектов и операций O(1)?
Это отличается от возможного дубликата тем, что фокусируется на эффективности (O(1) ops) и реализации самой структуры данных, а не расширении Java.
15 ответов
Из самого вопроса видно, что проблема операций O(n) возникает при запросе связанного списка. Поэтому нам нужна альтернативная структура данных. Мы должны иметь возможность обновлять время последнего доступа элементов из HashMap без поиска.
Мы можем сохранить две отдельные структуры данных. HashMap с парами (Key,Pointer) и двусвязным списком, который будет работать как приоритетная очередь для удаления и сохранения значений. Из HashMap мы можем указать элемент в двусвязном списке и обновить его время поиска. Поскольку мы переходим непосредственно из HashMap к элементу в списке, наша временная сложность остается на уровне O(1).
Например, наш двусвязный список может выглядеть так:
least_recently_used -> A <-> B <-> C <-> D <-> E <- most_recently_used
Нам нужно сохранить указатель на элементы LRU и MRU. Значения записей будут сохранены в списке, и когда мы запросим HashMap, мы получим указатель на список. В get() нам нужно поместить элемент в крайнюю правую часть списка. На месте (ключ, значение), если кеш заполнен, нам нужно удалить элемент в левой части списка как из списка, так и из HashMap.
Ниже приведен пример реализации на 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++;
}
}
}
Реализация, которая проходит тесты leetcode questiton + простые модульные тесты.
Я сделал запрос на извлечение по этому адресу: https://github.com/haoel/leetcode/pull/90/files
LRUCache.java
import java.util.LinkedHashMap;
import java.util.Iterator;
public class LRUCache {
private int capacity;
private LinkedHashMap<Integer,Integer> map;
public LRUCache(int capacity) {
this.capacity = capacity;
this.map = new LinkedHashMap<>();
}
public int get(int key) {
Integer value = this.map.get(key);
if (value == null) {
value = -1;
} else {
this.set(key, value);
}
return value;
}
public void set(int key, int value) {
if (this.map.containsKey(key)) {
this.map.remove(key);
} else if (this.map.size() == this.capacity) {
Iterator<Integer> it = this.map.keySet().iterator();
it.next();
it.remove();
}
map.put(key, value);
}
}
LRUCacheTest.java:
import java.util.ArrayList;
import org.junit.Test;
import static org.junit.Assert.*;
public class LRUCacheTest {
private LRUCache c;
public LRUCacheTest() {
this.c = new LRUCache(2);
}
@Test
public void testCacheStartsEmpty() {
assertEquals(c.get(1), -1);
}
@Test
public void testSetBelowCapacity() {
c.set(1, 1);
assertEquals(c.get(1), 1);
assertEquals(c.get(2), -1);
c.set(2, 4);
assertEquals(c.get(1), 1);
assertEquals(c.get(2), 4);
}
@Test
public void testCapacityReachedOldestRemoved() {
c.set(1, 1);
c.set(2, 4);
c.set(3, 9);
assertEquals(c.get(1), -1);
assertEquals(c.get(2), 4);
assertEquals(c.get(3), 9);
}
@Test
public void testGetRenewsEntry() {
c.set(1, 1);
c.set(2, 4);
assertEquals(c.get(1), 1);
c.set(3, 9);
assertEquals(c.get(1), 1);
assertEquals(c.get(2), -1);
assertEquals(c.get(3), 9);
}
}
removeEldestEntry () альтернативная реализация
Не уверен, что оно того стоит, так как оно занимает столько же строк, но здесь мы заканчиваем:
import java.util.LinkedHashMap;
import java.util.Iterator;
import java.util.Map;
class LinkedhashMapWithCapacity<K,V> extends LinkedHashMap<K,V> {
private int capacity;
public LinkedhashMapWithCapacity(int capacity) {
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return this.size() > this.capacity;
}
}
public class LRUCache {
private LinkedhashMapWithCapacity<Integer,Integer> map;
public LRUCache(int capacity) {
this.map = new LinkedhashMapWithCapacity<>(capacity);
}
public int get(int key) {
Integer value = this.map.get(key);
if (value == null) {
value = -1;
} else {
this.set(key, value);
}
return value;
}
public void set(int key, int value) {
if (this.map.containsKey(key))
this.map.remove(key);
this.map.get(key);
}
}
LinkedHashMap разработан с учетом этого
Из Javadocs:
Предусмотрен специальный конструктор для создания связанной хэш-карты, порядок итераций которой соответствует порядку, в котором к ее элементам обращались в последний раз, от последнего к последнему доступу до самого последнего (порядок доступа). Этот вид карты хорошо подходит для создания LRU-кэшей. Вызов методов put, putIfAbsent, get, getOrDefault, compute, computeIfAbsent, computeIfPresent или merge приводит к доступу к соответствующей записи (при условии, что она существует после завершения вызова). Методы замены обеспечивают доступ к записи только при замене значения. Метод putAll генерирует один доступ к записи для каждого сопоставления в указанной карте в том порядке, в котором сопоставления ключ-значение предоставляются итератором набора записей указанной карты. Никакие другие методы не генерируют входы. В частности, операции над коллекциями-представлениями не влияют на порядок итерации карты поддержки.
Метод removeEldestEntry(Map.Entry) может быть переопределен для наложения политики автоматического удаления устаревших сопоставлений при добавлении новых сопоставлений на карту.
Использование стека и 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());
}
Выход:
[k1, k2, k3]
[k2, k3, k1]
[k3, k1, k4]
/*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);
}
}
Я просто пишу это очень простое общее решение, хотя это не Thread безопасный.
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}
@templatetypedef
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder)
accessOrder - режим упорядочения - true для access-order, false для insert-order
Мы можем использовать 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;
}
}
Единственный улов заключается в том, что по умолчанию порядок связанных списков - это порядок вставки, а не доступа. Однако один из конструкторов предоставляет возможность использовать вместо этого порядок доступа.
Вот реализация Java с Generics а также LinkedHashMapи сложность O(1) на get() а также put(),
import java.util.LinkedHashMap;
public class LRUCache<K, V> {
private LinkedHashMap<K, V> lruCacheMap;
private final int capacity;
private final boolean SORT_BY_ACCESS = true;
private final float LOAD_FACTOR = 0.75F;
public LRUCache(int capacity){
this.capacity = capacity;
this.lruCacheMap = new LinkedHashMap<>(capacity, LOAD_FACTOR, SORT_BY_ACCESS);
}
public V get(K k){
return lruCacheMap.get(k);
}
public void put(K k, V v){
if(lruCacheMap.containsKey(k)){
lruCacheMap.remove(k);
}else if(lruCacheMap.size() >= capacity){
lruCacheMap.remove(lruCacheMap.keySet().iterator().next());
}
lruCacheMap.put(k, v);
}
public void printSequence(){
System.out.println(lruCacheMap.keySet());
}
}
Вот код для его тестирования:
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class TestLruCache {
static class MyHardDrive {
Map<String, Object> resources = new HashMap<>();
MyHardDrive(){
for(Character i='A'; i<='Z'; i++){
resources.put(i.toString(), new Object());
}
}
Object loadResource(String name){
return resources.get(name);
}
}
public static void main(String[] args) {
MyHardDrive hd = new MyHardDrive();
LRUCache<String,Object> cache = new LRUCache<>(4);
for(String key: Arrays.asList("A","B","C","A","D","E","F","E","F","G","A")){
Object object = cache.get(key);
if(object==null){
object = hd.loadResource(key);
cache.put(key, object);
}
cache.printSequence();
}
}
}
идея
Кеш - это не что иное, как циклический массив. Этот список содержит запись. когда появятся новые записи, добавьте в конец списка. Это означает наименее недавно использованный элемент в первую очередь. Предположим, если вы повторно используете какой-либо элемент, отсоедините его от списка и добавьте в конце.
Чтобы получить какой-либо элемент, нам нужно пройти по списку, который требует O(n) временной сложности. Чтобы избежать этого, я поддерживаю HashMap>. Здесь k - ключ, а IndexNode будет содержать указатель на запись в списке. таким образом, мы можем получить O(1) сложность времени.
рабочий раствор
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);
}
}
выход
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}
Вот реализация 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();
}
}
Вот юнит тест
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));
}
}
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);
}
}
Это решение также пройдет онлайн-судью LeetCode для проблемы с кешем LRU, аналогично этому ответу. Здесь мы используем HashMap с двусвязным списком. Постоянна и сложность памяти.
public class LRUCache {
private final Node head = new Node(0, 0);
private final Node tail = new Node(0, 0);
private final Map<Integer, Node> cache;
private final int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
cache = new HashMap<>(capacity);
head.next = tail;
tail.prev = head;
}
public int get(int key) {
Node node = cache.get(key);
if (node == null) {
return -1;
}
remove(node);
append(node);
return node.value;
}
public void put(int key, int value) {
Node currentNode = cache.get(key);
if (currentNode != null) {
updateNodeValue(value, currentNode);
} else {
createNewNode(key, value);
}
}
private void createNewNode(int key, int value) {
if (cache.size() == capacity) {
cache.remove(tail.prev.key);
remove(tail.prev);
}
Node node = new Node(key, value);
append(node);
cache.put(key, node);
}
private void updateNodeValue(int value, Node currentNode) {
remove(currentNode);
currentNode.value = value;
append(currentNode);
}
private void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void append(Node node) {
Node headNext = head.next;
head.next = node;
headNext.prev = node;
node.prev = head;
node.next = headNext;
}
private class Node {
Node prev, next;
int key, value;
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
}
Вот решение LeetCode для проблемы с кешем LRU:
public class LRUCache {
class DLinkedNode {
int key;
int value;
DLinkedNode prev;
DLinkedNode next;
}
private void addNode(DLinkedNode node) {
/**
* Always add the new node right after head.
*/
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(DLinkedNode node) {
/**
* Remove an existing node from the linked list.
*/
DLinkedNode prev = node.prev;
DLinkedNode next = node.next;
prev.next = next;
next.prev = prev;
}
private void moveToHead(DLinkedNode node) {
/**
* Move certain node in between to the head.
*/
removeNode(node);
addNode(node);
}
private DLinkedNode popTail() {
/**
* Pop the current tail.
*/
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}
private Map<Integer, DLinkedNode> cache = new HashMap<>();
private int size;
private int capacity;
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
head = new DLinkedNode();
// head.prev = null;
tail = new DLinkedNode();
// tail.next = null;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) { return -1; }
// move the accessed node to the head;
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node == null) {
DLinkedNode newNode = new DLinkedNode();
newNode.key = key;
newNode.value = value;
cache.put(key, newNode);
addNode(newNode);
++size;
if (size > capacity) {
// pop the tail
DLinkedNode tail = popTail();
cache.remove(tail.key);
--size;
}
} else {
// update the value.
node.value = value;
moveToHead(node);
}
}
}
Справка
Как сказали K'' и Ciro Santilli 新疆改造中心 六四事件 法轮功, это можно сделать с помощью LinkedHashMap учебный класс. При сжатии вы можете получить минимальную версию из 15 строк кода.
Ciro Santilli 新疆改造中心 六四事件 法轮功, почему бы просто не вырезать лишнее определение класса? Если бы используемые тесты ставили как другие java-карты, нам бы не пришлось связывать этот метод псевдонимом с методом set, который мы на самом деле ожидали бы получить с карты каким-то образом сета.
import java.utils.LinkedHashMap
import java.util.Map;
public class LRUCache<K,V> extends LinkedHashMap<K,V> {
private int maxSize;
// and other constructors for load factor and hashtable capacity
public LRUCache(int initialCapacity, float loadFactor, int maxSize) {
super(initialCapacity, loadFactor, true);
this.maxSize = maxSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return size() > maxSize;
}
// I don't like this. set should return a set put should put an item
public V set(K key, V value) {
put(key, value)
}
}
см. здесь и в документации для получения дополнительной информации.
Golang Решение проблемы leetcode, т.е. разработка структуры данных, которая соответствует ограничениям кэша наименее недавно использованного (LRU). Каждая функция получения и размещения должна выполняться со средней временной сложностью O(1) .
Примечание:- Только 17 тестовых случаев проходят из 21.
type Node struct {
key int
val int
prev *Node
next *Node
}
type LRUCache struct {
cache map[int]*Node
currSize int
capacity int
leastRU *Node
mostRU *Node
}
func Constructor(capacity int) LRUCache {
return LRUCache{
capacity: capacity,
currSize: 0,
leastRU: &Node{
key: 0,
val: 0,
prev: nil,
next: nil,
},
mostRU: &Node{
key: 0,
val: 0,
prev: nil,
next: nil,
},
cache: make(map[int]*Node),
}
}
func (this *LRUCache) Get(key int) int {
tempNode, ok := this.cache[key]
if !ok {
return -1
} else if this.mostRU.key == tempNode.key {
return tempNode.val
}
nextNode := tempNode.next
prevNode := tempNode.prev
if this.leastRU.key == tempNode.key {
nextNode.prev = nil
this.leastRU = nextNode
} else if this.mostRU.key != tempNode.key {
prevNode.next = nextNode
nextNode.prev = prevNode
}
tempNode.prev = this.mostRU
this.mostRU.next = tempNode
this.mostRU = tempNode
this.mostRU.next = nil
return tempNode.val
}
func (this *LRUCache) Put(key int, value int) {
if _, ok := this.cache[key]; ok {
this.cache[key].val = value
if this.leastRU.key != this.mostRU.key {
tempNode := this.cache[key]
nextNode := tempNode.next
prevNode := tempNode.prev
if this.leastRU.key == tempNode.key {
nextNode.prev = nil
this.leastRU = nextNode
} else if this.mostRU.key != tempNode.key {
prevNode.next = nextNode
nextNode.prev = prevNode
}
tempNode.prev = this.mostRU
this.mostRU.next = tempNode
this.mostRU = tempNode
this.mostRU.next = nil
}
return
} else {
newNode := &Node{
key: key,
val: value,
prev: nil,
next: nil,
}
this.mostRU.next = newNode
newNode.prev = this.mostRU
this.mostRU = newNode
this.cache[key] = newNode
if this.currSize == this.capacity {
fmt.Println(key, this.leastRU.key)
delete(this.cache, this.leastRU.key)
this.leastRU = this.leastRU.next
this.leastRU.prev = nil
} else if this.currSize < this.capacity {
if this.currSize == 0 {
this.leastRU = newNode
}
this.currSize++
}
}
// fmt.Println(this.cache)
}
/**
* Your LRUCache object will be instantiated and called as such:
* obj := Constructor(capacity);
* param_1 := obj.Get(key);
* obj.Put(key,value);
*/