简单LRU算法实现缓存-update2

pengzhaocheng16

浏览: 180346 次
性别:
来自: 广州

最近访客更多访客>>

cljuan0603

84303988

gsm0251321

z268l830

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

缓存算法

这次我们向大家介绍几种缓存中常见的算法，让各位对缓存算法有一个比较初步的了解。
贝莱蒂算法（Belady's Algorithm）
最有效率的缓存算法会丢掉未来最长时间内不使用的数据。这种理想情况被称作贝莱蒂最优算法或者千里眼算法。由于要预计数据要多久后才被使用基本上是不可能的，所以这种算法没有实际的可操作性。它的作用在于为不同的缓存算法订立一个优劣标准。
最近最少使用算法(LRU，Least Recently Used）
最近最少使用算法的思路是丢弃近段时间内最少被使用的数据。要实现这种算法需要跟踪数据何时被使用，用这种方法来筛选去近一段时间被最少使用次数的数据其代价往往是昂贵的。它的实现往往是通过在缓存数据上设立时间标志位，用以跟踪最近最少被使用的缓存数据。一个数据每被使用一次，其他数据的时间标志位数值就要增加。
最近最频繁使用算法（MRU，Most Recently Used）
最近最频繁使用算法和最近最少使用算法相反，它会首先丢弃最近最常使用的数据。有观点认为“当文件在顺序访问时，MRU算法是最佳选择”，抱有这样观点人也认为在反复进行大量数据的随机存储时，MRU因为倾向于保留旧的数据，随意比LRU算法有着更高的命中率。MRU算法经常用于旧的数据更常被用到的情况下。
伪LRU算法（PLRU，Pseudo-LRU）
因为缓存有着大量的关联性，LRU算法实现的代价往往比较昂贵。如果实际情况在丢弃任一个最近最少使用的数据就能满足，那么伪LRU算法就派上用场了，它为每一个缓存数据设立一个标志位就可以工作。
====================================
简单LRU算法实现缓存-update2
Posted on 2007-09-29 17:49 dennis 阅读(4845) 评论(5) 编辑收藏所属分类: java 、数据结构与算法、my open-source
update1:第二个实现，读操作不必要采用独占锁，缓存显然是读多于写，读的时候一开始用独占锁是考虑到要递增计数和更新时间戳要加锁，不过这两个变量都是采用原子变量，因此也不必采用独占锁，修改为读写锁。
update2:一个错误，老是写错关键字啊，LRUCache的maxCapacity应该声明为volatile，而不是transient。

import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
   
   最简单的LRU算法实现，就是利用jdk的LinkedHashMap，覆写其中的removeEldestEntry(Map.Entry)方法即可，如下所示：
import java.util.ArrayList;
import java.util.Map;


/**
 * 类说明：利用LinkedHashMap实现简单的缓存， 必须实现removeEldestEntry方法，具体参见JDK文档
 * 
 * @author dennis
 * 
 * @param <K>
 * @param <V>
 */
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 boolean containsKey(Object key) {
        try {
            lock.lock();
            return super.containsKey(key);
        } finally {
            lock.unlock();
        }
    }

    
    @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();
        }
    }

    public int size() {
        try {
            lock.lock();
            return super.size();
        } finally {
            lock.unlock();
        }
    }

    public void clear() {
        try {
            lock.lock();
            super.clear();
        } finally {
            lock.unlock();
        }
    }

    public Collection<Map.Entry<K, V>> getAll() {
        try {
            lock.lock();
            return new ArrayList<Map.Entry<K, V>>(super.entrySet());
        } finally {
            lock.unlock();
        }
    }
}

