思路:用map+链表实现,map用来提高查询速度,链表用来存放元素。链表头放入最新的元素,表尾为最老元素。访问cache命中,或者cache满写入时都需要对链表内容和map进行调整。
JDK里面有一个LinkedHashMap就是基于这个思路实现的。
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations:
and
- get
.
- set
- Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
- get(key)
- 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. Show Tags
- set(key, value)
- 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;
- }
- }
来源: http://www.phpxs.com/code/1001862/