题目
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key)
- 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value)
- 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
题解
这道题在今日头条、快手或者硅谷的公司中是比较常见的，代码要写的还蛮多的，难度也是hard级别。
最重要的是LRU 这个策略怎么去实现,
很容易想到用一个链表去实现最近使用的放在链表的最前面。
比如get一个元素,相当于被使用过了，这个时候它需要放到最前面，再返回值,
set同理。
那如何把一个链表的中间元素，快速的放到链表的开头呢？
很自然的我们想到了双端链表。
基于 HashMap 和 双向链表实现 LRU 的
整体的设计思路是，可以使用 HashMap 存储 key，这样可以做到 save 和 get key的时间都是 O(1)，而 HashMap 的 Value 指向双向链表实现的 LRU 的 Node 节点
核心操作的步骤:
- save(key, value)
首先在 HashMap 找到 Key 对应的节点，如果节点存在，更新节点的值，并把这个节点移动队头。如果不存在，需要构造新的节点，并且尝试把节点塞到队头，如果LRU空间不足，则通过 tail 淘汰掉队尾的节点，同时在 HashMap 中移除 Key。 - get(key)，通过 HashMap 找到 LRU 链表节点，因为根据LRU 原理，这个节点是最新访问的，所以要把节点插入到队头，然后返回缓存的值。
代码实现
public class LRUCache<K extends Comparable<K>,V> implements Iterable<K> {
@Override
public Iterator<K> iterator() {
return new Iterator<K>() {
private LinkNode cur = head.next;
@Override
public boolean hasNext() {
return cur!=tail;
}
@Override
public K next() {
LinkNode node = cur;
cur = cur.next;
return node.key;
}
};
}
public class LinkNode{
public K key;
public V value;
LinkNode pre;
LinkNode next;
public LinkNode(K key,V value) {
this.key = key;
this.value =value;
}
public LinkNode() {
}
}
public LRUCache(int size) {
this.maxCount = size;
this.size = 0;
cache = new HashMap<>(size*4/3);
head = new LinkNode();
tail = new LinkNode();
head.next = tail;
tail.next = head;
}
private Map<K,LinkNode> cache;
private LinkNode head; // 虚拟头结点
private LinkNode tail; // 虚拟尾结点
private int maxCount;
private int size;
public V get(K key){
LinkNode linkNode = cache.get(key);
if(linkNode==null){
return null;
}
moveToHead(linkNode);
return linkNode.value;
}
public void put(K key,V value){
LinkNode node = cache.get(key);
if(node!=null){
//
node.value = value;
moveToHead(node);
return;
}
LinkNode newNode = new LinkNode(key, value);
cache.put(key,newNode);
addNodeToHead(newNode);
size++;
if(size>maxCount){
LinkNode tail = popTail();
cache.remove(tail.key);
size--;
}
}
/**
* 弹出尾部节点
* @return
*/
public LinkNode popTail() {
LinkNode end = tail.pre;
removeNode(end);
return end;
}
/**
* 移除一个节点
*
* @param node
*/
private void removeNode(LinkNode node) {
node.next.pre = node.pre;
node.pre.next = node.next;
node.next = null;
node.pre =null;
}
/**
* 将节点移动到开头
*
* @param node
*/
public void moveToHead(LinkNode node){
removeNode(node);
addNodeToHead(node);
}
/**
* 在虚拟头结点前插入新节点
*
* @param node
*/
private void addNodeToHead(LinkNode node) {
node.next = this.head.next;
node.next.pre = node;
this.head.next = node;
node.pre = head;
}
public static void main(String[] args) {
LRUCache cache = new LRUCache(2 /* 缓存容量 */);
cache.put(1, 1);
cache.put(2, 2);
System.out.println(cache.get(1));
cache.put(3, 3); // 该操作会使得密钥 2 作废
System.out.println(cache.get(2));
cache.put(4, 4); // 该操作会使得密钥 1 作废
System.out.println(cache.get(1));
System.out.println(cache.get(3));
System.out.println(cache.get(4));
Iterator<Integer> iterator = cache.iterator();
while (iterator.hasNext()) {
Integer key = iterator.next();
System.out.println(cache.get(key));
}
}
}
