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