• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

LRU 缓存实现( Java )

技术杂谈 勤劳的小蚂蚁 3个月前 (01-29) 60次浏览 已收录 0个评论 扫描二维码

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 ,具体使用什么方式看个人喜好
  1. //LinkedHashMap的一个构造函数,当参数accessOrder为true时,即会按照访问顺序排序,最近访问的放在最前,最早访问的放在后面
  2. publicLinkedHashMap(
  3.    int initialCapacity,float loadFactor,boolean accessOrder){        
  4.    super(initialCapacity, loadFactor);        
  5.    this.accessOrder = accessOrder;
  6. }
  7. //LinkedHashMap自带的判断是否删除最老的元素方法,默认返回false,即不删除老数据
  8. //我们要做的就是重写这个方法,当满足一定条件时删除老数据
  9. protectedboolean removeEldestEntry(Map.Entry<K,V> eldest){        
  10.    returnfalse;
  11. }

LRU缓存 LinkedHashMap(inheritance) 实现

采用 inheritance 方式实现比较简单,而且实现了 Map 接口,在多线程环境使用时可以使用 Collections.synchronizedMap() 方法实现线程安全操作
  1. package cn.lzrabbit.structure.lru;
  2. import java.util.LinkedHashMap;
  3. import java.util.Map;
  4. /**
  5. * Created by liuzhao on 14-5-15. */
  6. publicclassLRUCache2<K, V>extendsLinkedHashMap<K, V>{
  7.     privatefinalint MAX_CACHE_SIZE;
  8.     publicLRUCache2(int cacheSize){
  9.         super((int)Math.ceil(cacheSize /0.75)+1,0.75f,true);
  10.        MAX_CACHE_SIZE = cacheSize;
  11.    }
  12.    @Override
  13.     protectedboolean removeEldestEntry(Map.Entry eldest){
  14.         return size()> MAX_CACHE_SIZE;
  15.    }
  16.    @Override
  17.     publicString toString(){
  18.        StringBuilder sb =newStringBuilder();
  19.         for(Map.Entry<K, V> entry : entrySet()){
  20.            sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));
  21.        }
  22.        return sb.toString();
  23.    }
  24. }
这样算是比较标准的实现吧,实际使用中这样写还是有些繁琐,更实用的方法时像下面这样写,省去了单独见一个类的麻烦
  1. finalint cacheSize =100;
  2. Map<String,String> map =newLinkedHashMap<String,String>((int)Math.ceil(cacheSize /0.75f)+1,0.75f,true){
  3.    @Override
  4.    protectedboolean removeEldestEntry(Map.Entry<String,String> eldest){
  5.     return size()> cacheSize;
  6.    }
  7. };

LRU缓存 LinkedHashMap(delegation) 实现

delegation 方式实现更加优雅一些,但是由于没有实现 Map 接口,所以线程同步就需要自己搞定了
  1. package cn.lzrabbit.structure.lru;
  2. import java.util.LinkedHashMap;
  3. import java.util.Map;
  4. import java.util.Set;/**
  5. * Created by liuzhao on 14-5-13. */
  6. publicclassLRUCache3<K, V>{
  7.     privatefinalint MAX_CACHE_SIZE;
  8.     privatefinalfloat DEFAULT_LOAD_FACTOR =0.75f;
  9.    LinkedHashMap<K, V> map;
  10.     publicLRUCache3(int cacheSize){
  11.        MAX_CACHE_SIZE = cacheSize;
  12.         //根据cacheSize和加载因子计算hashmap的capactiy,+1确保当达到cacheSize上限时不会触发hashmap的扩容,
  13.        int capacity =(int)Math.ceil(MAX_CACHE_SIZE / DEFAULT_LOAD_FACTOR)+1;
  14.        map =newLinkedHashMap(capacity, DEFAULT_LOAD_FACTOR,true){
  15.        @Override
  16.        protectedboolean removeEldestEntry(Map.Entry eldest){                             return size()> MAX_CACHE_SIZE;
  17.        }
  18.        };
  19.    }    
  20.    publicsynchronizedvoid put(K key, V value){
  21.        map.put(key, value);
  22.    }
  23.     publicsynchronized V get(K key){
  24.         return map.get(key);
  25.    }
  26.     publicsynchronizedvoid remove(K key){
  27.        map.remove(key);
  28.    }
  29.     publicsynchronizedSet<Map.Entry<K, V>> getAll(){
  30.         return map.entrySet();
  31.    }
  32.     publicsynchronizedint size(){
  33.         return map.size();
  34.    }
  35.     publicsynchronizedvoid clear(){
  36.        map.clear();
  37.    }
  38.    @Override
  39.     publicString toString(){
  40.        StringBuilder sb =newStringBuilder();
  41.         for(Map.Entry entry : map.entrySet()){
  42.            sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));
  43.        }
  44.        return sb.toString();
  45.    }
  46. }

LRU Cache的链表+HashMap实现

