java基础--自己动手实现一个LRU
目录
- LinkedHashMap 实现
- 继承 LinkedHashMap
- 组合 LinkedHashMap
- 链表 + HashMap 实现
要实现 LRU,需要做到两点:
- 查询出最近最晚使用的项
- 给最近使用的项做一个标记
- LinkedHashMap
- 双向链表 + HashMap
LinkedHashMap 实现
利用 LinkedHashMap 的原因就在于 LinkedHashMap 是有序的,默认情况下是按照元素的添加顺序存储的,也可以调整为根据访问顺序来调整内部顺序(设置参数 accessOrder 进行调整),即最近读取的数据放在最前面,我们就是利用 LinkedHashMap 的这个特性来实现 LRU。先来一个简单的例子吧:
public static void main(String[] args){Map map = new LinkedHashMap(10,0.75f,true); map.put("1","a"); map.put("2","b"); map.put("3","c"); map.put("4","d"); System.out.println("原始顺序为:"); for(Iteratorit = map.entrySet().iterator(); it.hasNext(); ){System.out.print(it.next().getKey() + ""); }System.out.println(); map.get("2"); System.out.println("访问 4 之后的顺序为:"); for(Iterator it = map.entrySet().iterator(); it.hasNext(); ){System.out.print(it.next().getKey() + ""); }}
运行结果:
原始顺序为:1234访问 4 之后的顺序为:1342
更多关于 LinkedHashMap,请看这篇文章:LinkedHashMap
LinkedHashMap 实现 LRU 有两种方式,一种是继承 LinkedHashMap,一种是利用组合的方式,下面分别演示这两种情况。
继承 LinkedHashMap
采用继承的方式实现起来是非常简单的,因为 LinkedHashMap 本身就已经具备了 LRU 的特性,我们只需要实现一点:当容器中元素个数超过我们设定的容量后,删除第一个元素即可。同时由于 LinkedHashMap 本身不具备线程安全,我们需要确保他线程安全,这个也很简单,重写 LinkedHashMap 的
get()
和 put()
方法即可,或者使用 Collections.synchronizedMap() 方法也可以。实现如下:public class LRUCacheLinkedHashMapextends LinkedHashMap { /*** 定一缓存容量*/private int capacity; LRUCacheLinkedHashMap(int capacity){// AccessOrder = truesuper(capacity,0.75f,true); this.capacity = capacity; } /*** 实现LRU的关键方法,如果 map 里面的元素个数大于了缓存最大容量,则删除链表的顶端元素** @param eldest* @return*/@Overridepublic boolean removeEldestEntry(Map.Entry eldest){System.out.println(eldest.getKey() + "=" + eldest.getValue()); return size()>capacity; } @Overridepublic synchronized V get(Object key) {return super.get(key); } @Overridepublic synchronized V put(K key, V value) {return super.put(key, value); }}
验证
public static void main(String[] args){LRUCacheLinkedHashMap cache = new LRUCacheLinkedHashMap(5); cache.put("1","a"); cache.put("2","b"); cache.put("3","c"); cache.put("4","d"); cache.put("5","e"); System.out.println("插入 5 个元素后的顺序"); printlnCache(cache); // 插入第 6 个元素cache.put("6","e"); System.out.println("插入第 6 个元素后的顺序"); printlnCache(cache); // 访问 第 3 个元素cache.get("3"); System.out.println("访问元素 3 后的顺序"); printlnCache(cache); } private static void printlnCache(LRUCacheLinkedHashMap cacheMap){for(Iteratorit = cacheMap.entrySet().iterator(); it.hasNext(); ){System.out.print(it.next().getKey() + ""); }System.out.println(); }
运行结果:
插入 5 个元素后的顺序12345插入第 6 个元素后的顺序23456访问元素 3 后的顺序24563
运行结果完全符合我们的预期
组合 LinkedHashMap
使用组合的方式可能会更加优雅些,但是由于没有实现 Map 接口,所以就不能使用
Collections.synchronizedMap()
方式来保证线程安全性了,所以需要在每个方法处增加 synchronized 来确保线程安全。实现方式如下:public class LRUCache{private int capacity; private Map cacheMap; public LRUCache(int capacity){this.capacity = capacity; cacheMap = new LinkedHashMap<>(capacity,0.75f,true); } public synchronized void put(K k,V v){cacheMap.put(k,v); // 移除第一个元素if(cacheMap.size() > capacity){K first = this.keyIterator().next(); cacheMap.remove(first); }} public synchronized V get(K k){return cacheMap.get(k); } public Iterator keyIterator(){return cacheMap.keySet().iterator(); }}
验证:
public static void main(String[] args) {LRUCache lruCache = new LRUCache(5); lruCache.put("1","a"); lruCache.put("2","b"); lruCache.put("3","c"); lruCache.put("4","d"); lruCache.put("5","e"); System.out.println("插入 5 个元素后的顺序"); println(lruCache); // 插入第 6 个元素lruCache.put("6","e"); System.out.println("插入 第 6 个元素后的顺序"); println(lruCache); // 访问 第 3 个元素lruCache.get("3"); System.out.println("访问元素 3 后的顺序"); println(lruCache); } private static void println(LRUCache lruCache){for(Iterator it = lruCache.keyIterator(); it.hasNext(); ){System.out.print(it.next() + ""); }System.out.println(); }
运行结果如下:
插入 5 个元素后的顺序12345插入 第 6 个元素后的顺序23456访问元素 3 后的顺序24563
组合的方式也显得非常简单,有两点需要注意:
- 保证每个方法的线程安全
- put 时,需要查看当前容量是否超过设置的容量,超过则需要删除第一个元素。当然小编这种是实现方式不是很优雅,这么做知识为了能够更加好阐述 LRU 的实现。更好的方案是在构造 LinkedHashMap 时,重写
removeEldestEntry(),
如下:
cacheMap = new LinkedHashMap(capacity,0.75f,true){@Overrideprotected boolean removeEldestEntry(Map.Entry eldest) {return size()>capacity; }};
链表 + HashMap 实现
我们想想,在不利用现存数据结构的条件(如 LinkedHashMap)如何实现一个 LRU 呢?缓存部分容易实现,我们都知道利用 HashMap 即可,但是如何实现缓存容量不足时丢弃最不常用的数据的功能?
- 利用时间戳。每一个访问,增加的元素我们都给其更新一个时间戳,在 put 的时候,检查,删除时间戳最小的就可以了。这种方法可以实现,但是代价较高,就是我们需要遍历整个数据,得到最小的时间戳。
- 我们可以换位思考,我们其实不需要关注每个节点的增加或者遍历时间,我们只需要知道那个节点是最先访问就可以了,所以我们可以利用链表记录访问记录,有新数据加入时放在链表的 head 节点,每次访问也将该数据放在 head 节点,那么链表的 tail 一定是最早访问的节点,所以每次当容量不足的时候删除 tail 节点数据并将它的前驱节点设置为 tail 就可以了。注意,这个链表是一个双向链表。代码如下:
public class LinkedLRUCache{ private int capacity; private Map map; private LRUNode head; private LRUNode tail; LinkedLRUCache(int capacity){this.capacity = capacity; this.map = new HashMap<>(); } public synchronized void put(K k,V v){LRUNode node = map.get(k); // 存在该 key,将节点的设置为 headif(node != null){node.value = https://www.it610.com/article/v; remove(node,false); }else{/*** 该节点不存在* 1、将该节点加入缓存* 2、设置该节点为 head* 3、判断是否超出容量*/node = new LRUNode(k,v); if(map.size()>= capacity){//删除 tail 节点remove(tail,true); } map.put(k,node); setHead(node); } // 设置当前节点为首节点setHead(node); } public Object get(String key) {LRUNode node = map.get(key); if (node != null) {// 将刚操作的元素放到headremove(node, false); setHead(node); return node.value; }return null; } /*** 设置头结点** @param node*/private void setHead(LRUNode node) {if(head != null){node.next = head; head.prev = node; } head = node; if(tail == null){tail = node; }} /*** 从链表中删除此Node** @param node* @param flag为 true 就删除该节点的 key*/private void remove(LRUNode node,boolean flag) {if (node.prev != null) {node.prev.next = node.next; } else {head = node.next; }if (node.next != null) {node.next.prev = node.prev; } else {tail = node.prev; }node.next = null; node.prev = null; if (flag) {map.remove(node.key); }}private Iterator iterator(){return map.keySet().iterator(); } private class LRUNode { /*** cache 的 key*/private K key; /*** cache 的 value*/private V value; private LRUNode next; private LRUNode prev; LRUNode(K key, V value) {this.key = key; this.value = https://www.it610.com/article/value; }}}
【java基础--自己动手实现一个LRU】验证
public static void main(String[] args){LRUCache lruCache = new LRUCache(5); lruCache.put("1","a"); lruCache.put("2","b"); lruCache.put("3","c"); lruCache.put("4","d"); lruCache.put("5","e"); System.out.println("插入 5 个元素"); println(lruCache); System.out.println("插入 3 元素"); lruCache.put("3","c"); println(lruCache); System.out.println("插入第6 个元素"); lruCache.put("6","f"); println(lruCache); System.out.println("访问 4 元素"); lruCache.get("4"); println(lruCache); }private static void println(LRUCache lruCache){Iterator iterator = lruCache.keyIterator(); while (iterator.hasNext()){System.out.print(iterator.next() + ""); }System.out.println(); }
执行结果:
插入 5 个元素12345插入 3 元素12453插入第6 个元素24536访问 4 元素25364
到此这篇关于java基础--自己动手实现一个LRU的文章就介绍到这了,更多相关java LRU内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家!
推荐阅读
- JAVA(抽象类与接口的区别&重载与重写&内存泄漏)
- 尽力
- 牛人进化+|牛人进化+ 按自己的意愿过一生
- 别怪生活,自己作的!
- 事件代理
- 放下心中的偶像包袱吧
- Java|Java OpenCV图像处理之SIFT角点检测详解
- 靈魂裡有香氣的人
- 改变自己,先从自我反思开始
- java中如何实现重建二叉树