java lru(least recently used )详解
lru是least recently used 的缩写，翻译过来就是“最近最少使用”，lru缓存就是使用这种原理实现，简单的说就是缓存一定量的数据，当超过设定的阈值时就把一些过期的数据删除掉，比如我们缓存10000条数据，当数据小于10000时可以随意添加，当超过10000时就需要把新的数据添加进来，同时要把过期数据删除，以确保我们最大缓存10000条，那怎么确定删除哪条过期数据呢，采用lru算法实现的话就是将最老的数据删掉，废话不多说，下面来说下java版的lru缓存实现
java里面实现lru缓存通常有两种选择，一种是使用linkedhashmap，一种是自己设计数据结构，使用链表+hashmap
lru cache的linkedhashmap实现
linkedhashmap自身已经实现了顺序存储，默认情况下是按照元素的添加顺序存储，也可以启用按照访问顺序存储，即最近读取的数据放在最前面，最早读取的数据放在最后面，然后它还有一个判断是否删除最老数据的方法，默认是返回false，即不删除数据，我们使用linkedhashmap实现lru缓存的方法就是对linkedhashmap实现简单的扩展，扩展方式有两种，一种是inheritance，一种是delegation，具体使用什么方式看个人喜好
我要评论
//linkedhashmap的一个构造函数，当参数accessorder为true时，即会按照访问顺序排序，最近访问的放在最前，最早访问的放在后面
public linkedhashmap(int initialcapacity, float loadfactor, boolean accessorder) {
super(initialcapacity, loadfactor);
this.accessorder = accessorder;
}
//linkedhashmap自带的判断是否删除最老的元素方法，默认返回false，即不删除老数据
//我们要做的就是重写这个方法，当满足一定条件时删除老数据
protected boolean removeeldestentry(map.entry<k,v> eldest) {
return false;
}
lru缓存linkedhashmap(inheritance)实现
采用inheritance方式实现比较简单，而且实现了map接口，在多线程环境使用时可以使用 collections.synchronizedmap()方法实现线程安全操作
package cn.lzrabbit.structure.lru;
import java.util.linkedhashmap;
import java.util.map;
/**
* created by liuzhao on 14-5-15.
*/
public class lrucache2<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;
}
@override
public string tostring() {
stringbuilder sb = new stringbuilder();
for (map.entry<k, v> entry : entryset()) {
sb.append(string.format("%s:%s ", entry.getkey(), entry.getvalue()));
}
return sb.tostring();
}
}
这样算是比较标准的实现吧，实际使用中这样写还是有些繁琐，更实用的方法时像下面这样写，省去了单独见一个类的麻烦
final int cachesize = 100;
map<string, string> map = new linkedhashmap<string, string>((int) math.ceil(cachesize / 0.75f) + 1, 0.75f, true) {
@override
protected boolean removeeldestentry(map.entry<string, string> eldest) {
return size() > cachesize;
}
};
lru缓存linkedhashmap(delegation)实现
delegation方式实现更加优雅一些，但是由于没有实现map接口，所以线程同步就需要自己搞定了
package cn.lzrabbit.structure.lru;
import java.util.linkedhashmap;
import java.util.map;
import java.util.set;
/**
* created by liuzhao on 14-5-13.
*/
public class lrucache3<k, v> {
private final int max_cache_size;
private final float default_load_factor = 0.75f;
linkedhashmap<k, v> map;
public lrucache3(int cachesize) {
max_cache_size = cachesize;
//根据cachesize和加载因子计算hashmap的capactiy，+1确保当达到cachesize上限时不会触发hashmap的扩容，
int capacity = (int) math.ceil(max_cache_size / default_load_factor) + 1;
map = new linkedhashmap(capacity, default_load_factor, true) {
@override
protected boolean removeeldestentry(map.entry eldest) {
return size() > max_cache_size;
}
};
}
public synchronized void put(k key, v value) {
map.put(key, value);
}
public synchronized v get(k key) {
return map.get(key);
}
public synchronized void remove(k key) {
map.remove(key);
}
public synchronized set<map.entry<k, v>> getall() {
return map.entryset();
}
public synchronized int size() {
return map.size();
}
public synchronized void clear() {
map.clear();
}
@override
public string tostring() {
stringbuilder sb = new stringbuilder();
for (map.entry entry : map.entryset()) {
sb.append(string.format("%s:%s ", entry.getkey(), entry.getvalue()));
}
return sb.tostring();
}
}
lru cache的链表+hashmap实现
注：此实现为非线程安全，若在多线程环境下使用需要在相关方法上添加synchronized以实现线程安全操作
package cn.lzrabbit.structure.lru;
import java.util.hashmap;
/**
* created by liuzhao on 14-5-12.
*/
public class lrucache1<k, v> {
private final int max_cache_size;
private entry first;
private entry last;
private hashmap<k, entry<k, v>> hashmap;
public lrucache1(int cachesize) {
max_cache_size = cachesize;
hashmap = new hashmap<k, entry<k, v>>();
}
public void put(k key, v value) {
entry entry = getentry(key);
if (entry == null) {
if (hashmap.size() >= max_cache_size) {
hashmap.remove(last.key);
removelast();
}
entry = new entry();
entry.key = key;
}
entry.value = value;
movetofirst(entry);
hashmap.put(key, entry);
}
public v get(k key) {
entry<k, v> entry = getentry(key);
if (entry == null) return null;
movetofirst(entry);
return entry.value;
}
public void remove(k key) {
entry entry = getentry(key);
if (entry != null) {
if (entry.pre != null) entry.pre.next = entry.next;
if (entry.next != null) entry.next.pre = entry.pre;
if (entry == first) first = entry.next;
if (entry == last) last = entry.pre;
}
hashmap.remove(key);
}
private void movetofirst(entry entry) {
if (entry == first) return;
if (entry.pre != null) entry.pre.next = entry.next;
if (entry.next != null) entry.next.pre = entry.pre;
if (entry == last) last = last.pre;
if (first == null || last == null) {
first = last = entry;
return;
}
entry.next = first;
first.pre = entry;
first = entry;
entry.pre = null;
}
private void removelast() {
if (last != null) {
last = last.pre;
if (last == null) first = null;
else last.next = null;
}
}
private entry<k, v> getentry(k key) {
return hashmap.get(key);
}
@override
public string tostring() {
stringbuilder sb = new stringbuilder();
entry entry = first;
while (entry != null) {
sb.append(string.format("%s:%s ", entry.key, entry.value));
entry = entry.next;
}
return sb.tostring();
}
class entry<k, v> {
public entry pre;
public entry next;
public k key;
public v value;
}
}
linkedhashmap的fifo实现
fifo是first input first output的缩写，也就是常说的先入先出，默认情况下linkedhashmap就是按照添加顺序保存，我们只需重写下removeeldestentry方法即可轻松实现一个fifo缓存，简化版的实现代码如下
final int cachesize = 5;
linkedhashmap<integer, string> lru = new linkedhashmap<integer, string>() {
@override
protected boolean removeeldestentry(map.entry<integer, string> eldest) {
return size() > cachesize;
}
};
调用示例
package cn.lzrabbit.structure.lru;
import cn.lzrabbit.itest;
import java.util.linkedhashmap;
import java.util.map;
/**
* created by liuzhao on 14-5-15.
*/
public class lrucachetest {
public static void main(string[] args) throws exception {
system.out.println("start...");
lrucache1();
lrucache2();
lrucache3();
lrucache4();
system.out.println("over...");
}
static void lrucache1() {
system.out.println();
system.out.println("===========================lru 链表实现===========================");
lrucache1<integer, string> lru = new lrucache1(5);
lru.put(1, "11");
lru.put(2, "11");
lru.put(3, "11");
lru.put(4, "11");
lru.put(5, "11");
system.out.println(lru.tostring());
lru.put(6, "66");
lru.get(2);
lru.put(7, "77");
lru.get(4);
system.out.println(lru.tostring());
system.out.println();
}
static <t> void lrucache2() {
system.out.println();
system.out.println("===========================lru linkedhashmap(inheritance)实现===========================");
lrucache2<integer, string> lru = new lrucache2(5);
lru.put(1, "11");
lru.put(2, "11");
lru.put(3, "11");
lru.put(4, "11");
lru.put(5, "11");
system.out.println(lru.tostring());
lru.put(6, "66");
lru.get(2);
lru.put(7, "77");
lru.get(4);
system.out.println(lru.tostring());
system.out.println();
}
static void lrucache3() {
system.out.println();
system.out.println("===========================lru linkedhashmap(delegation)实现===========================");
lrucache3<integer, string> lru = new lrucache3(5);
lru.put(1, "11");
lru.put(2, "11");
lru.put(3, "11");
lru.put(4, "11");
lru.put(5, "11");
system.out.println(lru.tostring());
lru.put(6, "66");
lru.get(2);
lru.put(7, "77");
lru.get(4);
system.out.println(lru.tostring());
system.out.println();
}
static void lrucache4() {
system.out.println();
system.out.println("===========================fifo linkedhashmap默认实现===========================");
final int cachesize = 5;
linkedhashmap<integer, string> lru = new linkedhashmap<integer, string>() {
@override
protected boolean removeeldestentry(map.entry<integer, string> eldest) {
return size() > cachesize;
}
};
lru.put(1, "11");
lru.put(2, "11");
lru.put(3, "11");
lru.put(4, "11");
lru.put(5, "11");
system.out.println(lru.tostring());
lru.put(6, "66");
lru.get(2);
lru.put(7, "77");
lru.get(4);
system.out.println(lru.tostring());
system.out.println();
}
}
运行结果
"c:\program files (x86)\java\jdk1.6.0_10\bin\java" -didea.launcher.port=7535 "-didea.launcher.bin.path=c:\program files (x86)\jetbrains\intellij idea 13.0.2\bin" -dfile.encoding=utf-8 -classpath "c:\program files (x86)\java\jdk1.6.0_10\jre\lib\charsets.jar;c:\program files (x86)\java\jdk1.6.0_10\jre\lib\deploy.jar;c:\program files (x86)\java\jdk1.6.0_10\jre\lib\javaws.jar;c:\program files (x86)\java\jdk1.6.0_10\jre\lib\jce.jar;c:\program files (x86)\java\jdk1.6.0_10\jre\lib\jsse.jar;c:\program files (x86)\java\jdk1.6.0_10\jre\lib\management-agent.jar;c:\program files (x86)\java\jdk1.6.0_10\jre\lib\plugin.jar;c:\program files (x86)\java\jdk1.6.0_10\jre\lib\resources.jar;c:\program files (x86)\java\jdk1.6.0_10\jre\lib\rt.jar;c:\program files (x86)\java\jdk1.6.0_10\jre\lib\ext\dnsns.jar;c:\program files (x86)\java\jdk1.6.0_10\jre\lib\ext\localedata.jar;c:\program files (x86)\java\jdk1.6.0_10\jre\lib\ext\sunjce_provider.jar;c:\program files (x86)\java\jdk1.6.0_10\jre\lib\ext\sunmscapi.jar;c:\program files (x86)\java\jdk1.6.0_10\jre\lib\ext\sunpkcs11.jar;d:\svn\projects\java\java.algorithm\target\test-classes;d:\svn\projects\java\java.algorithm\target\classes;c:\program files (x86)\jetbrains\intellij idea 13.0.2\lib\idea_rt.jar" com.intellij.rt.execution.application.appmain main
start...
===========================lru 链表实现===========================
5:11 4:11 3:11 2:11 1:11
4:11 7:77 2:11 6:66 5:11
===========================lru linkedhashmap(inheritance)实现===========================
1:11 2:11 3:11 4:11 5:11
5:11 6:66 2:11 7:77 4:11
===========================lru linkedhashmap(delegation)实现===========================
1:11 2:11 3:11 4:11 5:11
5:11 6:66 2:11 7:77 4:11
===========================fifo linkedhashmap默认实现===========================
{1=11, 2=11, 3=11, 4=11, 5=11}
{3=11, 4=11, 5=11, 6=66, 7=77}
over...
process finished with exit code 0
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
如对本文有疑问， 点击进行留言回复！！
详解SpringBoot修改启动端口server.port的四种方式
网友评论