注:此实现为非线程安全,若在多线程环境下使用需要在相关方法上添加synchronized 以实现线程安全操作
  1. package cn.lzrabbit.structure.lru;
  2. import java.util.HashMap;/**
  3. * Created by liuzhao on 14-5-12. */
  4. publicclassLRUCache1<K, V>{
  5.     privatefinalint MAX_CACHE_SIZE;
  6.     privateEntry first;
  7.     privateEntrylast;
  8.     privateHashMap<K,Entry<K, V>> hashMap;
  9.     publicLRUCache1(int cacheSize){
  10.        MAX_CACHE_SIZE = cacheSize;
  11.        hashMap =newHashMap<K,Entry<K, V>>();
  12.    }
  13.    publicvoid put(K key, V value){
  14.        Entry entry = getEntry(key);
  15.        if(entry ==null){
  16.            if(hashMap.size()>= MAX_CACHE_SIZE){
  17.                hashMap.remove(last.key);
  18.                removeLast();
  19.            }
  20.            entry =newEntry();
  21.            entry.key = key;
  22.        }
  23.        entry.value = value;
  24.        moveToFirst(entry);
  25.        hashMap.put(key, entry);
  26.    }
  27.     public V get(K key){
  28.        Entry<K, V> entry = getEntry(key);
  29.         if(entry ==null)returnnull;
  30.        moveToFirst(entry);
  31.        return entry.value;
  32.    }
  33.     publicvoid remove(K key){
  34.        Entry entry = getEntry(key);
  35.         if(entry !=null){
  36.            if(entry.pre !=null)
  37.                 entry.pre.next= entry.next;
  38.             if(entry.next!=null)
  39.                  entry.next.pre = entry.pre;
  40.             if(entry == first) first = entry.next;
  41.             if(entry ==last)last= entry.pre;
  42.        }
  43.        hashMap.remove(key);
  44.    }
  45.     privatevoid moveToFirst(Entry entry){
  46.        if(entry == first)return;
  47.        if(entry.pre !=null) entry.pre.next= entry.next;
  48.        if(entry.next!=null) entry.next.pre = entry.pre;
  49.        if(entry ==last)last=last.pre;
  50.        if(first ==null||last==null){
  51.            first =last= entry;
  52.            return;
  53.        }
  54.        entry.next= first;
  55.        first.pre = entry;
  56.        first = entry;
  57.        entry.pre =null;
  58.    }
  59.    privatevoid removeLast(){
  60.         if(last!=null){
  61.            last=last.pre;
  62.            if(last==null) first =null;
  63.            elselast.next=null;
  64.        }
  65.    }
  66.    privateEntry<K, V> getEntry(K key){
  67.         return hashMap.get(key);
  68.    }
  69.    @Override
  70.     publicString toString(){
  71.        StringBuilder sb =newStringBuilder();
  72.        Entry entry = first;
  73.         while(entry !=null){
  74.            sb.append(String.format("%s:%s ", entry.key, entry.value));
  75.            entry = entry.next;
  76.        }
  77.         return sb.toString();
  78.    }
  79.     classEntry<K, V>{
  80.         publicEntry pre;
  81.         publicEntrynext;
  82.         public K key;
  83.         public V value;
  84.    }
  85. }

LinkedHashMap的FIFO实现

FIFO是First Input First Output的缩写,也就是常说的先入先出,默认情况下LinkedHashMap就是按照添加顺序保存,我们只需重写下removeEldestEntry方法即可轻松实现一个FIFO缓存,简化版的实现代码如下
  1. finalint cacheSize =5;
  2. LinkedHashMap<Integer,String> lru =newLinkedHashMap<Integer,String>(){
  3.    @Override    protectedboolean removeEldestEntry(Map.Entry<Integer,String> eldest){    return size()> cacheSize;
  4.    }
  5. };

