快取的實做方式有好幾種，這次說明LRU快取實做的概念。
介紹
LRU(Least Recently Used Cache) 是一種快取的實做方式，概念是會儲存最近用過的內容，會透過 Hash Map與 Double Linked List 來搭配實做，如果欲常被使用，內容會被擺在 List愈前方的位置，如果快取滿了，則會從 List最末端元素開始移除。
因為List會從第一筆逐一查詢，所以查詢的時間複雜度為 O(N)，為了降低查詢時間，所以才搭配HashMap，在 HashMap中設置 key，讓 key的內容對應到 List中的元素，就可以讓查詢時間降低到 O(1)
Get(key)
當使用 get(key) 方法來取得內容時，會在最後，將找到的元素從 List中搬移至 List的第一個，所以愈少被查詢的元素會放置在 List愈尾端的地方。
Put(key, value)
使用 put(key, value)時，如果 List 還沒滿，則會將元素新增在 List的第一個位置，同時在 HashMap中新增一個entry；如果List滿了，則會將List最後一個元素移除，同時移除HashMap中對應的 entry，接著再將新的元素新增到List第一個，同時在HashMap中建立entry。
實做
在LeetCode 中剛好也有一題是 LRU的實做，使用上述概念就可以解開這一題。
這提其實沒有花很久就寫出來，只是看到最後的執行時間，效率仍然不滿意，所以嘗試很許多時間在改善程式效能。
第一個版本寫出來平均大約 15ms，後續寫到平均在 13ms才覺得滿意，為了降低執行時間，我想到的方式是減少使用 function，同時多了一個 moveToFront方法，其實就是先刪除再新增，如果真的是在開發程式，是不會這樣寫的，這邊只是為了提高程式執行速度才採取這個方式。經過這些調整，方法的確有效，不過每次跑出來的結果都不太一樣。
下面是同一個程式不同時間 submit結果，結果降到 11ms：
最快在 11ms，上面顯示比 99%的java submission 快，不過後面就平均落在 13ms，僅超越 75%的 java submission，所以Leet Code上執行時間應該參考就好，沒那麼絕對。
總結
看完 LRU，對快取的機制有初步理解，除了 LRU外還有另外幾種機制，後續再接續介紹，瞭解目的是為了在專案實做上，對於快取的機制有進一步瞭解，在選擇上會更有利。
題外話，如果是在解 Leet Code，同樣的問題，可以用繼承的方式繼承 LinkedHashMap，並 override removeEldestEntry方法，就可以解決，所以懂得愈多，某些時候在解問題時可以用更省力的方式解決。