如何用LinkedHashMap实现LRU缓存算法

LinkedHashMap   2014-09-12 22:00:16 发布
您的评价:
     
5.0
收藏     2收藏
文件夹
标签
(多个标签用逗号分隔)

缓存这个东西就是为了提高运行速度的,由于缓存是在寸土寸金的内存里面,不是在硬盘里面,所以容量是很有限的。LRU这个算法就是把最近一次使用时间离现在时间最远的数据删除掉。先说说List:每次访问一个元素后把这个元素放在 List一端,这样一来最远使用的元素自然就被放到List的另一端。缓存满了t的时候就把那最远使用的元素remove掉。但更实用的是 HashMap。因为List太慢,要删掉的数据总是位于List底层数组的第一个位置,删掉之后,后面的数据要向前补位。。所以复杂度是O(n),那就用链表结构的LinkedHashMap呗~,LinkedHashMap默认的元素顺序是put的顺序,但是如果使用带参数的构造函数,那么 LinkedHashMap会根据访问顺序来调整内部 顺序。 LinkedHashMap的get()方法除了返回元素之外还可以把被访问的元素放到链表的底端,这样一来每次顶端的元素就是remove的元素。

构造函数如下:

public LinkedHashMap (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发挥作用了~

扩展阅读

使用LinkedHashMap实现LRU缓存
Android内存优化之内存缓存
简单的java缓存实现
LRU缓存介绍与实现 (Java)
Android获取远程图片并本地缓存

为您推荐

JQuery经典总结
利用HTML5 Canvas对text文本进行渲染;
java发送内嵌图片邮件
基于Html5的网页大头贴
Spring3+Hibernate4+SpringMVC整合Ext:开发Ext界面

更多

LinkedHashMap
算法
相关文档  — 更多
相关经验  — 更多
相关讨论  — 更多