本文参考网上各种大神资料，吃水不忘挖井人。
按照惯例先给大家来个段子。
![]()
哈哈哈嗝
哈哈哈嗝
| 目录 |
|---|
| 原理解析 |
| 代码实现 |
| 面试总结 |
1，原理解析
计数+1
1，get数据的时候通过key去缓存中查找，如果命中直接返回，当前计数+1；
2，put数据的时候，当前保存的数据超过了capacity(容量最大值)，则移除计数最少的缓存项。
这是比较传统的写法，但是数据量庞大的时候，需要把所有数据遍历一下，找到那个引用最少的，比较消耗性能。
链表形式
1，get数据的时候通过key去缓存中查找，如果命中直接返回，把当前key移动到链表的头部；
2，put数据的时候，把数据放到链表头部，当前保存的数据超过了capacity，则移除链表末尾的数据，并把节点移动到链表头部。
2，代码实现
思路
1，get方法，判断节点是否存在，存在把节点移动到链表头部
2，put方法，判断节点是否存在，超过capacity 移除链表末尾数据，并把节点移动到链表头部
3，需要一个双向链表，
4，需要一个hashMap存储数据。
5，细节 就是链表节点相连的的问题
public class LRUCache {
private int capacity;//扩容容量
private HashMap<String,Node> map= new HashMap<>();//保存用户数据
private Node head = new Node(null,null);//链表头节点
private Node last = new Node(null,null);//链表尾节点
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = last;
last.pre = head;
}
public <E> E get(String key){
//如果没有key 返回Null
if (!map.containsKey(key)){
return null;
}
Node<E> node = map.get(key);
//从链表中拿出当前节点，把前后节点相连
node.pre.next = node.next;
node.next.pre = node.pre;
//把当前节点放到链表最前边
moveToFirst(node);
return node.value;
}
public <E> void put(String key,E value){
//获取当前key 的节点，并且把当前节点放到链表头部，直接替换value
if (get(key) != null){
map.get(key).value = value;
return;
}
//如果当前容量已经达到最大值，移除链表尾部节点
if (map.size() == capacity){
Node lastNode = last.pre;
map.remove(lastNode.key);
lastNode.pre.next=last;
last.pre = lastNode.pre;
}
//创建新的节点，移动到第一位
Node newNode =new Node(key,value);
map.put(key,newNode);
moveToFirst(newNode);
}
//移动到链表头部，需要把上下节点相连
private void moveToFirst(Node current){
current.next = head.next;
current.pre= head;
head.next.pre =current;
head.next = current;
}
class Node<E> {
public Node(String key, E value) {
this.key = key;
this.value = value;
}
Node pre;
Node next;
String key;
E value;
@Override
public String toString() {
return "Node{" +
"pre=" + pre.hashCode() +
", next=" + next.hashCode() +
'}';
}
}
}
3，面试总结
1，掌握应用场景，一般面试都会从图片或者网络框架问进来，基本上能够讲出来上面两种实现原理，应该就算OK
2，我面试遇到过，问我对LRUCache了解多少，最好能手写，很遗憾当时我并不能做到。
