LRU缓存设计是一个能够考察许多知识点以及实际编程能力的题目，因为我们在实际工作中是很有可能会去自己写一个LRU算法的简单缓存。本题是LeetCode的第 146 题。LRU——即 Least Recently Used，淘汰最近最少使用的元素的算法。考察的主要内容包括：
首先考虑简单的设计实现。一个LRU的缓存是基于队列实现的，Java中可以基于LinkedList或者Deque队列实现。需要实现两个基本操作get/put
1 public class LRUCache { 2 3 private final int capacity; 4 5 private Map<Integer, Integer> map = new ConcurrentHashMap<>(); 6 private Deque<Integer> queue = new LinkedList<Integer>(); 7 8 public LRUCache(int capacity) { 9 this.capacity = capacity; 10 } 11 12 public int get(int key) { 13 Integer value = map.get(key); 14 if (value != null) { 15 16 this.queue.remove((Integer)key); 17 this.queue.addLast(key); 18 return value; 19 } 20 return -1; 21 } 22 23 public void put(int key, int value) { 24 if (map.get(key) != null) { 25 this.queue.remove((Integer)key); 26 this.queue.addLast(key); 27 map.put(key, value); 28 return; 29 } 30 31 if (queue.size() >= capacity) { 32 Integer lruKey = this.queue.pollFirst(); 33 map.remove(lruKey); 34 } 35 this.queue.addLast(key); 36 map.put(key, value); 37 } 38 } 39 40 /** 41 * Your LRUCache object will be instantiated and called as such: 42 * LRUCache obj = new LRUCache(capacity); 43 * int param_1 = obj.get(key); 44 * obj.put(key,value); 45 */
好了，这个题目现在已经完成了，然而光这些，在实际开发中缓存往往会被多线程同时访问，我们考虑的就需要更加周密，也更能体现我们的水平。那么线程安全的实现需要一些说明额外的东西呢？
答案就是——加锁。因为对缓存队列和map的操作是可能多个线程同时进行的，所以我们用可重入锁 ReetrantLock 去保护这一过程即可。ReetrantLock 的原理这里就先不赘述。
1 public class LRUCache { 2 3 private final int capacity; 4 5 private ReentrantLock lock = new ReentrantLock(); 6 7 private Map<Integer, Integer> map = new ConcurrentHashMap<>(); 8 private Deque<Integer> queue = new LinkedList<Integer>(); 9 10 public LRUCache(int capacity) { 11 this.capacity = capacity; 12 } 13 14 public int get(int key) { 15 Integer value = map.get(key); 16 if (value != null) { 17 lock.lock(); 18 try { 19 this.queue.remove((Integer)key); 20 this.queue.addLast(key); 21 return value; 22 } finally { 23 lock.unlock(); 24 } 25 } 26 return -1; 27 } 28 29 public void put(int key, int value) { 30 if (map.get(key) != null) { 31 lock.lock(); 32 try { 33 this.queue.remove((Integer)key); 34 this.queue.addLast(key); 35 map.put(key, value); 36 } finally { 37 lock.unlock(); 38 } 39 return; 40 } 41 42 lock.lock(); 43 try { 44 if (queue.size() >= capacity) { 45 Integer lruKey = this.queue.pollFirst(); 46 map.remove(lruKey); 47 } 48 this.queue.addLast(key); 49 map.put(key, value); 50 } finally { 51 lock.unlock(); 52 } 53 } 54 } 55 56 /** 57 * Your LRUCache object will be instantiated and called as such: 58 * LRUCache obj = new LRUCache(capacity); 59 * int param_1 = obj.get(key); 60 * obj.put(key,value); 61 */
原文：https://www.cnblogs.com/XiaoHDeBlog/p/13198998.html