庄周梦蝶

生活、程序、未来
   :: 首页 ::  ::  :: 聚合  :: 管理

简单LRU算法实现缓存-update2

Posted on 2007-09-29 17:49 dennis 阅读(5518) 评论(5)  编辑  收藏 所属分类: java数据结构与算法my open-source
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());
        }

    }
}




评论

# re: 简单LRU算法实现缓存-update1  回复  更多评论   

2007-09-30 10:04 by sitinspring
Mark.

# re: 简单LRU算法实现缓存-update1  回复  更多评论   

2007-10-13 03:07 by 小飞飞
这个怎么用了?

# re: 简单LRU算法实现缓存-update1  回复  更多评论   

2007-10-13 16:43 by dennis
@小飞飞
怎么用?老大,缓存怎么用

# re: 简单LRU算法实现缓存-update1  回复  更多评论   

2008-01-09 13:57 by zhangwei
很好,我正想找一个这样的程序那,谢谢了。

# re: 简单LRU算法实现缓存-update1[未登录]  回复  更多评论   

2008-01-14 09:18 by bruce
说一下咱用呀?楼主

只有注册用户登录后才能发表评论。


网站导航: