LRU cache
实现lru 缓存
思路:用map+链表实现,map用来提高查询速度,链表用来存放元素。链表头放入最新的元素,表尾为最老元素。访问cache命中,或者cache满写入时都需要对链表内容和map进行调整。
JDK里面有一个LinkedHashMap就是基于这个思路实现的。
LRU Cache
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get
and set
.
get(key)
- Get the value (will always be positive)
of the key if the key exists in the cache, otherwise return -1.
set(key, value)
- Set or insert the value if the key is not already present. When the cache
reached its capacity, it should invalidate the least recently used item before inserting a new item.
public class LRUCache { static class Node { int key; int value; @Override public String toString() { return "Node{" + "key=" + key + ", value=" + value + '}'; } } static private LinkedList<Node> cache; static private int cap; static private Node indexMap[]; public LRUCache(int capacity) { cache = new LinkedList<Node>(); indexMap = new Node[100000]; cap = capacity; } static public boolean isFull() { return cache.size() == cap; } static public Node find(int key) { if (cache.isEmpty()) return null; Node tar = null; if ((tar = indexMap[key]) == null) return null; cache.remove(tar); cache.addFirst(tar); return tar; } public int get(int key) { Node node = find(key); if (node == null) { return -1; } return node.value; } public void set(int key, int value) { Node node = null; if ((node = find(key)) != null) { node.value = value; return; } //not find the element if (isFull()) { indexMap[cache.getLast().key] = null; cache.removeLast(); } Node newNode = new Node(); newNode.key = key; newNode.value = value; cache.addFirst(newNode); indexMap[key] = newNode; } }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。