`

使用LinkedHashMap构建LRU的Cache

阅读更多

这段时间好好整理了一下基础,发现很多对我来说新的东西,里面博大精深的东西真的很多,经常使用HashMap,对HashMap的结构和原理非常了解,但是忽略了还有LinkedHashMap这个好东西。

 

先转一篇blog:

 

LinkedHashMap的特性:
Linked内部含有一个private transient Entry header;来记录元素插入的顺序或者是元素被访问的顺序。利用这个线性结构的对象,可以帮助记录entry加入的前后顺序或者记录entry被访问的 频率(最少被访问的entry靠前,最近访问的entry靠后)。大致的过程如下:

new LinkedHashMap(10, 0.75, true);
其中前面两个参数就是HashMap构造函数需要的参数,后面的true表明LinkedHashMap按照访问的次序来排序。
按照访问的次序来排序的含义:当调用LinkedHashMap的get(key)或者put(key, value)时,碰巧key在map中被包含,那么LinkedHashMap会将key对象的entry放在线性结构的最后。
按照插入顺序来排序的含义:调用get(key), 或者put(key, value)并不会对线性结构产生任何的影响。

正是因为LinkedHashMap提供按照访问的次序来排序的功能,所以它才需要改写HashMap的get(key)方法(HashMap不需要排序)和HashMap.Entry的recordAccess(HashMap)方法
public Object get(Object key) {
        Entry e = (Entry)getEntry(key);
        if (e == null)
            return null;
        e.recordAccess(this);
        return e.value;
    }

void recordAccess(HashMap m) {
            LinkedHashMap lm = (LinkedHashMap)m;
            if (lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }
注 意addBefore(lm.header)是将该entry放在header线性表的最后。(参考LinkedHashMap.Entry extends HashMap.Entry 比起HashMap.Entry多了before, after两个域,是双向的)

至于put(key, value)方法, LinkedHashMap不需要去改写,用HashMap的就可以了,因为HashMap在其put(key, value)方法里边已经预留了e.recordAccess(this);

还有一个方法值得关注:
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return false;
    }
当 调用put(key, value)的时候,HashMap判断是否要自动增加map的size的作法是判断是否超过threshold, LinkedHashMap则进行了扩展,如果removeEldestEntry方法return false;(默认的实现),那么LinkedHashMap跟HashMap处理扩容的方式一致;如果removeEldestEntry返回 true,那么LinkedHashMap会自动删掉最不常用的那个entry(也就是header线性表最前面的那个)。

这会造成严重的性能问题吗?答案当然是否定的。因为在这儿的链表操作是常量级的。这也是LinkedHashMap/Set在这儿比TreeMap/Set性能更高的原因。

同样,LinkedHashMap/Set也不是thread-safe的。如果在多线程下访问,是需要进行外部同步,或者使用Collections.synchronizedMap()的方法包装成一个thread-safe的Map/Set。

特别需要注意的是,在使用“访问顺序”时,读取节点操作也是“结构变化”的操作。因为,这会改变元素遍历的顺序。所以,在使用 LinkedHashMap的iterator()方法,遍历元素时,如果其它线程有读取操作,也要进行同步。否则,也会抛出同其它fail-fast一 样的由于删除或增加操作而引起的CurrentModificationException的例外。
最后,LinkedHashMap缺省是使用插入顺序的,如何构造一个访问顺序的LinkedHashMap呢?很简单: public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) accessOrder = true 即可。

 

回来补充一个利用LinkedHashMap来实现LRU的Cache类,看了上面的特性,实现起来实在太简单了!

 

package lru;

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;

/**
 *
 *<p>Test</p>
 *<p>Description:</P>
 *<p>Company:Cisco CAS</p>
 *<p>Department:CAS</p>
 *@Author: Tommy Zhou
 *@Since: 1.0
 *@Version:Date:2011-5-13
 *
 **/

public class LRUCache<K,V> extends LinkedHashMap<K, V>{
    private LinkedHashMap<K,V>  cache =null ;
    private int cacheSize = 0;
      
    public LRUCache(int cacheSize){
        this.cacheSize = cacheSize;
        int hashTableCapacity = (int) Math.ceil (cacheSize / 0.75f) + 1;
        cache = new LinkedHashMap<K, V>(hashTableCapacity, 0.75f,true)
        {
            // (an anonymous inner class)
            private static final long serialVersionUID = 1;

            @Override
            protected boolean removeEldestEntry (Map.Entry<K, V> eldest)
            {
                System.out.println("size="+size());
                return size () > LRUCache.this.cacheSize;
            }
        };
    }
  
    public V put(K key,V value){
        return cache.put(key, value);
    }

    public V get(Object key){
        return cache.get(key);
    }
   
    public static void main(String[] args) {
        LRUCache<String, String> lruCache = new LRUCache<String, String>(5);
        lruCache.put("1", "1");
        lruCache.put("2", "2");
        lruCache.put("3", "3");
        lruCache.put("4", "4");
       
        System.out.println(lruCache.get("2"));
        lruCache.get("2");
        lruCache.put("6", "6");
        lruCache.put("5", "5");
        System.out.println(lruCache.get("1"));
       
       
       
       
    }

}

分享到:
评论

相关推荐

    Java实现LRU算法.zip

    在Java中实现LRU算法,通常会使用数据结构如HashMap或LinkedHashMap来存储页面及其访问信息。HashMap提供快速的查找操作,而LinkedHashMap则同时保持了插入顺序,这对于实现LRU至关重要,因为我们需要快速找到最近...

    lru.rar_LRU

    在实际编程中,可以使用各种编程语言的库来实现LRU,例如Python的`functools.lru_cache`,Java的`LinkedHashMap`,或者是C++的自定义实现。 总之,LRU算法是一种高效的内存管理策略,通过优先淘汰最近最少使用的...

    LRU算法--utils工具包

    这篇博客文章可能讨论了如何使用这些工具来构建一个LRU缓存系统。 首先,我们来看`LRUCache.java`。这个文件很可能是实现了一个自定义的LRU缓存结构。`LRUCache`通常会包含一个内部类来维护一个双向链表,用于记录...

    基于Java实现缓存Cache的深入分析

    本文将深入探讨如何使用Java实现一个基于LinkedHashMap的LRU(Least Recently Used,最近最少使用)缓存策略。 LRU缓存策略的基本思想是:当缓存满时,优先淘汰最近最少使用的数据。在Java中,LinkedHashMap类提供...

    java-lru-demo:这是LRU算法的实现

    LRU(Least Recently Used)算法是一种常用的页面替换策略,它基于“最近最少使用”的原则...通过学习这个项目,你可以掌握如何在Java中利用`LinkedHashMap`来构建高效的缓存系统,以及如何根据业务需求调整缓存策略。

    javalruleetcode-LeetCode-Solutions:LeetCode-解决方案

    在 Java 中实现 LRUCache,我们可以利用 LinkedHashMap 这个数据结构,它具有访问顺序和插入顺序的特性,非常适合构建 LRU 缓存。 首先,我们需要了解 LinkedHashMap 的三个关键属性: 1. accessOrder:布尔值,...

    LRUCache实现 同步LRUCache

    LRUCache(Least Recently Used Cache)是一种常用的缓存淘汰策略,它基于“最近最少使用”的原则,当缓存满时,会优先淘汰最近最不常使用的数据。在Java中,虽然标准库没有直接提供LRUCache,但我们可以通过自定义...

    java高速文件缓存

    1. LRU(Least Recently Used):最近最少使用策略,当缓存满时,淘汰最近最少使用的数据。 2. LFU(Least Frequently Used):最不经常使用策略,淘汰使用频率最低的数据。 3. FIFO(First In First Out):先进先...

    基于Java的实例源码-Java缓存工具 SimpleCache.zip

    2. **实现类**:`SimpleCache`可能是实现`Cache`接口的具体类,它可能使用了Java集合框架中的数据结构,如HashMap或LinkedHashMap来存储缓存项,并且可能实现了缓存过期策略,比如基于时间的过期或者基于LRU(Least ...

    Redis面试专题及答案(下).pdf

    以下是一个使用Java实现的LRU缓存示例,基于`LinkedHashMap`: ```java import java.util.LinkedHashMap; import java.util.Map; public class LRUCache, V&gt; extends LinkedHashMap, V&gt; { private final int ...

    LRUCache:用Java实现的小型LRUCache。 不顾编码测试而制造

    LRUCache(Least Recently Used Cache)是一种常用的缓存淘汰策略,它基于“最近最少使用”的原则,当缓存满时,会优先淘汰最近最不常使用的数据。在Java中实现LRUCache,我们可以利用Java 8引入的`java.util....

    eviction-hashmap

    - 可以使用链表和哈希表组合的方式实现,比如Java的LinkedHashMap,它可以维护元素的插入顺序或访问顺序,方便实现LRU策略。 - 使用第三方库,如Google的Guava库中的Cache,它提供了丰富的缓存配置和自动剔除策略...

    PhotoWall:照片墙

    这个项目的核心是实现一个高效的照片加载策略,通过采用LrcCache(Least Recently Used Cache,最近最少使用缓存)来优化图片的加载速度和内存使用,为用户提供快速、无卡顿的浏览体验。 在瀑布流布局中,照片会...

Global site tag (gtag.js) - Google Analytics