作 者: haifeiWu 原文链接: https://www.hchstudio.cn/article/2019/9a45/ 版权声明:非特殊声明均为本站原创作品,转载时请注明作者和原文链接。
由于版权原因,请阅读原文 --> LRU 算法
作 者: haifeiWu 原文链接: https://www.hchstudio.cn/article/2019/9a45/ 版权声明:非特殊声明均为本站原创作品,转载时请注明作者和原文链接。
作 者: haifeiWu 原文链接: https://www.hchstudio.cn/article/2019/9a45/ 版权声明:非特殊声明均为本站原创作品,转载时请注明作者和原文链接。
What ? LRU 是 Least Recently Used 的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间 t,当须淘汰一个页面时,选择现有页面中其 t 值最大的,即最近最久未使用的页面予以淘汰。-百科 上面是对操作系统中 LRU 算法的阐述,本文说的 LRU 主要是指该算法在业务层的缓存算法中的应用,总而言之,基本的实现逻辑是一样的。
How ? 算法思想:
1,新数据插入到链表头部。
2,每当缓存命中(即缓存数据被访问),则将数据移到链表头部。
3,当链表满的时候,将链表尾部的数据丢弃。
算法实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 class Node { public Node (String key,String value) { this .key = key; this .value = value; } public Node pre; public Node next; public String key; public String value; } public class LRUCache { private Node head; private Node end; private int limit; private HashMap map; public LRUCache (int limit) { this .limit = limit; map = new HashMap(); } public String get (String key) { Node node = map.get(key); if (node == null ) { return null ; } refreshNode(node); return node.value; } public void put (String key, String value) { Node node = map.get(key); if (node == null ) { while (map.size() >= limit) { String oldKey = removeNode(head); map.remove(oldKey); } node = new Node(key, value); addNode(node); map.put(key, node); } else { node.value = value; refreshNode(node); } } private void refreshNode (Node node) { if (node == end) { return ; } removeNode(node); addNode(node); } private String removeNode (Node node) { if (node == end) { end = end.pre; } else if (node == head) { head = head.next; } else { node.pre.next = node.next; node.next.pre = node.pre; } return node.key; } private void addNode (Node node) { if (end != null ) { end.next = node; node.pre = end; node.next = null ; } end = node; if (head == null ) { head = node; } } }
JDK 中的算法实现 通常不需要我们自己专门实现一个此算法的数据结构,使用 JDK 内置的 LinkedHashMap 稍加改造即可。1 2 3 4 5 6 7 8 9 10 11 12 13 14 public class LRUCache <K , V > extends LinkedHashMap <K , V > { private final int MAX_CACHE_SIZE; public LRUCache2 (int cacheSize) { super ((int ) Math.ceil(cacheSize / 0.75 ) + 1 , 0.75f , true ); MAX_CACHE_SIZE = cacheSize; } @Override protected boolean removeEldestEntry (Map.Entry eldest) { return size() > MAX_CACHE_SIZE; } }
mybatis 中的 LRU 算法实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 public class LruCache implements Cache { private final Cache delegate; private Map<Object, Object> keyMap; private Object eldestKey; public LruCache (Cache delegate) { this .delegate = delegate; setSize(1024 ); } @Override public String getId () { return delegate.getId(); } @Override public int getSize () { return delegate.getSize(); } public void setSize (final int size) { keyMap = new LinkedHashMap<Object, Object>(size, .75F , true ) { private static final long serialVersionUID = 4267176411845948333L ; @Override protected boolean removeEldestEntry (Map.Entry<Object, Object> eldest) { boolean tooBig = size() > size; if (tooBig) { eldestKey = eldest.getKey(); } return tooBig; } }; } @Override public void putObject (Object key, Object value) { delegate.putObject(key, value); cycleKeyList(key); } @Override public Object getObject (Object key) { keyMap.get(key); return delegate.getObject(key); } @Override public Object removeObject (Object key) { return delegate.removeObject(key); } @Override public void clear () { delegate.clear(); keyMap.clear(); } @Override public ReadWriteLock getReadWriteLock () { return null ; } private void cycleKeyList (Object key) { keyMap.put(key, key); if (eldestKey != null ) { delegate.removeObject(eldestKey); eldestKey = null ; } } }
作 者: haifeiWu 原文链接: https://www.hchstudio.cn/article/2019/9a45/ 版权声明:非特殊声明均为本站原创作品,转载时请注明作者和原文链接。