目錄：
- 1. LRU 緩存介紹
- 2. ConcurrentLinkedQueue簡單介紹
- 3. ReadWriteLock簡單介紹
- 4.ScheduledExecutorService 簡單介紹
- 5. 徒手擼一個線程安全的 LRU 緩存
- 6. 實現一個線程安全並且帶有過期時間的 LRU 緩存
很多人就會問了：“網上已經有這麼多現成的緩存了！為什麼面試官還要我們自己實現一個呢？” 。咳咳咳，當然是為了面試需要。哈哈！開個玩笑，我個人覺得更多地是為了學習吧！
- 實現一個線程安全的 LRU 緩存
- 實現一個線程安全並且帶有過期時間的 LRU 緩存
考慮到了線程安全性我們使用了 ConcurrentHashMap 、ConcurrentLinkedQueue這兩個線程安全的集合。另外，還用到 ReadWriteLock（讀寫鎖）。為了實現帶有過期時間的緩存，我們用到了 ScheduledExecutorService來做定時任務執行。
1. LRU 緩存介紹
LRU (Least Recently Used,最近最少使用)是一種緩存淘汰策略。
LRU緩存指的是當緩存大小已達到最大分配容量的時候，如果再要去緩存新的對象數據的話，就需要將緩存中最近訪問最少的對象刪除掉以便給新來的數據騰出空間。
2. ConcurrentLinkedQueue簡單介紹
ConcurrentLinkedQueue是一個基於單向鏈表的無界無鎖線程安全的隊列，適合在高併發環境下使用，效率比較高。 我們在使用的時候，可以就把它理解為我們經常接觸的數據結構——隊列，不過是增加了多線程下的安全性保證罷了。和普通隊列一樣，它也是按照先進先出(FIFO)的規則對接點進行排序。 另外，隊列元素中不可以放置null元素。
ConcurrentLinkedQueue 整個繼承關係如下圖所示：
ConcurrentLinkedQueue中最主要的兩個方法是：offer(value)和poll()，分別實現隊列的兩個重要的操作：入隊和出隊(offer(value)等價於add(value))。
我們添加一個元素到隊列的時候，它會添加到隊列的尾部，當我們獲取一個元素時，它會返回隊列頭部的元素。
單鏈表
利用ConcurrentLinkedQueue隊列先進先出的特性，每當我們 put/get(緩存被使用)元素的時候，我們就將這個元素存放在隊列尾部，這樣就能保證隊列頭部的元素是最近最少使用的。
3. ReadWriteLock簡單介紹
ReadWriteLock 是一個接口，位於java.util.concurrent.locks包下，裡面只有兩個方法分別返回讀鎖和寫鎖：
ReentrantReadWriteLock 是ReadWriteLock接口的具體實現類。
讀寫鎖還是比較適合緩存這種讀多寫少的場景。讀寫鎖可以保證多個線程和同時讀取，但是隻有一個線程可以寫入。但是，有一個問題是當讀鎖被線程持有的時候，讀鎖是無法被其它線程申請的，會處於阻塞狀態，直至讀鎖被釋放。
另外，同一個線程持有寫鎖時是可以申請讀鎖，但是持有讀鎖的情況下不可以申請寫鎖。
4.ScheduledExecutorService 簡單介紹
ScheduledExecutorService 是一個接口，ScheduledThreadPoolExecutor 是其主要實現類。
ScheduledThreadPoolExecutor 主要用來在給定的延遲後運行任務，或者定期執行任務。 這個在實際項目用到的比較少，因為有其他方案選擇比如quartz。但是，在一些需求比較簡單的場景下還是非常有用的！
ScheduledThreadPoolExecutor 使用的任務隊列 DelayQueue 封裝了一個 PriorityQueue，PriorityQueue 會對隊列中的任務進行排序，執行所需時間短的放在前面先被執行，如果執行所需時間相同則先提交的任務將被先執行。
5. 徒手擼一個線程安全的 LRU 緩存
5.1. 實現方法
ConcurrentHashMap + ConcurrentLinkedQueue +ReadWriteLock
5.2. 原理
ConcurrentHashMap 是線程安全的Map，我們可以利用它緩存 key,value形式的數據。ConcurrentLinkedQueue是一個線程安全的基於鏈表的隊列（先進先出），我們可以用它來維護 key 。每當我們put/get(緩存被使用)元素的時候，我們就將這個元素對應的 key 存放在隊列尾部，這樣就能保證隊列頭部的元素是最近最少使用的。當我們的緩存容量不夠的時候，我們直接移除隊列頭部對應的key以及這個key對應的緩存即可！
另外，我們用到了ReadWriteLock(讀寫鎖)來保證線程安全。
5.3. put方法具體流程分析
為了方便大家理解，我將代碼中比較重要的 put(key,value)方法的原理圖畫了出來，如下圖所示：
5.4. 源碼
<code>/** * @author shuang.kou ** 使用 ConcurrentHashMap+ConcurrentLinkedQueue+ReadWriteLock實現線程安全的 LRU 緩存 * 這裡只是為了學習使用，本地緩存推薦使用 Guava 自帶的。使用 Spring 的話，推薦使用Spring Cache */ public class MyLruCache { /** * 緩存的最大容量 */ private final int maxCapacity; private ConcurrentHashMap cacheMap; private ConcurrentLinkedQueue keys; /** * 讀寫鎖 */ private ReadWriteLock readWriteLock = new ReentrantReadWriteLock(); private Lock writeLock = readWriteLock.writeLock(); private Lock readLock = readWriteLock.readLock(); public MyLruCache(int maxCapacity) { if (maxCapacity (maxCapacity); keys = new ConcurrentLinkedQueue<>(); } public V put(K key, V value) { // 加寫鎖 writeLock.lock(); try { //1.key是否存在於當前緩存 if (cacheMap.containsKey(key)) { moveToTailOfQueue(key); cacheMap.put(key, value); return value; } //2.是否超出緩存容量，超出的話就移除隊列頭部的元素以及其對應的緩存 if (cacheMap.size() == maxCapacity) { System.out.println("maxCapacity of cache reached"); removeOldestKey(); } //3.key不存在於當前緩存。將key添加到隊列的尾部並且緩存key及其對應的元素 keys.add(key); cacheMap.put(key, value); return value; } finally { writeLock.unlock(); } } public V get(K key) { //加讀鎖 readLock.lock(); try { //key是否存在於當前緩存 if (cacheMap.containsKey(key)) { // 存在的話就將key移動到隊列的尾部 moveToTailOfQueue(key); return cacheMap.get(key); } //不存在於當前緩存中就返回Null return null; } finally { readLock.unlock(); } } public V remove(K key) { writeLock.lock(); try { //key是否存在於當前緩存 if (cacheMap.containsKey(key)) { // 存在移除隊列和Map中對應的Key keys.remove(key); return cacheMap.remove(key); } //不存在於當前緩存中就返回Null return null; } finally { writeLock.unlock(); } } /** * 將元素添加到隊列的尾部(put/get的時候執行) */ private void moveToTailOfQueue(K key) { keys.remove(key); keys.add(key); } /** * 移除隊列頭部的元素以及其對應的緩存 (緩存容量已滿的時候執行) */ private void removeOldestKey() { K oldestKey = keys.poll(); if (oldestKey != null) { cacheMap.remove(oldestKey); } } public int size() { return cacheMap.size(); } }
/<code>
非併發環境測試：
併發環境測試：
我們初始化了一個固定容量為 10 的線程池和count為10的CountDownLatch。我們將100次操作分10次添加到線程池 ，然後我們等待線程池執行完成這10次操作。
6. 實現一個線程安全並且帶有過期時間的 LRU 緩存
實際上就是在我們上面時間的LRU緩存的基礎上加上一個定時任務去刪除緩存，常見的實現定時任務的方式有下面幾種：
- Timer :不被推薦，多線程會存在問題。
- ScheduledExecutorService ：定時器線程池，可以用來替代 Timer
- DelayQueue ：延時隊列
- quartz ：一個很火的開源任務調度框架，很多其他框架都是基於 quartz 開發的，比如噹噹網的elastic-job就是基於quartz二次開發之後的分佈式調度解決方案
- ......
最終我們選擇了 ScheduledExecutorService，主要原因是它易用（基於DelayQueue做了很多封裝）並且基本能滿足我們的大部分需求。
我們在我們上面實現的線程安全的 LRU 緩存基礎上，簡單稍作修改即可！我們增加了一個方法：
我們put元素的時候，如果通過這個方法就能直接設置過期時間。
完整源碼如下：
<code>/** * @author shuang.kou ** 使用 ConcurrentHashMap+ConcurrentLinkedQueue+ReadWriteLock+ScheduledExecutorService實現線程安全的 LRU 緩存 * 這裡只是為了學習使用，本地緩存推薦使用 Guava 自帶的，使用 Spring 的話，推薦使用Spring Cache */ public class MyLruCacheWithExpireTime { /** * 緩存的最大容量 */ private final int maxCapacity; private ConcurrentHashMap cacheMap; private ConcurrentLinkedQueue keys; /** * 讀寫鎖 */ private ReadWriteLock readWriteLock = new ReentrantReadWriteLock(); private Lock writeLock = readWriteLock.writeLock(); private Lock readLock = readWriteLock.readLock(); private ScheduledExecutorService scheduledExecutorService; public MyLruCacheWithExpireTime(int maxCapacity) { if (maxCapacity (maxCapacity); keys = new ConcurrentLinkedQueue<>(); scheduledExecutorService = Executors.newScheduledThreadPool(3); } public V put(K key, V value, long expireTime) { // 加寫鎖 writeLock.lock(); try { //1.key是否存在於當前緩存 if (cacheMap.containsKey(key)) { moveToTailOfQueue(key); cacheMap.put(key, value); return value; } //2.是否超出緩存容量，超出的話就移除隊列頭部的元素以及其對應的緩存 if (cacheMap.size() == maxCapacity) { System.out.println("maxCapacity of cache reached"); removeOldestKey(); } //3.key不存在於當前緩存。將key添加到隊列的尾部並且緩存key及其對應的元素 keys.add(key); cacheMap.put(key, value); if (expireTime > 0) { removeAfterExpireTime(key, expireTime); } return value; } finally { writeLock.unlock(); } } public V get(K key) { //加讀鎖 readLock.lock(); try { //key是否存在於當前緩存 if (cacheMap.containsKey(key)) { // 存在的話就將key移動到隊列的尾部 moveToTailOfQueue(key); return cacheMap.get(key); } //不存在於當前緩存中就返回Null return null; } finally { readLock.unlock(); } } public V remove(K key) { writeLock.lock(); try { //key是否存在於當前緩存 if (cacheMap.containsKey(key)) { // 存在移除隊列和Map中對應的Key keys.remove(key); return cacheMap.remove(key); } //不存在於當前緩存中就返回Null return null; } finally { writeLock.unlock(); } } /** * 將元素添加到隊列的尾部(put/get的時候執行) */ private void moveToTailOfQueue(K key) { keys.remove(key); keys.add(key); } /** * 移除隊列頭部的元素以及其對應的緩存 (緩存容量已滿的時候執行) */ private void removeOldestKey() { K oldestKey = keys.poll(); if (oldestKey != null) { cacheMap.remove(oldestKey); } } private void removeAfterExpireTime(K key, long expireTime) { scheduledExecutorService.schedule(() -> { //過期後清除該鍵值對 cacheMap.remove(key); keys.remove(key); }, expireTime, TimeUnit.MILLISECONDS); } public int size() { return cacheMap.size(); } }
/<code>
測試效果：
