yeskery

简单的 LRU Cache 设计与实现

介绍

LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。

实现

最常见的实现是使用一个链表保存缓存数据,详细算法实现如下:

  1. public class LRUCache<K, V> {
  2. /**
  3. * 节点类
  4. */
  5. class Node {
  6. /** 父节点 */
  7. Node parent;
  8. /** 子节点 */
  9. Node child;
  10. /** 散列表的键 */
  11. K key;
  12. /** 散列表的值 */
  13. V value;
  14. /**
  15. * 节点类的构造方法
  16. * @param key 散列表的键
  17. * @param value 散列表的值
  18. */
  19. private Node(K key, V value) {
  20. this.key = key;
  21. this.value = value;
  22. }
  23. @Override
  24. public String toString() {
  25. return "Node{" +
  26. "key=" + key +
  27. ", value=" + value +
  28. '}';
  29. }
  30. }
  31. /** 缓存的最大容量 */
  32. private final int capacity;
  33. /** 当前缓存的实际大小 */
  34. private int size;
  35. /** 头节点 */
  36. private Node root;
  37. /** 尾节点 */
  38. private Node tail;
  39. /**
  40. * LRU 缓存对象的构造方法
  41. * @param capacity 缓存的最大容量
  42. */
  43. public LRUCache(int capacity) {
  44. this.capacity = capacity;
  45. }
  46. /**
  47. * 根据散列表的键从缓存中取出散列表中对应的值
  48. * @param key 散列表的键
  49. * @return 散列表中对应的值
  50. */
  51. public V get(K key) {
  52. Node node = searchNode(key);
  53. if (node != null) {
  54. V value = node.value;
  55. //如果root节点是查找节点则无需提升节点
  56. if (node == root) {
  57. return value;
  58. }
  59. //进行节点提升
  60. setHeaderNode(node);
  61. return value;
  62. }
  63. return null;
  64. }
  65. /**
  66. * 向缓存中放入一组缓存键值
  67. * @param key 散列表的键
  68. * @param value 散列表的值
  69. */
  70. public void put(K key, V value) {
  71. if (root == null) {
  72. root = new Node(key, value);
  73. tail = root;
  74. size++;
  75. return;
  76. }
  77. if (get(key) != null) {
  78. root.value = value;
  79. return;
  80. }
  81. if (size < capacity) {
  82. size++;
  83. } else {
  84. //移除队尾节点
  85. //如果是尾节点是根节点
  86. if (tail == root) {
  87. root = null;
  88. tail = null;
  89. } else {
  90. //有且仅有根尾两个节点
  91. if (root.child == tail && tail.parent == root) {
  92. root.child = null;
  93. tail.parent = null;
  94. tail = root;
  95. } else {
  96. Node tempNode = tail.parent;
  97. tail.parent = null;
  98. tempNode.child = null;
  99. tail = tempNode;
  100. }
  101. }
  102. }
  103. Node node = new Node(key, value);
  104. node.child = root;
  105. if (root != null) {
  106. root.parent = node;
  107. }
  108. root = node;
  109. if (tail == null) {
  110. tail = root;
  111. }
  112. }
  113. @Override
  114. public String toString() {
  115. StringBuilder stringBuilder = new StringBuilder("size=");
  116. stringBuilder.append(size).append(",data=[");
  117. for (Node node = root; node != null; node = node.child) {
  118. stringBuilder.append(node.key).append("=").append(node.value).append(",");
  119. }
  120. if (stringBuilder.charAt(stringBuilder.length() - 1) == ',') {
  121. stringBuilder.deleteCharAt(stringBuilder.length() - 1);
  122. }
  123. stringBuilder.append("]");
  124. return stringBuilder.toString();
  125. }
  126. /**
  127. * 根据key进行节点搜索
  128. * @param key key
  129. * @return 搜索到的节点
  130. */
  131. private Node searchNode(K key) {
  132. if (size < 1) {
  133. return null;
  134. } else if (size == 1) {
  135. return root.key.equals(key) ? root : null;
  136. } else if (size == 2) {
  137. return root.key.equals(key) ? root : tail.key.equals(key) ? tail : null;
  138. }
  139. Node left = root, right = tail;
  140. while (left != right && left.child != right && right.parent != left) {
  141. if (left.key.equals(key)) {
  142. return left;
  143. }
  144. if (right.key.equals(key)) {
  145. return right;
  146. }
  147. left = left.child;
  148. right = right.parent;
  149. }
  150. return left.key.equals(key) ? left : right.key.equals(key) ? right : null;
  151. }
  152. /**
  153. * 将指定节点提升到根节点
  154. * @param target 指定的节点
  155. */
  156. private void setHeaderNode(Node target) {
  157. Node source = root;
  158. //只有两个节点
  159. if (size == 2) {
  160. source.parent = target;
  161. target.child = source;
  162. source.child = null;
  163. target.parent = null;
  164. root = target;
  165. tail = source;
  166. } else if (target == tail) {
  167. //尾节点需要提升到根节点
  168. target.parent.child = null;
  169. tail = target.parent;
  170. target.parent = null;
  171. target.child = source;
  172. source.parent = target;
  173. root = target;
  174. } else {
  175. //中间节点需要提升到根节点
  176. Node tempNode1 = target.child;
  177. Node tempNode2 = target.parent;
  178. tempNode1.parent = tempNode2;
  179. tempNode2.child = tempNode1;
  180. target.child = source;
  181. source.parent = target;
  182. target.parent = null;
  183. root = target;
  184. }
  185. }
  186. public static void main(String[] args) {
  187. long start = System.currentTimeMillis();
  188. LRUCache<Integer, Integer> cache = new LRUCache<>(2048);
  189. Random random = new Random();
  190. for (int i = 0;i < 5000;i++) {
  191. int value = random.nextInt(1000);
  192. if (random.nextBoolean()) {
  193. cache.put(value, value);
  194. } else {
  195. System.out.println(cache.get(value));
  196. }
  197. }
  198. System.out.printf("running time: %dms", System.currentTimeMillis() - start);
  199. }

评论

发表评论 点击刷新验证码

提示

该功能暂未开放