LRU缓存介绍与实现 (Java)

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

1. public class LRUCache {
2. private int cacheSize;
3. private Hashtable<Object, Entry> nodes;//缓存容器
4. private int currentSize;
5. private Entry first;//链表头
6. private Entry last;//链表尾
7. public LRUCache(int i) {
8. currentSize = 0;
9. cacheSize = i;
10. nodes = new Hashtable<Object, Entry>(i);//缓存容器
11. }
12. /**
13. * 获取缓存中对象,并把它放在最前面
14. */
15. public Entry get(Object key) {
16. Entry node = nodes.get(key);
17. if (node != null) {
18. moveToHead(node);
19. return node;
20. } else {
21. return null;
22. }
23. }
24. /**
25. * 添加 entry到hashtable, 并把entry
26. */
27. public void put(Object key, Object value) {
28. //先查看hashtable是否存在该entry, 如果存在，则只更新其value
29. Entry node = nodes.get(key);
30. if (node == null) {
31. //缓存容器是否已经超过大小.
32. if (currentSize >= cacheSize) {
33. nodes.remove(last.key);
34. removeLast();
35. } else {
36. currentSize++;
37. }
38. node = new Entry();
39. }
40. node.value = value;
41. //将最新使用的节点放到链表头，表示最新使用的.
42. moveToHead(node);
43. nodes.put(key, node);
44. }
45. /**
46. * 将entry删除, 注意：删除操作只有在cache满了才会被执行
47. */
48. public void remove(Object key) {
49. Entry node = nodes.get(key);
50. //在链表中删除
51. if (node != null) {
52. if (node.prev != null) {
53. node.prev.next = node.next;
54. }
55. if (node.next != null) {
56. node.next.prev = node.prev;
57. }
58. if (last == node)
59. last = node.prev;
60. if (first == node)
61. first = node.next;
62. }
63. //在hashtable中删除
64. nodes.remove(key);
65. }
66. /**
67. * 删除链表尾部节点，即使用最后 使用的entry
68. */
69. private void removeLast() {
70. //链表尾不为空,则将链表尾指向null. 删除连表尾（删除最少使用的缓存对象）
71. if (last != null) {
72. if (last.prev != null)
73. last.prev.next = null;
74. else
75. first = null;
76. last = last.prev;
77. }
78. }
79. /**
80. * 移动到链表头，表示这个节点是最新使用过的
81. */
82. private void moveToHead(Entry node) {
83. if (node == first)
84. return;
85. if (node.prev != null)
86. node.prev.next = node.next;
87. if (node.next != null)
88. node.next.prev = node.prev;
89. if (last == node)
90. last = node.prev;
91. if (first != null) {
92. node.next = first;
93. first.prev = node;
94. }
95. first = node;
96. node.prev = null;
97. if (last == null)
98. last = first;
99. }
100. /*
101. * 清空缓存
102. */
103. public void clear() {
104. first = null;
105. last = null;
106. currentSize = 0;
107. }
108. }
109. class Entry {
110. Entry prev;//前一节点
111. Entry next;//后一节点
112. Object value;//值
113. Object key;//键
114. }

115. leetcode 146. LRU Cache 链表操作与缓存处理

     2017年08月06日 12:11:26 Hackerzer 阅读数 568更多

     分类专栏： 算法

      
     版权声明：本文为博主原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。

     本文链接：https://blog.csdn.net/chengdezhi2011/article/details/76762623

     1.  
        public class LRUCache {
     2.  
        class DlinkedNote{
     3.  
        int key;
     4.  
        int value;
     5.  
        DlinkedNote pre;
     6.  
        DlinkedNote post;
     7.  
        DlinkedNote(){}
     8.  
        DlinkedNote(int key, int value){
     9.  
        this.key = key;
     10.  
         this.value = value;
     11.  
         }
     12.  
         }
     13.  
          
     14.  
         HashMap<Integer, DlinkedNote> cache = new HashMap<Integer, DlinkedNote>();
     15.  
         int capacity;
     16.  
         DlinkedNote head;
     17.  
         DlinkedNote tail;
     18.  
          
     19.  
          
     20.  
         public DlinkedNote poptail(){
     21.  
         DlinkedNote res = tail.pre;
     22.  
         removenode(res);
     23.  
         return res;
     24.  
         }
     25.  
          
     26.  
         public void movetohead(DlinkedNote node){
     27.  
         removenode(node);
     28.  
         addnode(node);
     29.  
         }
     30.  
          
     31.  
         public void removenode(DlinkedNote node){
     32.  
         DlinkedNote pre = node.pre;
     33.  
         DlinkedNote post = node.post;
     34.  
         pre.post = post;
     35.  
         post.pre = pre;
     36.  
         }
     37.  
          
     38.  
         /** always add at the head of link*/
     39.  
         public void addnode(DlinkedNote node){
     40.  
         DlinkedNote cur_first = this.head.post;
     41.  
         cur_first.pre = node;
     42.  
         node.post = cur_first;
     43.  
         node.pre = this.head;
     44.  
         this.head.post = node;
     45.  
         }
     46.  
          
     47.  
         public LRUCache(int capacity) {
     48.  
         DlinkedNote head = new DlinkedNote();
     49.  
         DlinkedNote tail = new DlinkedNote();
     50.  
         head.post = tail;
     51.  
         tail.pre = head;
     52.  
         this.head = head;
     53.  
         this.tail = tail;
     54.  
         this.capacity = capacity;
     55.  
         // this.count = 0;
     56.  
         }
     57.  
          
     58.  
         public int get(int key) {
     59.  
         DlinkedNote res = cache.get(key);
     60.  
         if(res==null){
     61.  
         return -1;
     62.  
         }
     63.  
         movetohead(res);
     64.  
         return res.value;
     65.  
         }
     66.  
          
     67.  
         public void put(int key, int value) {
     68.  
         DlinkedNote node = cache.get(key);
     69.  
         int count = cache.size();
     70.  
         if(node==null){
     71.  
         DlinkedNote new_node = new DlinkedNote(key, value);
     72.  
         this.cache.put(key, new_node);
     73.  
         addnode(new_node);
     74.  
         count++;
     75.  
         // while(count>this.capacity)
     76.  
         if(count>this.capacity){
     77.  
         DlinkedNote last = this.poptail();
     78.  
         cache.remove(last.key);
     79.  
         }
     80.  
         }else{
     81.  
         if(node.value!=value){
     82.  
         node.value = value;
     83.  
         }
     84.  
         movetohead(node);
     85.  
         }
     86.  
         }
     87.