最简单的LRU算法实现，线程安全的

liangwj72

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

最近访客更多访客>>

greedcoder

weiwan5675

qqluobairan

QING____

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

2007-09 ( 2)
更多存档...

博客分类：

工具

算法多线程 Java Cache Apache

LRU算法用途之广就不说了，凡是要用cache的地方都可以见到它的身影。特别是线程多，并发高，数据量大的环境下。

jdk1.5真好，在LinkedHashMap.java的源码中直接有这样的字样、“This kind of map is well-suited to building LRU caches.......The removeEldestEntry(Map.Entry) method may be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map.” 就是说自己写一下removeEldestEntry就搞定了。难为我当年自己写了一个。

以下是代码，我增加的是线程安全的代码

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

注意，只有get和put是线程安全的。

本来这贴是想放到入门论坛的，不过想了一下，要用LRU算法的，知道ReentrantLock的人好像也不能算新手了。

分享到：

Spring + JMX 入门

2007-09-14 16:51
浏览 7203
评论(5)
论坛回复 / 浏览 (5 / 14356)
查看更多

5 楼 liangwj72 2007-09-14

dengyin2000 写道

你可以用jdk5的read write lock。 get操作是可以不用block get的线程的。

Lock的使用请看：http://www.javalobby.org/java/forums/t45090.html

不用ReadWriteLock是因为：LRU算法原理中，get操作一定是有写的操作的，否则没办法找到最近最少用过的节点，所以也没办法用ReadWriteLock。这也是我为什么在get和put用同一个锁的原因。

4 楼 liangwj72 2007-09-14

liquidthinker 写道

apache commons的集合包里面有lru map的实现，之前做过一个objects cache，就是用的它，如果是jdk1.4环境，可以用这个

不用commons-collections中LRUMap的原因是：当时我看过里面的源码，和自己写的比较过，也和jdk1.5的比较过，发现还是jdk1.5中的实现方法效率高。

我看来的LRUMap是commons-collections-3.1中的。

BTW:当时自己写LRU算法时，完以后才发现commons collections中已经有了，也是挺郁闷的。

3 楼 dengyin2000 2007-09-14

很简单随手写写。 
 
 
<div class='code_title'>java 代码</div>
<div class='dp-highlighter'>
<div class='bar'> </div>
<ol class='dp-j' start='1'>
 <li class='alt'> import java.util.LinkedHashMap; </li>
 <li class=''>import java.util.concurrent.locks.Lock; </li>
 <li class='alt'>import java.util.concurrent.locks.ReadWriteLock; </li>
 <li class=''>import java.util.concurrent.locks.ReentrantReadWriteLock; </li>
 <li class='alt'>import java.util.concurrent.locks.ReentrantReadWriteLock.ReadLock; </li>
 <li class=''>import java.util.concurrent.locks.ReentrantReadWriteLock.WriteLock; </li>
 <li class='alt'> </li>
 <li class=''> public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> </li>
 <li class='alt'> { </li>
 <li class=''> private final int maxCapacity; </li>
 <li class='alt'> private static final float DEFAULT_LOAD_FACTOR = 0.75f; </li>
 <li class=''> private ReadWriteLock globalLock ; </li>
 <li class='alt'> private Lock readLock; </li>
 <li class=''> private Lock writeLock; </li>
 <li class='alt'> </li>
 <li class=''> public LRULinkedHashMap(int maxCapacity) </li>
 <li class='alt'> { </li>
 <li class=''> super(maxCapacity, DEFAULT_LOAD_FACTOR, true); </li>
 <li class='alt'> this.maxCapacity = maxCapacity; </li>
 <li class=''> globalLock = new ReentrantReadWriteLock(); </li>
 <li class='alt'> readLock = globalLock.readLock(); </li>
 <li class=''> writeLock = globalLock.writeLock(); </li>
 <li class='alt'> } </li>
 <li class=''> </li>
 <li class='alt'> @Override </li>
 <li class=''> protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) </li>
 <li class='alt'> { </li>
 <li class=''> return size() > maxCapacity; </li>
 <li class='alt'> } </li>
 <li class=''> </li>
 <li class='alt'> @Override </li>
 <li class=''> public V get(Object key) </li>
 <li class='alt'> { </li>
 <li class=''> readLock.lock(); </li>
 <li class='alt'> try { </li>
 <li class=''> return super.get(key); </li>
 <li class='alt'> } </li>
 <li class=''> finally { </li>
 <li class='alt'> readLock.unlock(); </li>
 <li class=''> } </li>
 <li class='alt'> } </li>
 <li class=''> </li>
 <li class='alt'> @Override </li>
 <li class=''> public V put(K key, V value) </li>
 <li class='alt'> { </li>
 <li class=''> writeLock.lock(); </li>
 <li class='alt'> try { </li>
 <li class=''> return super.put(key, value); </li>
 <li class='alt'> } </li>
 <li class=''> finally { </li>
 <li class='alt'> writeLock.unlock(); </li>
 <li class=''> } </li>
 <li class='alt'> } </li>
 <li class=''> } </li>
</ol>
</div>

2 楼 dengyin2000 2007-09-14

你可以用jdk5的read write lock。 get操作是可以不用block get的线程的。

Lock的使用请看：http://www.javalobby.org/java/forums/t45090.html

1 楼 liquidthinker 2007-09-14

apache commons的集合包里面有lru map的实现，之前做过一个objects cache，就是用的它，如果是jdk1.4环境，可以用这个

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论