简单LRU算法实现缓存-update2

update1:第二个实现，读操作不必要采用独占锁，缓存显然是读多于写，读的时候一开始用独占锁是考虑到要递增计数和更新时间戳要加锁，不过这两个变量都是采用原子变量，因此也不必采用独占锁，修改为读写锁。
update2:一个错误，老是写错关键字啊，LRUCache的maxCapacity应该声明为volatile，而不是transient。
  
   最简单的LRU算法实现，就是利用jdk的LinkedHashMap，覆写其中的removeEldestEntry(Map.Entry)方法即可，如下所示：

import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
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());
        }

    }
}

文章转自庄周梦蝶  ，原文发布时间2007-09-29

时间： 2024-08-26 03:46:45

简单LRU算法实现缓存-update2的相关文章

缓存淘汰算法--LRU算法

[本文转载于缓存淘汰算法--LRU算法] 1. LRU 1.1. 原理 LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是"如果数据最近被访问过,那么将来被访问的几率也更高". 1.2. 实现 最常见的实现是使用一个链表保存缓存数据,详细算法实现如下: 1. 新数据插入到链表头部: 2. 每当缓存命中(即缓存数据被访问),则将数据移到链表头部: 3. 当链表满的时候,将链表尾部的数据丢弃. 1.3. 分析 [命中率] 当

PreloadDataCache支持预取的数据缓存，使用简单，支持多种缓存算法，支持不同网络类型，扩展性强

主要特性:(1).使用简单 (2).可自动预取新数据 (3).可选择多种缓存算法(包括FIFO.LIFO.LRU.MRU.LFU.MFU等15种)或自定义缓存算法 (4).省流量性能佳(有且仅有一个线程获取数据) (5).支持不同类型网络处理 (6)缓存可序列化到本地 缓存可从文件中恢复 (7).扩展性强 (8). 包含map的大多数接口 适用:Java和Android开发中获取数据较耗时的应用,如网络通讯.响应慢数据获取,在类似网易新闻.花瓣这类应用中可以起到很好的效果.对于图片缓存可直接使用

Android图片缓存之Lru算法（二）_Android

前言: 上篇我们总结了Bitmap的处理,同时对比了各种处理的效率以及对内存占用大小,点击查看.我们得知一个应用如果使用大量图片就会导致OOM(out of memory),那该如何处理才能近可能的降低oom发生的概率呢?之前我们一直在使用SoftReference软引用,SoftReference是一种现在已经不再推荐使用的方式,因为从 Android 2.3 (API Level 9)开始,垃圾回收器会更倾向于回收持有软引用或弱引用的对象,这让软引用变得不再可靠,所以今天我们来认识一种新的缓

Android图片缓存之Lru算法（二）

前言: 上篇我们总结了Bitmap的处理,同时对比了各种处理的效率以及对内存占用大小,点击查看.我们得知一个应用如果使用大量图片就会导致OOM(out of memory),那该如何处理才能近可能的降低oom发生的概率呢?之前我们一直在使用SoftReference软引用,SoftReference是一种现在已经不再推荐使用的方式,因为从 Android 2.3 (API Level 9)开始,垃圾回收器会更倾向于回收持有软引用或弱引用的对象,这让软引用变得不再可靠,所以今天我们来认识一种新的缓

LRU算法简单例子

package com.aspboy.base.cache; /* * Created on 2004-8-18 *  *"最近最少使用算法"(LRU算法),它是将最近一段时间内最少被访问过的行淘汰出局. *因此需要为每行设置一个计数器,LRU算法是把命中行的计数器清零,其他各行计数器加1. *当需要替换时淘汰行计数器计数值最大的数据行出局. *这是一种高效.科学的算法,其计数器清零过程可以把一些频繁调用后再不需要的数据淘汰出Cache, *提高Cache的利用率. */ import

Python实现LRU算法的2种方法

  这篇文章主要介绍了Python实现LRU算法的2种方法,本文分别给出了用OrderedDict实现.用dict+list实现两种方法,需要的朋友可以参考下 LRU:least recently used,最近最少使用算法.它的使用场景是:在有限的空间中存储对象时,当空间满时,会按一定的原则删除原有的对象,常用的原则(算法)有LRU,FIFO,LFU等.在计算机的Cache硬件,以及主存到虚拟内存的页面置换,还有Redis缓存系统中都用到了该算法.我在一次面试和一个笔试时,也遇到过这个问题.

关于LRU算法

一,LRU 原理 LRU(Least Recently Used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是"如果数据最近被访问过,那么将来被访问的几率也更高". 实现 最常见的实现是使用一个链表保存缓存数据,详细算法实现如下: 1. 新数据插入到链表头部: 2. 每当缓存命中(即缓存数据被访问),则将数据移到链表头部: 3. 当链表满的时候,将链表尾部的数据丢弃. 分析 [命中率] 当存在热点数据时,LRU的效率很好,但偶发性的.周期性的批量操作会导致LRU

使用 LinkedHashMap 实现 LRU 算法

LinkedHashMap 源码分析 public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> 上面是 LinkedHashMap 的继承结构.然后看下构造方法: private transient Entry<K,V> header;//内部链表的头 private final boolean accessOrder;//是否按照访问的顺序排序,默认是 false pu

Redis近似LRU算法优化

公有云Redis服务:https://www.aliyun.com/product/kvstore?spm=5176.8142029.388261.37.59zzzj 背景 在前一篇文章<Redis作为LRU Cache的实现>中,我们看到了在Redis 2.8.19中LRU算法的具体实现,Redis使用了24 bit的lru时间戳来模拟一个近似的LRU算法,节省了实现一个严格LRU算法所需要的大量内存空间. 但是,上篇文章我们也挖了一个坑,说过现有的近似算法模拟效果还有待提高,今天这篇文章就