之前暑期实习面试的时候也被问到了，需要我们说一下思路，然后实现。如果让我们简单来实现一下的话，有很多的方式。比如Java就有自带的LinkedHashMap来实现，但是面试官既然问了那便是不想让你直接调用接口了。我们一般都是用哈希+双向链表来实现。下面给出三种实现方式，参考leetcode题解，leetcode上面也有类似的题。
它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
LinkedHashMap
最容易实现的，但也是面试官应该最不想看到的。毕竟这样完全考察不到你的coding能力。
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private int initialCapacity;
public LRUCache(int initialCapacity) {
//true表示按照访问顺序排序
super(initialCapacity, 0.75f, true);
this.initialCapacity = initialCapacity;
}
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<K, V> eldest) {
if (size() > initialCapacity) {
return true;
}
return false;
}
}
哈希+队列
用哈希来存取值，以对首是最久未使用的，对尾是最近使用来实现
class LRUCache {
Map<Integer,Integer> map;
//队列，对首是越久未使用的，对尾是最近使用的
Queue<Integer> queue;
int cap;
public LRUCache(int capacity) {
this.map = new HashMap<>();
this.queue = new LinkedList<>();
this.cap = capacity;
}
public int get(int key) {
//如果key存在，移除重新添加就能靠近队尾
if(queue.contains(key)){
queue.remove(key);
queue.add(key);
return map.get(key);
}else{
return -1;
}
}
public void put(int key, int value) {
//如果使用的是已经存在的key
if(queue.contains(key)){
queue.remove(key);
queue.add(key);
map.put(key,value);
//如果缓存已经满了，删除最久未使用的
}else if(cap == 0){
map.remove(queue.poll());
queue.add(key);
map.put(key,value);
}else{
//有空闲的位置，第一次添加，直接添加进去
queue.add(key);
map.put(key,value);
cap--;
}
}
}
哈希+手动实现双向链表
面试官有时候应该更希望看到我们手动来实现双向链表，展示coding能力。这里以leetcode参考答案为例
class LRUCache {
class Node{
int key;
int value;
Node prev;
Node next;
public Node(){}
public Node(int key,int value){this.key = key; this.value = value;}
}
private HashMap<Integer,Node> cache = new HashMap<>();
private int size;
private int capacity;
private Node head,tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
// 使用伪头部和伪尾部结点
head = new Node();
tail = new Node();
//构建双向链表
head.next = tail;
tail.next = head;
}
public int get(int key) {
Node node = cache.get(key);
if(node == null){
return -1;
}
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
Node node = cache.get(key);
if(node == null){
//如果key不存在，创建一个新的结点
Node temp = new Node(key,value);
cache.put(key,temp);
//将最新存进来的结点移动至头部
addToHead(temp);
++size;
//如果长度超出了我们的容量，将尾部的结点删除
if(size > capacity){
Node tail = removeTail();
cache.remove(tail.key);
--size;
}
}else{
//如果存在key，将原来的值覆盖掉
node.value = value;
moveToHead(node);
}
}
private void addToHead(Node node){
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(Node node){
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void moveToHead(Node node){
removeNode(node);
addToHead(node);
}
private Node removeTail(){
Node res = tail.prev;
removeNode(res);
return res;
}
}
