数据结构~缓存淘汰算法--LRU算法（Java的俩种实现方式，万字解析

/**
• 使用jdk库类实现LRU
*/
class LRUCacheByLinkedHashMap {
private LinkedHashMap nodes;
private int size;
public LRUCacheByLinkedHashMap(int capacity) {
//实现LRU的linkedHashMap的构造方法
nodes = new LinkedHashMap<>(capacity, 0.75f, true);
this.size = capacity;
}
public int get(int key) {
Integer ret = nodes.get(key);
return ret == null ? -1 : ret;
}
public void put(int key, int value) {
nodes.put(key, value);
if (nodes.size() > size) {
//使用迭代器删除第一个数据
Iterator> iterator = nodes.entrySet().iterator();
if (iterator.hasNext()) {
iterator.next();
iterator.remove();
}
}
}
}

class LRUCache {
static class Node {
int key;
int val;
Node prev;
Node next;
private Node(){}
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}
private int size;
private HashMap map;
private int capacity;
private Node head;
private Node tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
map = new HashMap<>();
head = new Node();
tail = new Node();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
Node node = map.get(key);
if (node == null) {
//没有这个节点
return -1;
}
//需要移动到最前面
moveHead(node);