阿里巴巴笔试考到了LRU,一激动忘了怎么回事了。。准备不充分啊。。
缓存这个东西就是为了提高运行速度的,由于缓存是在寸土寸金的内存里面,不是在硬盘里面,所以容量是很有限的。LRU这个算法就是把最近一次使用时间离现在时间最远的数据删除掉。先说说List:每次访问一个元素后把这个元素放在 List一端,这样一来最远使用的元素自然就被放到List的另一端。缓存满了t的时候就把那最远使用的元素remove掉。但更实用的是HashMap。因为List太慢,要删掉的数据总是位于List底层数组的第一个位置,删掉之后,后面的数据要向前补位。。所以复杂度是O(n),那就用链表结构的LinkedHashMap呗~,LinkedHashMap默认的元素顺序是put的顺序,但是如果使用带参数的构造函数,那么LinkedHashMap会根据访问顺序来调整内部
顺序。 LinkedHashMap的get()方法除了返回元素之外还可以把被访问的元素放到链表的底端,这样一来每次顶端的元素就是remove的元素。
构造函数如下:
publicLinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder);
initialCapacity 初始容量
loadFactor 加载因子,一般是 0.75f
accessOrder false 基于插入顺序 true 基于访问顺序(get一个元素后,这个元素被加到最后,使用了LRU 最近最少被使用的调度算法)
来个例子吧:
import java.util.*;
class Test
{
public static void main(String[] args) throws Exception{
Map<Integer,Integer> map=new LinkedHashMap<>(10,0.75f,true);
map.put(9,3);
map.put(7,4);
map.put(5,9);
map.put(3,4);
//现在遍历的话顺序肯定是9,7,5,3
//下面访问了一下9,3这个键值对,输出顺序就变喽~
map.get(9);
for(Iterator<Map.Entry<Integer,Integer>> it=map.entrySet().iterator();it.hasNext();){
System.out.println(it.next().getKey());
}
}
}
输出
7
5
3
9
好玩吧~
下面开始实现LRU缓存喽~
import java.util.*;
//扩展一下LinkedHashMap这个类,让他实现LRU算法
class LRULinkedHashMap<K,V> extends LinkedHashMap<K,V>{
//定义缓存的容量
private int capacity;
private static final long serialVersionUID = 1L;
//带参数的构造器
LRULinkedHashMap(int capacity){
//调用LinkedHashMap的构造器,传入以下参数
super(16,0.75f,true);
//传入指定的缓存最大容量
this.capacity=capacity;
}
//实现LRU的关键方法,如果map里面的元素个数大于了缓存最大容量,则删除链表的顶端元素
@Override
public boolean removeEldestEntry(Map.Entry<K, V> eldest){
System.out.println(eldest.getKey() + "=" + eldest.getValue());
return size()>capacity;
}
}
//测试类
class Test{
public static void main(String[] args) throws Exception{
//指定缓存最大容量为4
Map<Integer,Integer> map=new LRULinkedHashMap<>(4);
map.put(9,3);
map.put(7,4);
map.put(5,9);
map.put(3,4);
map.put(6,6);
//总共put了5个元素,超过了指定的缓存最大容量
//遍历结果
for(Iterator<Map.Entry<Integer,Integer>> it=map.entrySet().iterator();it.hasNext();){
System.out.println(it.next().getKey());
}
}
}
输出结果如下
9=3
9=3
9=3
9=3
9=3
7
5
3
6
分析一下:使用带参数构造器,且启用LRU模式的LinkedHashMap会在每次有新元素加入的时候,判断当前储存元素是否超过了缓存上限,也就是执行
一次removeEldestEntry方法,看最后的遍历结果,发现果然把9删除了,LRU发挥作用了~
分享到:
相关推荐
Android提供了LRUCache类,可以方便的使用它来实现LRU算法的缓存。Java提供了LinkedHashMap,可以用该类很方便的实现LRU算法,Java的LRULinkedHashMap是直接继承了LinkedHashMap,进行了极少的改动后可以实现LRU...
Android提供了LRUCache类,可以方便的使用它来实现LRU算法的缓存。Java提供了LinkedHashMap,可以用该类很方便的实现LRU算法,Java的LRULinkedHashMap就是直接继承了LinkedHashMap,进行了极少的改动后就可以实现LRU...
通过一个特殊的构造函数,三个参数的这种,最后一个布尔值参数表示是否要维护最近访问顺序,如果是 true 的话会维护最近访问的顺序,如果是 false 的话,只会维护插入...LinkedHashMap这种结构非常适合构造 LRU 缓存。
分成三级对图片进行缓存,第一级采用LinkedHashMap(LRU算法),第二季采用ConcurrentHashMap线程安全控制
这是关于Java学习的主要针对LinkedHashMap的实现原理
SDK中的LruCache类参考实现的LRU算法缓存存储类. 原理 之前分析过Lru算法的实现方式:HashMap+双向链表,参考链接: 这里主要介绍Android SDK中LruCache缓存算法的实现. 构造函数 LruCache只有一个构造函数,并且有一个...
如何用LinkedHashMap实现LRU? 如何用TreeMap实现一致性hash? ConcurrentHashMap是如何在保证并发安全的同时提高性能? ConcurrentHashMap是如何让多线程同时参与扩容? LinkedBlockingQueue、DelayQueue是如何实现...
ava基础 基础知识 ...Java集合详解5:深入理解LinkedHashMap和LRU缓存 Java集合详解6:TreeMap和红黑树 Java集合详解7:HashSet,TreeSet与LinkedHashSet Java集合详解8:Java集合类细节精讲 JavaWeb
基于LinkedHashMap实现LRU算法 PalindromeBaseArray 基于数组实现回文串的判断 链表练习 SingleLinkedList 实现单链表的增、删、改、查操作 LRUBaseLinkedList 基于单链表实现LRU算法 PalindromeBaseLinked 基于链表...
LruCacheUtils - 基于LinkedHashMap实现LRU缓存的工具类 MemcachedUtils - 基于memcached的工具类 RedisUtils - 基于redis的工具类,与redis的集群配置无缝结合 db JdbcUtils - 操作jdbc的工具类 MongodbUtils - ...
采用LinkedHashMap自带的LRU 算法缓存数据, 可检测对象是否已被虚拟机回收,并且重新计算当前缓存大小,清除缓存中无用的键值对象(即已经被虚拟机回收但未从缓存清除的数据); * 默认内存缓存大小为: 4 * 1024 * ...
cacheEhCacheUtils - 基于ehcache的工具类LruCacheUtils - 基于LinkedHashMap实现LRU缓存的工具类MemcachedUtils - 基于memcached的工具类XMemcachedUtils - 基于memcached的工具类(使用XMemcached客户端)Redis...
基于JavaLinkedHashMap实现的 LRU 算法 algorithm.consistentHashing ConsistentHash: 一致性Hash算法 algorithm.cap algorithm.subset 给一个set打印出所有子集 jdk jdk 知识 jdk.autoboxing 自动装箱拆箱 jdk....
要注意一点的是LinkedHashMap是可以实现LRU缓存策略的,前提是你需要将LinkedHashMap中的accessorder属性设置为true。 因此你基本可以认为LinkedHashMap是LinkedList和HashMap的一个组合。 LinkedHashMap简介 ...
深入Java集合学习系列(四): LinkedHashMap的实现原理
这个demo主要讲解了LinkedHashmap的使用,希望可以帮助需要的同学.
LinkedHashMap源代码,Java中Map的一种实现子类。
·课程中,Eclipse和IDEA这两种企业一线开发环境都使用到了 3.技术讲解更深入、更全面: ·课程共30天,715个知识视频小节,涉及主流Java使用的方方面面,全而不冗余 ·全程内容涵盖数据结构、设计模式、JVM内存...
如果键不存在,则设置或插入值当缓存达到其容量时,它应该在插入新项目之前使最近最少使用的项目无效 都在O(1) 解决方案 LinkedHashMap + 重写的removeEldestEntry方法备注: LinkedHashMap有两种迭代顺序:访问顺序...