实现LRU缓存， 学会两种实现方式， 原始一点的用HashMap,可以了解更多实现细节， 还有就是LinkedHashMap(比较简单 就省略了)（ 可以先将代码放到Leetcode上跑通过后再来看代码）， 看了半天别人的代码然后跑过去通不过是件很沮丧的事情。
1. HashMap版本
package com.azhou.xiaoming; import java.util.HashMap; import java.util.Map; public class LRUCache { int capacity; Map<Integer, LRUNode> map = new HashMap<>(); LRUNode head; LRUNode tail; public LRUCache(int capacity) { this.capacity = capacity; } public int get(int key) { LRUNode node = map.get(key); if(node != null) { removeAndInsert(node); return node.value; } return -1; } public void put(int key, int value) { if(head == null) { head = new LRUNode(key, value); tail = head; map.put(key, head); } LRUNode temp = map.get(key); if(temp != null) { temp.value = value; map.put(key, temp); removeAndInsert(temp); } else { if(map.size() >= capacity) { map.remove(tail.key); if(tail == head) { head = new LRUNode(key, value); tail = head; map.put(key, head); return ; } else { tail = tail.pre; tail.next = null; } } LRUNode node = new LRUNode(key, value); map.put(key, node); node.next = head; head.pre = node; node.pre = null; head = node; } } private void removeAndInsert(LRUNode node) { if(node == head) { return ; } else if(node == tail) { tail = node.pre; tail.next = null; } else { node.pre.next = node.next; node.next.pre = node.pre; } node.next = head; node.pre = null; head.pre = node; head = node; } public static void main(String[] args) { LRUCache cache = new LRUCache(1); cache.put(1,1); int i = cache.get(1); System.out.println("第一次：" + i); cache.put(2,2); int i1 = cache.get(2); System.out.println("第二次:" + i1); cache.put(3,3); } } class LRUNode { int key; int value; LRUNode next; LRUNode pre; public LRUNode(int key, int value) { this.key = key; this.value = value; } }