如果你去看LinkedHashMap的源码可知，LRU算法是通过双向链表来实现，当某个位置被命中，通过调整链表的指向将该位置调整到头位置，新加入的内容直接放在链表头，如此一来，最近被命中的内容就向链表头移动，需要替换时，链表最后的位置就是最近最少使用的位置。
LRU算法还可以通过计数来实现，缓存存储的位置附带一个计数器，当命中时将计数器加1，替换时就查找计数最小的位置并替换，结合访问时间戳来实现。这种算法比较适合缓存数据量较小的场景，显然，遍历查找计数最小位置的时间复杂度为O(n)。我实现了一个，结合了访问时间戳，当最小计数大于MINI_ACESS时(这个参数的调整对命中率有较大影响），就移除最久没有被访问的项：

package net.rubyeye.codelib.util.concurrency.cache;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

/**
 * 
 * @author dennis 类说明：当缓存数目不多时，才用缓存计数的传统LRU算法
 * @param <K>
 * @param <V>
 */
public class LRUCache<K, V> implements Serializable {

    private static final int DEFAULT_CAPACITY = 100;

    protected Map<K, ValueEntry> map;

    private final ReadWriteLock lock = new ReentrantReadWriteLock();

    private final Lock readLock = lock.readLock();

    private final Lock writeLock = lock.writeLock();

    private final volatile int maxCapacity;  //保持可见性

    public static int MINI_ACCESS = 5;

    public LRUCache() {
        this(DEFAULT_CAPACITY);
    }

    public LRUCache(int capacity) {
        if (capacity <= 0)
            throw new RuntimeException("缓存容量不得小于0");
        this.maxCapacity = capacity;
        this.map = new HashMap<K, ValueEntry>(maxCapacity);
    }

    public boolean ContainsKey(K key) {
        try {
            readLock.lock();
            return this.map.containsKey(key);
        } finally {
            readLock.unlock();
        }
    }

    public V put(K key, V value) {
        try {
            writeLock.lock();
            if ((map.size() > maxCapacity - 1) && !map.containsKey(key)) {
                // System.out.println("开始");
                Set<Map.Entry<K, ValueEntry>> entries = this.map.entrySet();
                removeRencentlyLeastAccess(entries);
            }
            ValueEntry new_value = new ValueEntry(value);
            ValueEntry old_value = map.put(key, new_value);
            if (old_value != null) {
                new_value.count = old_value.count;
                return old_value.value;
            } else
                return null;
        } finally {
            writeLock.unlock();
        }
    }

    /**
     * 移除最近最少访问
     */
    protected void removeRencentlyLeastAccess(
            Set<Map.Entry<K, ValueEntry>> entries) {
        // 最小使用次数
        long least = 0;
        // 访问时间最早
        long earliest = 0;
        K toBeRemovedByCount = null;
        K toBeRemovedByTime = null;
        Iterator<Map.Entry<K, ValueEntry>> it = entries.iterator();
        if (it.hasNext()) {
            Map.Entry<K, ValueEntry> valueEntry = it.next();
            least = valueEntry.getValue().count.get();
            toBeRemovedByCount = valueEntry.getKey();
            earliest = valueEntry.getValue().lastAccess.get();
            toBeRemovedByTime = valueEntry.getKey();
        }
        while (it.hasNext()) {
            Map.Entry<K, ValueEntry> valueEntry = it.next();
            if (valueEntry.getValue().count.get() < least) {
                least = valueEntry.getValue().count.get();
                toBeRemovedByCount = valueEntry.getKey();
            }
            if (valueEntry.getValue().lastAccess.get() < earliest) {
                earliest = valueEntry.getValue().count.get();
                toBeRemovedByTime = valueEntry.getKey();
            }
        }
        // System.out.println("remove:" + toBeRemoved);
        // 如果最少使用次数大于MINI_ACCESS，那么移除访问时间最早的项(也就是最久没有被访问的项）
        if (least > MINI_ACCESS) {
            map.remove(toBeRemovedByTime);
        } else {
            map.remove(toBeRemovedByCount);
        }
    }

    public V get(K key) {
        try {
            readLock.lock();
            V value = null;
            ValueEntry valueEntry = map.get(key);
            if (valueEntry != null) {
                // 更新访问时间戳
                valueEntry.updateLastAccess();
                // 更新访问次数
                valueEntry.count.incrementAndGet();
                value = valueEntry.value;
            }
            return value;
        } finally {
            readLock.unlock();
        }
    }

    public void clear() {
        try {
            writeLock.lock();
            map.clear();
        } finally {
            writeLock.unlock();
        }
    }

    public int size() {
        try {
            readLock.lock();
            return map.size();
        } finally {
            readLock.unlock();
        }
    }

    public long getCount(K key) {
        try {
            readLock.lock();
            ValueEntry valueEntry = map.get(key);
            if (valueEntry != null) {
                return valueEntry.count.get();
            }
            return 0;
        } finally {
            readLock.unlock();
        }
    }

    public Collection<Map.Entry<K, V>> getAll() {
        try {
            readLock.lock();
            Set<K> keys = map.keySet();
            Map<K, V> tmp = new HashMap<K, V>();
            for (K key : keys) {
                tmp.put(key, map.get(key).value);
            }
            return new ArrayList<Map.Entry<K, V>>(tmp.entrySet());
        } finally {
            readLock.unlock();
        }
    }

    class ValueEntry implements Serializable {
        private V value;

        private AtomicLong count;

        private AtomicLong lastAccess;

        public ValueEntry(V value) {
            this.value = value;
            this.count = new AtomicLong(0);
            lastAccess = new AtomicLong(System.nanoTime());
        }

        public void updateLastAccess() {
            this.lastAccess.set(System.nanoTime());
        }

    }
}

分享到：