2007-09-14

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

关键字: 算法
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的人好像也不能算新手了。
评论
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用同一个锁的原因。
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中已经有了，也是挺郁闷的。
dengyin2000 2007-09-14
很简单  随手写写。


java 代码
 
  1.  import java.util.LinkedHashMap;  
  2. import java.util.concurrent.locks.Lock;  
  3. import java.util.concurrent.locks.ReadWriteLock;  
  4. import java.util.concurrent.locks.ReentrantReadWriteLock;  
  5. import java.util.concurrent.locks.ReentrantReadWriteLock.ReadLock;  
  6. import java.util.concurrent.locks.ReentrantReadWriteLock.WriteLock;  
  7.      
  8.  public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V>    
  9.  {    
  10.      private final int maxCapacity;    
  11.      private static final float DEFAULT_LOAD_FACTOR = 0.75f;    
  12.      private ReadWriteLock  globalLock ;  
  13.      private Lock readLock;  
  14.      private Lock writeLock;  
  15.      
  16.      public LRULinkedHashMap(int maxCapacity)    
  17.      {    
  18.          super(maxCapacity, DEFAULT_LOAD_FACTOR, true);    
  19.          this.maxCapacity = maxCapacity;    
  20.          globalLock  = new ReentrantReadWriteLock();  
  21.          readLock = globalLock.readLock();  
  22.          writeLock = globalLock.writeLock();  
  23.      }    
  24.      
  25.      @Override    
  26.      protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest)    
  27.      {    
  28.          return size() > maxCapacity;    
  29.      }    
  30.      
  31.      @Override    
  32.      public V get(Object key)    
  33.      {    
  34.          readLock.lock();  
  35.          try {    
  36.              return super.get(key);    
  37.          }    
  38.          finally {    
  39.              readLock.unlock();    
  40.          }    
  41.      }    
  42.      
  43.      @Override    
  44.      public V put(K key, V value)    
  45.      {    
  46.          writeLock.lock();  
  47.          try {    
  48.              return super.put(key, value);    
  49.          }    
  50.          finally {    
  51.              writeLock.unlock();    
  52.          }    
  53.      }    
  54.  }    
dengyin2000 2007-09-14
你可以用jdk5的read write lock。 get操作是可以不用block get的线程的。

Lock的使用请看：http://www.javalobby.org/java/forums/t45090.html
liquidthinker 2007-09-14
apache commons的集合包里面有lru map的实现，之前做过一个objects cache，就是用的它，如果是jdk1.4环境，可以用这个
发表评论

提醒: 该博客已发表在公共论坛，博客所有留言会成为论坛回贴，留言请注意遵守论坛发贴规则

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

liangwj72
搜索本博客
最近加入圈子
最新评论