LRU的几种实现方式

[TFdream]

一、 什么是LRU？

LRU 即 Least Rencetly Used（最近最少使用）缓存替换策略。在任何LRU算法中，它必定有以下两个策略组成：

• 退化 策略。根据访问情况，对节点按热度进行排序（hot->cold），以便决定哪些节点是热节点（hot）的，哪些节点是冷节点（cold）的。
• 清除 策略。即去掉那些cold的数据。
  • 替换。这个在操作系统缓存中应该是一个常用的做法。
  • 删除。删除掉数据，以腾出空间放新的数据。（因为内存是有限的）

其中，退化的策略，一般按以下两种方式去处理：

• 非集中式：即每命中一次就进行退化操作。 非集中式的退化操作，往往由双向链表的方式去实现。每次命中之后就移动命中节点在链表中的位置。（位置靠前的就是hot的数据）。当然，复杂的策略中，有用queue数组进行hot分级等。
• 集中式：定期去进行退化操作。 在集中式的退化操作，常用的策略是：每次命中之后，记录一个时间戳、定时器时间点等等参数。由一个线程去扫描，定期清除老数据。

实现方式

基于LinkedHashMap

import java.util.LinkedHashMap;  
import java.util.concurrent.locks.Lock;  
import java.util.concurrent.locks.ReentrantLock;  

public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V>  {  
    private final int maxCapacity;  
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;  
    private final Lock lock = new ReentrantLock();  

    public LRULinkedHashMap(int maxCapacity) {  
        super(maxCapacity, DEFAULT_LOAD_FACTOR, true);  
        this.maxCapacity = maxCapacity;  
    }  

    @Override  
    protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest)  {  
        return size() > maxCapacity;  
    }  

    @Override  
    public V get(Object key)  {  
        try {  
            lock.lock();  
            return super.get(key);  
        } finally {  
            lock.unlock();  
        }  
    }  

    @Override  
    public V put(K key, V value)  {  
        try {  
            lock.lock();  
            return super.put(key, value);  
        } finally {  
            lock.unlock();  
        }  
    }

    @Override
    public V remove(Object key) {
        try {
            lock.lock();
            return super.remove(key);
        } finally {
            lock.unlock();
        }
    }
}

相关资料

• 阿里中间件团队博客 - ConcurrentHaspLRUHashMap实现初探