首页 > 其他 > 详细

基于双向链表实现LRU缓存淘汰机制

时间：2016-07-07 02:13:02      阅读：310      评论：0      收藏：0      [点我收藏+]

一：LRU算法

? ? ? LRU即最近最少使用算法，常用在缓存淘汰机制里面，目前比较流行的基于内存的分布式缓存系统memcached默认就是使用LRU算法来对过期的数据进 行淘汰，比如假定我们设置缓存最多存1000条数据，当数据未达到1000条时可以一直添加，但数据超过1000条了就会使用采用的缓存淘汰算法淘汰过期 的数据。

二：链表实现原理

? ? ? 下 面的图片是在网上找的一张。原理很简单，每个节点node都持有前后节点的引用，当某个节点删除时或者某个节点被访问时都需要移动链表的位置，基于LRU 的缓存算法，当某个节点被访问的时候，将这个节点移到链表头部表示最新的数据，删除的时候，直接删除链表尾部的数据即可
bubuko.com,布布扣

三：代码实现

?

Java代码
  1. package?com.travelsky.pss.lru;??
  2. ??
  3. import?java.util.Hashtable;??
  4. import?java.util.concurrent.CountDownLatch;??
  5. import?java.util.concurrent.ExecutorService;??
  6. import?java.util.concurrent.Executors;??
  7. ??
  8. public?class?LRUCacheLinkHashMap<K,?V>?{??
  9. ??
  10. ????private?LinkCacheNode?firstNode;??
  11. ??
  12. ????private?LinkCacheNode?lastNode;??
  13. ??
  14. ????private?final?int?MAX_CACHE_SIZE;??
  15. ??
  16. ????private?Hashtable<K,?LinkCacheNode>?hashtable;??
  17. ??
  18. ????public?LRUCacheLinkHashMap(int?cacheSize)?{??
  19. ????????this.MAX_CACHE_SIZE?=?cacheSize;??
  20. ????????hashtable?=?new?Hashtable<K,?LinkCacheNode>(cacheSize);??
  21. ????}??
  22. ??
  23. ????/**?
  24. ?????*?内部类,定义节点对象?
  25. ?????*??
  26. ?????*?@author?tanjie?
  27. ?????*?
  28. ?????*/??
  29. ????class?LinkCacheNode?{??
  30. ????????//?前一个节点??
  31. ????????private?LinkCacheNode?prev;??
  32. ????????//?下一个节点??
  33. ????????private?LinkCacheNode?next;??
  34. ????????//?当前节点的key??
  35. ????????private?K?key;??
  36. ????????//?当前节点的value??
  37. ????????private?V?value;??
  38. ????}??
  39. ??
  40. ????//?当往链表里面放数据时,将最新的数据指向链表头??
  41. ????public?synchronized?void?put(K?key,?V?value)?{??
  42. ????????//?如果此时链表已经超过了最大的大小,则首先移除链表尾部的数据??
  43. ????????LinkCacheNode?cacheNode?=?getCacheNode(key);??
  44. ????????if?(null?==?cacheNode)?{??
  45. ????????????//?如果链表已经不允许放数据??
  46. ????????????if?(hashtable.size()?>=?MAX_CACHE_SIZE)?{??
  47. ????????????????if?(null?!=?lastNode)?{??
  48. ????????????????????hashtable.remove(lastNode.key);??
  49. ????????????????????//?当缓存容量满的时候,移除链表尾部的数据??
  50. ????????????????????removeLastNode();??
  51. ????????????????}??
  52. ????????????}??
  53. ????????????cacheNode?=?new?LinkCacheNode();??
  54. ????????}??
  55. ????????cacheNode.key?=?key;??
  56. ????????//?如果连接里面有值,直接修改value值即可,key不变??
  57. ????????cacheNode.value?=?value;??
  58. ????????//?新加入的移到链表头部??
  59. ????????moveToHeadNode(cacheNode);??
  60. ????????hashtable.put(key,?cacheNode);??
  61. ????????System.out.println("当前线程:"?+?Thread.currentThread().getName()??+?",put操作:firstNode:"?+?firstNode);??
  62. ????????System.out.println("当前线程:"?+?Thread.currentThread().getName()?+",put操作:lastNode:"?+?lastNode);??
  63. ????????System.out.println("=================================================");??
  64. ????}??
  65. ??
  66. ????/**?
  67. ?????*?节点的获取,模拟每次获取一次,都将该节点移动到链表头,表示最近刚被访问过?
  68. ?????*??
  69. ?????*?@param?key?
  70. ?????*?@return?
  71. ?????*/??
  72. ????public?synchronized?Object?get(K?key)?{??
  73. ????????LinkCacheNode?node?=?getCacheNode(key);??
  74. ????????if?(null?==?node)?{??
  75. ????????????return?null;??
  76. ????????}??
  77. ????????//?每次key被请求一次,就移动到链表头,模拟当前数据刚被访问过??
  78. ????????moveToHeadNode(node);??
  79. ????????System.out.println("当前线程:"?+?Thread.currentThread().getName()?+?",get操作:firstNode:"?+?firstNode);??
  80. ????????System.out.println("当前线程:"?+?Thread.currentThread().getName()?+?",get操作:lastNode:"?+?lastNode);??
  81. ????????System.out.println("================================");??
  82. ????????return?node.value;??
  83. ????}??
  84. ??
  85. ????/**?
  86. ?????*?节点的删除?
  87. ?????*??
  88. ?????*?@param?key?
  89. ?????*/??
  90. ????public?synchronized?void?remove(K?key)?{??
  91. ????????LinkCacheNode?entry?=?getCacheNode(key);??
  92. ????????if?(null?!=?entry)?{??
  93. ????????????//?设置前一个节点的引用??
  94. ????????????if?(null?!=?entry.prev)?{??
  95. ????????????????entry.prev.next?=?entry.next;??
  96. ????????????}??
  97. ????????????//?反向设置下一个节点的引用??
  98. ????????????if?(null?!=?entry.next)?{??
  99. ????????????????entry.next.prev?=?entry.prev;??
  100. ????????????}??
  101. ????????????//?如果删除的是链表头部节点,将下一个节点设置为第一个节点??
  102. ????????????if?(entry?==?firstNode)?{??
  103. ????????????????firstNode?=?entry.next;??
  104. ????????????}??
  105. ????????????//?如果删除的是链表尾部节点,将前一个节点设置为最后一个节点??
  106. ????????????if?(entry?==?lastNode)?{??
  107. ????????????????lastNode?=?entry.prev;??
  108. ????????????}??
  109. ????????}??
  110. ????????hashtable.remove(key);??
  111. ????}??
  112. ??
  113. ????/**?
  114. ?????*?将节点移动到链表头?
  115. ?????*?@param?cacheEntry?
  116. ?????*/??
  117. ????private?void?moveToHeadNode(LinkCacheNode?cacheEntry)?{??
  118. ????????//?如果当前需要移动的就是第一个位置,则不需要移动??
  119. ????????if?(cacheEntry?==?firstNode)?{??
  120. ????????????return;??
  121. ????????}??
  122. ????????//?在移动节点之前,先设置当前节点的前后节点的引用??
  123. ????????if?(null?!=?cacheEntry.prev)?{??
  124. ????????????cacheEntry.prev.next?=?cacheEntry.next;??
  125. ????????}??
  126. ????????if?(null?!=?cacheEntry.next)?{??
  127. ????????????cacheEntry.next.prev?=?cacheEntry.prev;??
  128. ????????}??
  129. ????????//?如果是最后一个节点移动到头部,将节点的前一个设置为尾部节点??
  130. ????????if?(cacheEntry?==?lastNode)?{??
  131. ????????????lastNode?=?cacheEntry.prev;??
  132. ????????}??
  133. ????????if?(null?!=?firstNode)?{??
  134. ????????????//?移动节点的下一个节点的引用指向未移动前的链表的第一个节点??
  135. ????????????cacheEntry.next?=?firstNode;??
  136. ????????????//?未移动前链表的第一个节点的前一个节点的引用指向当前移动的节点??
  137. ????????????firstNode.prev?=?cacheEntry;??
  138. ????????}??
  139. ????????//?将移动节点设置为链表头部节点??
  140. ????????firstNode?=?cacheEntry;??
  141. ????????cacheEntry.prev?=?null;??
  142. ????????if?(null?==?lastNode)?{??
  143. ????????????lastNode?=?firstNode;??
  144. ????????}??
  145. ??
  146. ????}??
  147. ??
  148. ????/**?
  149. ?????*?移除链表尾的数据?
  150. ?????*/??
  151. ????private?void?removeLastNode()?{??
  152. ????????if?(null?!=?lastNode)?{??
  153. ????????????if?(null?!=?lastNode.prev)?{??
  154. ????????????????lastNode.prev.next?=?null;??
  155. ????????????????//?只有一个节点的时候??
  156. ????????????}?else?{??
  157. ????????????????firstNode?=?null;??
  158. ????????????}??
  159. ????????????lastNode?=?lastNode.prev;??
  160. ????????}??
  161. ????}??
  162. ??
  163. ????/**?
  164. ?????*?通过key获取节点数据对象?
  165. ?????*??
  166. ?????*?@param?key?
  167. ?????*?@return?
  168. ?????*/??
  169. ????private?LinkCacheNode?getCacheNode(K?key)?{??
  170. ????????return?hashtable.get(key);??
  171. ????}??
  172. ??
  173. ????public?static?void?main(String[]?args)?throws?InterruptedException?{??
  174. ????????final?LRUCacheLinkHashMap<String,?String>?lru?=???
  175. ????????????????new?LRUCacheLinkHashMap<String,?String>(3);??
  176. ????????final?CountDownLatch?latch?=?new?CountDownLatch(15);??
  177. ????????ExecutorService?service?=?Executors.newCachedThreadPool();??
  178. ????????for(int?i=1;i<=15;i++){??
  179. ????????????final?int?index?=?i;??
  180. ????????????service.submit(new??Runnable()?{??
  181. ????????????????@Override??
  182. ????????????????public?void?run()?{??
  183. ????????????????????lru.put(String.valueOf(index),?"value:"?+?index);??
  184. ????????????????????latch.countDown();??
  185. ????????????????}??
  186. ????????????});??
  187. ????????}??
  188. ????????latch.await();?????????????????
  189. ????}??
  190. }??

