class LRUCache extends LinkedHashMap<Integer, Integer>{
private int capacity;

public LRUCache(int capacity) {
super(capacity, 0.75F, true);
this.capacity = capacity;
}

public int get(int key) {
return super.getOrDefault(key, -1);
}

//可以不写
public void put(int key, int value) {
super.put(key, value);
}

@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}

解法二：

哈希表 + 双向链表

LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。

双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。

哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。

这样以来，我们首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在 O(1) 的时间内完成 get 或者 put 操作。

注意：在双向链表的实现中，使用一个伪头部和伪尾部标记界限，这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。

代码如下：

class LRUCache {

class DLinkedNode{
int key;
int value;

DLinkedNode prev;
DLinkedNode next;
public DLinkedNode(){}
public DLinkedNode(int key,int value){
this.key = key;
this.value = value;
}
}

private Map<Integer,DLinkedNode> cache = new HashMap<Integer,DLinkedNode>();
private int size;
private int capacity;
private DLinkedNode head,tail;

public LRUCache(int capacity) {
this.capacity = capac

《Android学习笔记总结+最新移动架构视频+大厂安卓面试真题+项目实战源码讲义》

【docs.qq.com/doc/DSkNLaERkbnFoS0ZF】 完整内容开源分享

ity;
this.size = 0;
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.prev = head;
}

public int get(int key) {
DLinkedNode node = cache.get(key);
if(node == null){
return -1;
}
//如果 key 存在，先通过哈希表定位,再移到头部
moveToHead(node);
return node.value;

}

public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if(node == null){
//如果 key 不存在，创建一个新的节点
DLinkedNode newNode = new DLinkedNode(key,value);
//添加至哈希表
cache.put(key,newNode);
//添加至双向链表的头部
addToHead(newNode);
++size;
//如果超出容量，删除双向链表的尾部节点，同时删除哈希表中对应的项
if(size > capacity){
DLinkedNode tail = removeTail();
cache.remove(tail.key);
–size;
}

} else {
//如果 key 存在，先通过哈希表定位，再修改 value(覆盖值)，并转移到头部
node.value = value;
moveToHead(node);
}
}

private void addToHead(DLinkedNode node){
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}

private void moveToHead(DLinkedNode node){
removeNode(node);
addToHead(node);
}

private DLinkedNode removeTail(){
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}

private void removeNode(DLinkedNode node){