java LRU(Least Recently Used )详解及实例代码

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

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！