测试

  1. publicclassLRUCacheTest  {    
  2. publicstaticvoid main(String[] args)throwsException{
  3.        System.out.println("start...");
  4.        lruCache1();
  5.        lruCache2();
  6.        lruCache3();
  7.        lruCache4();
  8.        System.out.println("over...");
  9.    }
  10. staticvoid lruCache1(){
  11.        System.out.println();
  12.        System.out.println("===========================LRU 链表实现===========================");
  13.        LRUCache1<Integer,String> lru =newLRUCache1(5);
  14.        lru.put(1,"11");
  15.        lru.put(2,"11");
  16.        lru.put(3,"11");
  17.        lru.put(4,"11");
  18.        lru.put(5,"11");
  19.        System.out.println(lru.toString());
  20.        lru.put(6,"66");
  21.        lru.get(2);
  22.        lru.put(7,"77");
  23.        lru.get(4);
  24.        System.out.println(lru.toString());
  25.        System.out.println();
  26.    }
  27.    static   <T>void lruCache2(){
  28.        System.out.println();
  29.        System.out.println("===========================LRU LinkedHashMap(inheritance)实现===========================");
  30.        LRUCache2<Integer,String> lru =newLRUCache2(5);
  31.        lru.put(1,"11");
  32.        lru.put(2,"11");
  33.        lru.put(3,"11");
  34.        lru.put(4,"11");
  35.        lru.put(5,"11");
  36.        System.out.println(lru.toString());
  37.        lru.put(6,"66");
  38.        lru.get(2);
  39.        lru.put(7,"77");
  40.        lru.get(4);
  41.        System.out.println(lru.toString());
  42.        System.out.println();
  43.    }  
  44.    static  void lruCache3(){
  45.        System.out.println();
  46.        System.out.println("===========================LRU LinkedHashMap(delegation)实现===========================");
  47.        LRUCache3<Integer,String> lru =newLRUCache3(5);
  48.        lru.put(1,"11");
  49.        lru.put(2,"11");
  50.        lru.put(3,"11");
  51.        lru.put(4,"11");
  52.        lru.put(5,"11");
  53.        System.out.println(lru.toString());
  54.        lru.put(6,"66");
  55.        lru.get(2);
  56.        lru.put(7,"77");
  57.        lru.get(4);
  58.        System.out.println(lru.toString());
  59.        System.out.println();
  60.    }  
  61.    static  void lruCache4(){
  62.        System.out.println();
  63.        System.out.println("===========================FIFO LinkedHashMap默认实现===========================");        finalint cacheSize =5;
  64.        LinkedHashMap<Integer,String> lru =newLinkedHashMap<Integer,String>(){
  65.            @Override            
  66.        protectedboolean removeEldestEntry(Map.Entry<Integer,String> eldest){                return size()> cacheSize;
  67.            }
  68.        };
  69.        lru.put(1,"11");
  70.        lru.put(2,"11");
  71.        lru.put(3,"11");
  72.        lru.put(4,"11");
  73.        lru.put(5,"11");
  74.        System.out.println(lru.toString());
  75.        lru.put(6,"66");
  76.        lru.get(2);
  77.        lru.put(7,"77");
  78.        lru.get(4);
  79.        System.out.println(lru.toString());
  80.        System.out.println();
  81.    }
  82. }
运行结果
  1. "C:Program Files (x86)Javajdk1.6.0_10binjava"-Didea.launcher.port=7535"-Didea.launcher.bin.path=C:Program Files (x86)JetBrainsIntelliJ IDEA 13.0.2bin"-Dfile.encoding=UTF-8-classpath "C:Program Files (x86)Javajdk1.6.0_10jrelibcharsets.jar;C:Program Files (x86)Javajdk1.6.0_10jrelibdeploy.jar;C:Program Files (x86)Javajdk1.6.0_10jrelibjavaws.jar;C:Program Files (x86)Javajdk1.6.0_10jrelibjce.jar;C:Program Files (x86)Javajdk1.6.0_10jrelibjsse.jar;C:Program Files (x86)Javajdk1.6.0_10jrelibmanagement-agent.jar;C:Program Files (x86)Javajdk1.6.0_10jrelibplugin.jar;C:Program Files (x86)Javajdk1.6.0_10jrelibresources.jar;C:Program Files (x86)Javajdk1.6.0_10jrelibrt.jar;C:Program Files (x86)Javajdk1.6.0_10jrelibextdnsns.jar;C:Program Files (x86)Javajdk1.6.0_10jrelibextlocaledata.jar;C:Program Files (x86)Javajdk1.6.0_10jrelibextsunjce_provider.jar;C:Program Files (x86)Javajdk1.6.0_10jrelibextsunmscapi.jar;C:Program Files (x86)Javajdk1.6.0_10jrelibextsunpkcs11.jar;D:SVNprojectsJavaJava.Algorithmtargettest-classes;D:SVNprojectsJavaJava.Algorithmtargetclasses;C:Program Files (x86)JetBrainsIntelliJ IDEA 13.0.2libidea_rt.jar" com.intellij.rt.execution.application.AppMainMain
  2. start...===========================LRU 链表实现===========================
  3. 5:114:113:112:111:11
  4. 4:117:772:116:665:11
  5. ===========================LRU LinkedHashMap(inheritance)实现===========================
  6. 1:112:113:114:115:11
  7. 5:116:662:117:774:11
  8. ===========================LRU LinkedHashMap(delegation)实现===========================
  9. 1:112:113:114:115:11
  10. 5:116:662:117:774:11
  11. ===========================FIFO LinkedHashMap默认实现==========================={1=11,2=11,3=11,4=11,5=11}
  12. {3=11,4=11,5=11,6=66,7=77}
  13. over...
  14. Process finished withexit code 0

丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:LRU 缓存实现( Java )
喜欢 (0)
[247507792@qq.com]
分享 (0)
勤劳的小蚂蚁
关于作者:
温馨提示:本文来源于网络,转载文章皆标明了出处,如果您发现侵权文章,请及时向站长反馈删除。

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00