android里面lrucache算法為什么用雙向鏈表實(shí)現(xiàn)？LRU是通過雙向鏈表和映射實(shí)現(xiàn)的，在Java中也是通過雙向鏈表實(shí)現(xiàn)的。通過JDK中的LinkedHashMap很容易實(shí)現(xiàn)lrucache。將

android里面lrucache算法為什么用雙向鏈表實(shí)現(xiàn)？

LRU是通過雙向鏈表和映射實(shí)現(xiàn)的，在Java中也是通過雙向鏈表實(shí)現(xiàn)的。通過JDK中的LinkedHashMap很容易實(shí)現(xiàn)lrucache。

將最近訪問的元素放在鏈表的一端，如果容量達(dá)到限制，則從另一端刪除該元素

LRU算法的設(shè)計(jì)原則是：如果最近一段時(shí)間內(nèi)沒有訪問過某個(gè)數(shù)據(jù)，則將來不太可能訪問該數(shù)據(jù)。換言之，當(dāng)有限的空間充滿數(shù)據(jù)時(shí)，應(yīng)該消除最長時(shí)間未被訪問的數(shù)據(jù)。

執(zhí)行LRU

1。使用數(shù)組存儲(chǔ)數(shù)據(jù)，用訪問時(shí)間戳標(biāo)記每個(gè)數(shù)據(jù)項(xiàng)。插入新數(shù)據(jù)項(xiàng)時(shí)，首先增加數(shù)組中現(xiàn)有數(shù)據(jù)項(xiàng)的時(shí)間戳，將新數(shù)據(jù)項(xiàng)的時(shí)間戳設(shè)置為0，然后將其插入數(shù)組中。每次訪問數(shù)組中的數(shù)據(jù)項(xiàng)時(shí)，所訪問數(shù)據(jù)項(xiàng)的時(shí)間戳都設(shè)置為0。當(dāng)數(shù)組空間已滿時(shí)，時(shí)間戳最大的數(shù)據(jù)項(xiàng)將被刪除。

2. 使用鏈表實(shí)現(xiàn)，每次插入新數(shù)據(jù)時(shí)，將新數(shù)據(jù)插入鏈表的頭部；每次緩存命中時(shí)，將數(shù)據(jù)移動(dòng)到鏈表的頭部（即訪問數(shù)據(jù)）；然后在鏈表已滿時(shí)丟棄鏈表末尾的數(shù)據(jù)。

3. 使用鏈表和HashMap。當(dāng)需要插入新數(shù)據(jù)項(xiàng)時(shí)，如果新數(shù)據(jù)項(xiàng)存在于鏈表中（通常稱為hit），請將節(jié)點(diǎn)移動(dòng)到鏈表的頭部。如果不存在，則創(chuàng)建一個(gè)新節(jié)點(diǎn)并將其放在鏈表的頭部。如果緩存已滿，請刪除鏈表的最后一個(gè)節(jié)點(diǎn)。在訪問數(shù)據(jù)時(shí)，如果鏈表中存在該數(shù)據(jù)項(xiàng)，則節(jié)點(diǎn)會(huì)移到鏈表的頭，否則返回-1。這樣，鏈表末尾的節(jié)點(diǎn)就是最近不可訪問的數(shù)據(jù)項(xiàng)。

對于第一種方法，需要連續(xù)維護(hù)數(shù)據(jù)項(xiàng)的訪問時(shí)間戳。另外，在插入數(shù)據(jù)、刪除數(shù)據(jù)和訪問數(shù)據(jù)時(shí)，時(shí)間復(fù)雜度為O（n）。對于第二種方法，鏈表的時(shí)間復(fù)雜度為O（n）。所以一般來說，第三種方法是實(shí)現(xiàn)LRU算法。

lru算法？

1. Linkedhashset繼承自hahsset。構(gòu)造方法使用三個(gè)參數(shù)調(diào)用方法。構(gòu)造方法的底層初始化LinkedHashMap。因?yàn)長inkedHashMap是有序的，所以linkedhashset也是有序的。為什么我們不能調(diào)用這個(gè)構(gòu)造函數(shù)？它是包訪問級(jí)別，不能在外部調(diào)用。接下來，分析LinkedHashMap是如何實(shí)現(xiàn)的，以理解為什么它是有序的。

2. 先看下面的圖片。（對于寫在手機(jī)上的問題，你不能把圖片放在文字里，它們都在下面。）。

LinkedHashMap的數(shù)據(jù)結(jié)構(gòu)與HashMap不同。HashMap中的條目有四個(gè)屬性：key、value、hash和next，而LinkedHashMap中的條目添加了before和after屬性。因此，LinkedHashMap在HashMap的基礎(chǔ)上使用雙向鏈表來連接所有節(jié)點(diǎn)。當(dāng)然，它也有一個(gè)頭部節(jié)點(diǎn)，所以遍歷可以有序進(jìn)行。具體結(jié)構(gòu)如圖所示。

3. LinkedHashMap主要重寫addentry和createentry方法，在創(chuàng)建節(jié)點(diǎn)時(shí)創(chuàng)建雙向鏈表。

此外，LinkedHashMap還可以實(shí)現(xiàn)LRU算法的緩存。

源代碼基于JDK7查看ha。如果你不懂HashMap，你可以看到我分享的另一篇文章。

希望對您有所幫助，您可以關(guān)注我，以后會(huì)分享更多的架構(gòu)和java知識(shí)文章。