LruCache算法原理及實作LruCache算法原理及實作

<code>LRU</code>為<code>Least Recently Used</code>的縮寫，意思也就是近期最少使用算法。<code>LruCache</code>将<code>LinkedHashMap</code>的順序設定為LRU順序來實作LRU緩存，每次調用<code>get</code>并擷取到值(也就是從記憶體緩存中命中)，則将該對象<code>移到連結清單的尾端</code>。調用<code>put</code>插入新的對象也是存儲在<code>連結清單尾端</code>，這樣當記憶體緩存達到設定的最大值時，将<code>連結清單頭部的對象</code>（近期最少用到的）移除。

基于<code>LinkedHashMap</code>的<code>LRUCache</code>的實作，關鍵是重寫<code>LinkedHashMap</code>的<code>removeEldestEntry</code>方法，在<code>LinkedHashMap</code>中該方法預設傳回<code>false</code>（LRUCache本身未考慮線程安全的問題），這樣此映射的行為将類似于正常映射，即永遠不能移除最舊的元素。

按從近期通路最少到近期通路最多的順序（即通路順序）來儲存元素，LinkedHashMap提供了LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)構造函數，該哈希映射的疊代順序就是最後通路其條目的順序，這種映射很适合建構LRU緩存。

LinkedHashMap提供了removeEldestEntry(Map.Entry eldest)方法。該方法在每次添加新條目時移除最舊條目，但該方法預設傳回false，這樣，此映射的行為将類似于正常映射，即永遠不能移除最舊的元素。因而需要重寫該方法。

參考文檔：

<a href="http://blog.csdn.net/pingnanlee/article/details/40585941">http://blog.csdn.net/pingnanlee/article/details/40585941</a> <a href="http://www.cnblogs.com/children/archive/2012/10/02/2710624.html">http://www.cnblogs.com/children/archive/2012/10/02/2710624.html</a>