LRU算法的设计原则是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。
实现思路：
- 采用HashMap，对key-value进行存储，获取时直接查询map,达到查询时间O(1)
- 采用双向链表，链表的每个节点是对key-value的包装，按照访问时间的先后进行链接，最近访问的放在链表头部，最久访问的放在链表尾部，用两个额外指针head和tail进行标记，当capacity满时，直接对tail进行删除，而不需要遍历整个链表；插入时，新节点直接放在链表头部，修改head指针即可。
- put时，如果已存在这个key，那么只需要更新它的value，再将其原有的指向关系修改，最后提到头部，修改head指针和节点的pre和next指针；如果不存在，先判断capacity是否已满，满了需要先删除tail节点，之后在将新节点放在表头，最后将key-Node放到map。
- get时，先根据map是否存在，不存在直接返回-1或null；存在，则需要更新该key在链表的位置，修改该key节点的原来指向关系，再放到头部，修改head指针和节点的pre和next指针
- remove时，和get类似，只不过修改该key节点的指向关系之后不需要放在链表头部
- clear时，将所有属性和集合置空即可
package com.tao.leetcode;
import java.util.HashMap;
import java.util.Optional;
/**
* @author: Penger
* @time: 2019/8/7
* @description: <p>
* </p>
**/
public class CustomLru<K, V> {
class LruNode {
LruNode pre;
LruNode next;
K key;
V value;
LruNode(K key, V value, LruNode pre, LruNode next) {
this.key = key;
this.value = value;
this.pre = pre;
this.next = next;
Optional.ofNullable(next).ifPresent(node -> node.pre = this);
}
}
private int maxCapacity;
private int size;
private HashMap<K, LruNode> map;
private LruNode head;
private LruNode tail;
public CustomLru(int capacity) {
this.maxCapacity = capacity;
this.size = 0;
this.map = new HashMap<>(capacity);
this.head = null;
this.tail = null;
}
public void put(K k, V v) {
Optional.ofNullable(map.get(k)).map(node -> {
if (node == head) {
node.value = v;
return node;
}
node.value = v;
removeNode(node);
moveToHead(node);
return true;
}).orElseGet(() -> {
if (size >= maxCapacity) {
map.remove(tail.key);
removeNode(tail);
} else {
size++;
}
if (head == null) {
head = tail = new LruNode(k, v, null, null);
} else {
head = new LruNode(k, v, null, head);
}
map.put(k, head);
return true;
});
}
public V get(K k) {
return Optional.ofNullable(map.get(k)).map(node -> {
if (node == head) {
return node.value;
}
removeNode(node);
moveToHead(node);
return node.value;
}).orElse(null);
}
public V remove(K k) {
return Optional.ofNullable(map.get(k)).map(node -> {
if (node == head) {
head = node.next;
head.pre = null;
}
removeNode(node);
size--;
return node.value;
}).orElse(null);
}
public void clear() {
head = null;
tail = null;
map.clear();
}
private void removeNode(LruNode node) {
Optional.ofNullable(node).ifPresent(cur -> {
Optional.ofNullable(cur.pre).ifPresent(n -> n.next = cur.next);
Optional.ofNullable(cur.next).ifPresent(n -> n.pre = cur.pre);
if (cur == tail) {
tail = cur.pre;
}
cur.pre = null;
cur.next = null;
});
}
private void moveToHead(LruNode node) {
Optional.ofNullable(node).ifPresent(n -> {
n.next = head;
head.pre = n;
n.pre = null;
head = n;
});
}
public static void main(String[] args) {
CustomLru<Integer, Integer> cache = new CustomLru<>(2);
cache.put(1, 1);
cache.put(2, 2);
// 返回 1
System.out.println(cache.get(1));
// 该操作会使得密钥 2 作废
cache.put(3, 3);
// 返回 null (未找到)
System.out.println(cache.get(2));
// 该操作会使得密钥 1 作废
cache.put(4, 4);
// 返回 null (未找到)
System.out.println(cache.get(1));
// 返回 3
System.out.println(cache.get(3));
// 返回 4
System.out.println(cache.get(4));
}
}
