JDK中的實現
在JDK中LinkedHashMap可以作為LRU算法以及插入順序的實現，LinkedHashMap繼承自HashMap，底層結合hash表和雙向鏈表，元素的插入和查詢等操作通過計算hash值找到其數組位置，在做插入或則查詢操作是，將元素插入到鏈表的表頭（當然得先刪除鏈表中的老元素），如果容量滿了，則刪除LRU這個元素，在鏈表表尾的元素即是。
LinkedHashMap的時間復雜度和HashMap差不多，雙向鏈表的刪除和表頭插入等操作都是O（1）復雜度，故不會影響HashMap的操作性能，插入，查詢，刪除LRU元素等操作均是O（1）的時間復雜度。
LinkedHashMap不是線程安全的類，用于多線程緩存則需要花點心思去同步它了，JDK中有支持并發的高性能ConcurrenHashMap，沒有ConcurrenListHashMap的實現，故要使用支持并發的高性能LRU算法還得靠自己去繼承ConcurrenHashMap或則其他方式實現。Google以及其它資深研發團隊已有ConcurrenListHashMap的實現
當然知道了原理，我們自己也可以來實現LRU算法
1.簡單的計數或則LU時間標記法
底層使用hash表，插入和訪問的時間都可以做到O（1）復雜度，容量滿了需要刪除LRU，則需要遍歷一遍數組，通過計數或則LU時間得到LRU，刪除之，時間復雜度O（n）。此算法簡單容易實現，適合數據量不大的需求
2.通過棧或雙向鏈表
這種算法通過維護元素的在鏈表中的順序來達到計算元素的訪問熱度，不需要額外的空間來計數或則記錄訪問時間。
插入時，先檢查改元素存在此鏈表中沒有，有的刪除之，然后再將元素插入表頭。
訪問時，遍歷數組查找該元素，然后將該元素移動至表頭。
這樣一來，最近被訪問的元素都在表頭，故要找出LRU則只需要刪除表尾元素即可。插入和訪問的時間復雜度均為O（n），如果用來作為緩存（查詢操作頻繁），相比hash表的實現，性能相當不好啊
3.結合HashMap和雙向鏈表
通過上面可知道HashMap可實現讀寫O(1)復雜度，但是找出LRU需要遍歷整個數組，而通過維護鏈表則相反，僅需要O（1）就可以找出LRU，故將兩者結合起來，實現綜合復雜度為O（1）的LRU算法
使用數組來存放元素，插入時通過hash計算出其位置，然后改變該元素在鏈表中的指針，兩個操作的時間復雜度均為1。具體實現可參考JDK的LinkedHashMap
http://www.360doc.com/content/14/0402/09/10504424_365635496.shtml