??可能的运行结果如下：

Java代码
  1. 当前线程:pool-1-thread-4,put操作:firstNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@5660d6??
  2. 当前线程:pool-1-thread-4,put操作:lastNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@5660d6??
  3. =================================================??
  4. 当前线程:pool-1-thread-15,put操作:firstNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@ef83d3??
  5. 当前线程:pool-1-thread-15,put操作:lastNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@5660d6??
  6. =================================================??
  7. 当前线程:pool-1-thread-14,put操作:firstNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@88df60??
  8. 当前线程:pool-1-thread-14,put操作:lastNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@5660d6??
  9. =================================================??
  10. 当前线程:pool-1-thread-13,put操作:firstNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@1318b??
  11. 当前线程:pool-1-thread-13,put操作:lastNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@ef83d3??
  12. =================================================??
  13. 当前线程:pool-1-thread-11,put操作:firstNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@5bb966??
  14. 当前线程:pool-1-thread-11,put操作:lastNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@88df60??
  15. =================================================??
  16. 当前线程:pool-1-thread-10,put操作:firstNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@1e903d5??
  17. 当前线程:pool-1-thread-10,put操作:lastNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@1318b??
  18. =================================================??
  19. 当前线程:pool-1-thread-9,put操作:firstNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@faa550??
  20. 当前线程:pool-1-thread-9,put操作:lastNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@5bb966??
  21. =================================================??
  22. 当前线程:pool-1-thread-7,put操作:firstNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@17b6643??
  23. 当前线程:pool-1-thread-7,put操作:lastNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@1e903d5??
  24. =================================================??
  25. 当前线程:pool-1-thread-6,put操作:firstNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@76e8a7??
  26. 当前线程:pool-1-thread-6,put操作:lastNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@faa550??
  27. =================================================??
  28. 当前线程:pool-1-thread-5,put操作:firstNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@a45536??
  29. 当前线程:pool-1-thread-5,put操作:lastNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@17b6643??
  30. =================================================??
  31. 当前线程:pool-1-thread-3,put操作:firstNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@d66426??
  32. 当前线程:pool-1-thread-3,put操作:lastNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@76e8a7??
  33. =================================================??
  34. 当前线程:pool-1-thread-2,put操作:firstNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@1490eb5??
  35. 当前线程:pool-1-thread-2,put操作:lastNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@a45536??
  36. =================================================??
  37. 当前线程:pool-1-thread-1,put操作:firstNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@164b09c??
  38. 当前线程:pool-1-thread-1,put操作:lastNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@d66426??
  39. =================================================??
  40. 当前线程:pool-1-thread-12,put操作:firstNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@186f247??
  41. 当前线程:pool-1-thread-12,put操作:lastNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@1490eb5??
  42. =================================================??
  43. 当前线程:pool-1-thread-8,put操作:firstNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@8c4a77??
  44. 当前线程:pool-1-thread-8,put操作:lastNode:com.travelsky.pss.lru.LRUCacheLinkHashMap$LinkCacheNode@164b09c??
  45. =================================================??

?? 可以看到，当多个线程同时往链表添加数据的时候，当超过大小3后，最先添加的数据会被淘汰掉。

基于双向链表实现LRU缓存淘汰机制

原文：http://090508tanjie.iteye.com/blog/2308782
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！