`

【温故】 LRU算法的代码实现

 
阅读更多
[java]  
  1. import java.util.LinkedHashMap;  
  2. import java.util.Collection;  
  3. import java.util.Map;  
  4. import java.util.ArrayList;  
  5.   
  6. /** 
  7. * An LRU cache, based on <code>LinkedHashMap</code>. 
  8. * 
  9. * <p> 
  10. * This cache has a fixed maximum number of elements (<code>cacheSize</code>). 
  11. * If the cache is full and another entry is added, the LRU (least recently used) 
  12. * entry is dropped. 
  13. * 
  14. * <p> 
  15. * This class is thread-safe. All methods of this class are synchronized. 
  16. * 
  17. * <p> 
  18. * Author: Christian d'Heureuse, Inventec Informatik AG, Zurich, Switzerland<br> 
  19. * Multi-licensed: EPL / LGPL / GPL / AL / BSD. 
  20. */  
  21. public class LRUCache<K,V> {  
  22.   
  23. private static final float   hashTableLoadFactor = 0.75f;  
  24.   
  25. private LinkedHashMap<K,V>   map;  
  26. private int                  cacheSize;  
  27.   
  28. /** 
  29. * Creates a new LRU cache. 
  30. * @param cacheSize the maximum number of entries that will be kept in this cache. 
  31. */  
  32. public LRUCache (int cacheSize) {  
  33.    this.cacheSize = cacheSize;  
  34.    int hashTableCapacity = (int)Math.ceil(cacheSize / hashTableLoadFactor) + 1;  
  35.    map = new LinkedHashMap<K,V>(hashTableCapacity, hashTableLoadFactor, true) {  
  36.       // (an anonymous inner class)  
  37.       private static final long serialVersionUID = 1;  
  38.       @Override protected boolean removeEldestEntry (Map.Entry<K,V> eldest) {  
  39.          return size() > LRUCache.this.cacheSize; }}; }  
  40.   
  41. /** 
  42. * Retrieves an entry from the cache.<br> 
  43. * The retrieved entry becomes the MRU (most recently used) entry. 
  44. * @param key the key whose associated value is to be returned. 
  45. * @return    the value associated to this key, or null if no value with this key exists 
  46. * in the cache. 
  47. */  
  48. public synchronized V get (K key) {  
  49.    return map.get(key); }  
  50.   
  51. /** 
  52. * Adds an entry to this cache. 
  53. * The new entry becomes the MRU (most recently used) entry. 
  54. * If an entry with the specified key already exists in the cache, 
  55. * it is replaced by the new entry. 
  56. * If the cache is full, the LRU (least recently used) entry is removed from the cache. 
  57. * @param key    the key with which the specified value is to be associated. 
  58. * @param value  a value to be associated with the specified key. 
  59. */  
  60. public synchronized void put (K key, V value) {  
  61.    map.put (key, value); }  
  62.   
  63. /** 
  64. * Clears the cache. 
  65. */  
  66. public synchronized void clear() {  
  67.    map.clear(); }  
  68.   
  69. /** 
  70. * Returns the number of used entries in the cache. 
  71. * @return the number of entries currently in the cache. 
  72. */  
  73. public synchronized int usedEntries() {  
  74.    return map.size(); }  
  75.   
  76. /** 
  77. * Returns a <code>Collection</code> that contains a copy of all cache entries. 
  78. * @return a <code>Collection</code> with a copy of the cache content. 
  79. */  
  80. public synchronized Collection<Map.Entry<K,V>> getAll() {  
  81.    return new ArrayList<Map.Entry<K,V>>(map.entrySet()); }  
  82.   
  83. // end class LRUCache  
  84. -----------------------------------------------------------------------------------  
  85. // Test routine for the LRUCache class.  
  86. public static void main (String[] args) {  
  87.    LRUCache<String,String> c = new LRUCache<String, String>(3);  
  88.    c.put ("1""one");                           // 1  
  89.    c.put ("2""two");                           // 2 1  
  90.    c.put ("3""three");                         // 3 2 1  
  91.    c.put ("4""four");                          // 4 3 2  
  92.    if (c.get("2") == nullthrow new Error();    // 2 4 3  
  93.    c.put ("5""five");                          // 5 2 4  
  94.    c.put ("4""second four");                   // 4 5 2  
  95.    // Verify cache content.  
  96.    if (c.usedEntries() != 3)              throw new Error();  
  97.    if (!c.get("4").equals("second four")) throw new Error();  
  98.    if (!c.get("5").equals("five"))        throw new Error();  
  99.    if (!c.get("2").equals("two"))         throw new Error();  
  100.    // List cache content.  
  101.    for (Map.Entry<String, String> e : c.getAll())  
  102.       System.out.println (e.getKey() + " : " + e.getValue()); }  


代码出自:http://www.source-code.biz/snippets/java/6.htm

 

 

       今天主要来讨论基于双链表的LRU算法的实现, 在讨论之前,我们需要了解一下,传统LRU算法的实现,与其的弊端。

 

       传统意义的LRU算法是为每一个Cache对象设置一个计数器,每次Cache命中则给计数器+1,而Cache用完,需要淘汰旧内容,放置新内容时,就查看所有的计数器,并将最少使用的内容替换掉。

       它的弊端很明显,如果Cache的数量少,问题不会很大, 但是如果Cache的空间过大,达到10W或者100W以上,一旦需要淘汰,则需要遍历所有计算器,其性能与资源消耗是巨大的。效率也就非常的慢了。

 

       基于这样的情况,所有就有新的LRU算法的实现----基于双链表 的LRU实现。

       它的原理: 将Cache的所有位置都用双连表连接起来,当一个位置被命中之后,就将通过调整链表的指向,将该位置调整到链表头的位置,新加入的Cache直接加到链表头中。

       这样,在多次进行Cache操作后,最近被命中的,就会被向链表头方向移动,而没有命中的,而想链表后面移动,链表尾则表示最近最少使用的Cache。

       当需要替换内容时候,链表的最后位置就是最少被命中的位置,我们只需要淘汰链表最后的部分即可。

 

       上面说了这么多的理论, 下面用代码来实现一个LRU策略的缓存。

       我们用一个对象来表示Cache,并实现双链表,下面给出完整的实现,这个类也被Tomcat所使用( org.apache.tomcat.util.collections.LRUCache),但是在tomcat6.x版本中,已经被弃用,使用另外其他的缓存类来替代它。

 

 

Java代码  收藏代码
  1. public class LRUCache {  
  2.     private int cacheSize;  
  3.     private Hashtable nodes;//缓存容器  
  4.     private int currentSize;  
  5.     private CacheNode first;//链表头  
  6.     private CacheNode last;//链表尾 
  7.     /** 
  8.      * 链表节点 
  9.      * @author Administrator 
  10.      * 
  11.      */  
  12.     class CacheNode {  
  13.         CacheNode prev;//前一节点  
  14.         CacheNode next;//后一节点  
  15.         Object value;//值  
  16.         Object key;//键  
  17.         CacheNode() {  
  18.         }  
  19.     }  
  20.   
  21.     public LRUCache(int i) {  
  22.         currentSize = 0;  
  23.         cacheSize = i;  
  24.         nodes = new Hashtable(i);//缓存容器  
  25.     }  
  26.       
  27.     /** 
  28.      * 获取缓存中对象 
  29.      * @param key 
  30.      * @return 
  31.      */  
  32.     public Object get(Object key) {  
  33.         CacheNode node = (CacheNode) nodes.get(key);  
  34.         if (node != null) {  
  35.             moveToHead(node);  
  36.             return node.value;  
  37.         } else {  
  38.             return null;  
  39.         }  
  40.     }  
  41.       
  42.     /** 
  43.      * 添加缓存 
  44.      * @param key 
  45.      * @param value 
  46.      */  
  47.     public void put(Object key, Object value) {  
  48.         CacheNode node = (CacheNode) nodes.get(key);  
  49.           
  50.         if (node == null) {  
  51.             //缓存容器是否已经超过大小.  
  52.             if (currentSize >= cacheSize) {  
  53.                 if (last != null)//将最少使用的删除  
  54.                     nodes.remove(last.key);  
  55.                 removeLast();  
  56.             } else {  
  57.                 currentSize++;  
  58.             }  
  59.               
  60.             node = new CacheNode();  
  61.         }  
  62.         node.value = value;  
  63.         node.key = key;  
  64.         //将最新使用的节点放到链表头,表示最新使用的.  
  65.         moveToHead(node);  
  66.         nodes.put(key, node);  
  67.     }  
  68.   
  69.     /** 
  70.      * 将缓存删除 
  71.      * @param key 
  72.      * @return 
  73.      */  
  74.     public Object remove(Object key) {  
  75.         CacheNode node = (CacheNode) nodes.get(key);  
  76.         if (node != null) {  
  77.             if (node.prev != null) {  
  78.                 node.prev.next = node.next;  
  79.             }  
  80.             if (node.next != null) {  
  81.                 node.next.prev = node.prev;  
  82.             }  
  83.             if (last == node)  
  84.                 last = node.prev;  
  85.             if (first == node)  
  86.                 first = node.next;  
  87.         }  
  88.         return node;  
  89.     }  
  90.   
  91.     public void clear() {  
  92.         first = null;  
  93.         last = null;  
  94.     }  
  95.   
  96.     /** 
  97.      * 删除链表尾部节点 
  98.      *  表示 删除最少使用的缓存对象 
  99.      */  
  100.     private void removeLast() {  
  101.         //链表尾不为空,则将链表尾指向null. 删除连表尾(删除最少使用的缓存对象)  
  102.         if (last != null) {  
  103.             if (last.prev != null)  
  104.                 last.prev.next = null;  
  105.             else  
  106.                 first = null;  
  107.             last = last.prev;  
  108.         }  
  109.     }  
  110.       
  111.     /** 
  112.      * 移动到链表头,表示这个节点是最新使用过的 
  113.      * @param node 
  114.      */  
  115.     private void moveToHead(CacheNode node) {  
  116.         if (node == first)  
  117.             return;  
  118.         if (node.prev != null)  
  119.             node.prev.next = node.next;  
  120.         if (node.next != null)  
  121.             node.next.prev = node.prev;  
  122.         if (last == node)  
  123.             last = node.prev;  
  124.         if (first != null) {  
  125.             node.next = first;  
  126.             first.prev = node;  
  127.         }  
  128.         first = node;  
  129.         node.prev = null;  
  130.         if (last == null)  
  131.             last = first;  
  132.     } 
  133. }  
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics