如何用LinkedHashMap實現LRU緩存算法

jopen 10年前發布 | 78K 次閱讀 算法 LinkedHashMap

緩存這個東西就是為了提高運行速度的，由于緩存是在寸土寸金的內存里面，不是在硬盤里面，所以容量是很有限的。LRU這個算法就是把最近一次使用時間離現在時間最遠的數據刪除掉。先說說List：每次訪問一個元素后把這個元素放在 List一端，這樣一來最遠使用的元素自然就被放到List的另一端。緩存滿了t的時候就把那最遠使用的元素remove掉。但更實用的是 HashMap。因為List太慢，要刪掉的數據總是位于List底層數組的第一個位置，刪掉之后，后面的數據要向前補位。。所以復雜度是O(n)，那就用鏈表結構的LinkedHashMap唄~，LinkedHashMap默認的元素順序是put的順序，但是如果使用帶參數的構造函數，那么 LinkedHashMap會根據訪問順序來調整內部 順序。 LinkedHashMap的get()方法除了返回元素之外還可以把被訪問的元素放到鏈表的底端，這樣一來每次頂端的元素就是remove的元素。

構造函數如下：

public LinkedHashMap (int initialCapacity, float loadFactor, boolean accessOrder)；

 initialCapacity   初始容量

 loadFactor    加載因子，一般是 0.75f

accessOrder   false 基于插入順序  true  基于訪問順序（get一個元素后，這個元素被加到最后，使用了LRU  最近最少被使用的調度算法）

來個例子吧：

    import java.util.*;



class Test  
{  
    public static void main(String[] args) throws Exception{  

        Map<Integer,Integer> map=new LinkedHashMap<>(10,0.75f,true);  
        map.put(9,3);  
        map.put(7,4);  
        map.put(5,9);  
        map.put(3,4);  
        //現在遍歷的話順序肯定是9,7,5,3  
        //下面訪問了一下9,3這個鍵值對，輸出順序就變嘍~  
        map.get(9);  
        for(Iterator<Map.Entry<Integer,Integer>> it=map.entrySet().iterator();it.hasNext();){  
            System.out.println(it.next().getKey());  
        }  
    }  
}  </pre><a class="CopyToClipboard" title="copy" href="/misc/goto?guid=4959614864620731076"></a></div>



</div>
</div>
輸出</div>


7

5

3

9


好玩吧~


下面開始實現LRU緩存嘍~








    import java.util.*;

    //擴展一下LinkedHashMap這個類，讓他實現LRU算法

    class LRULinkedHashMap<K,V> extends LinkedHashMap<K,V>{

        //定義緩存的容量

        private int capacity;

        private static final long serialVersionUID = 1L;

        //帶參數的構造器

        LRULinkedHashMap(int capacity){

            //調用LinkedHashMap的構造器，傳入以下參數

            super(16,0.75f,true);

            //傳入指定的緩存最大容量

            this.capacity=capacity;

        }

        //實現LRU的關鍵方法，如果map里面的元素個數大于了緩存最大容量，則刪除鏈表的頂端元素

        @Override

        public boolean removeEldestEntry(Map.Entry<K, V> eldest){

            System.out.println(eldest.getKey() + "=" + eldest.getValue());

            return size()>capacity;

        }

    }

    //測試類

    class Test{

    public static void main(String[] args) throws Exception{



    //指定緩存最大容量為4  
    Map<Integer,Integer> map=new LRULinkedHashMap<>(4);  
    map.put(9,3);  
    map.put(7,4);  
    map.put(5,9);  
    map.put(3,4);  
    map.put(6,6);  
    //總共put了5個元素，超過了指定的緩存最大容量  
    //遍歷結果  
        for(Iterator<Map.Entry<Integer,Integer>> it=map.entrySet().iterator();it.hasNext();){  
            System.out.println(it.next().getKey());  
        }  
    }  
}  </pre><a class="CopyToClipboard" title="copy" href="/misc/goto?guid=4959614864620731076"></a></div>



</div>
</div>
輸出結果如下</div>


9=3

9=3

9=3

9=3

9=3

7

5

3

6


分析一下：使用帶參數構造器，且啟用LRU模式的LinkedHashMap會在每次有新元素加入的時候，判斷當前儲存元素是否超過了緩存上限，也就是執行

一次removeEldestEntry方法，看最后的遍歷結果，發現果然把9刪除了，LRU發揮作用了~



                    

                    

                        
 本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

                        
 轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

                        
 本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

                        
                        
                    


                

                

                    

                        
相關經驗

                        
                    

                    

                        
相關資訊

                        
                    

                    

                        
相關文檔