LruLinkedHashMap

LRU(Least Recently Used)アルゴリズムを持つ Map を作成する場合、LinkedHashMap を使うとラクチンです。

LRU アルゴリズムの実装方法

removeEldestEntry(java.util.Map.Entry) メソッドをオーバーライドするだけで、LRU アルゴリズムを持った Map になります。put 時にこのメソッドがよばれ、true を返すと最も長時間アクセスされていない要素が削除されます。ということで、

return size() > maxEntries;

のように戻り値を設定するだけで、最大サイズが maxEntries の LRUアルゴリズムを持った Map となります。

get時の振る舞い

内部的には、二重のリンクリストを保持していて、そのリストを常に、最後にアクセスのあったエントリを先頭にするように保守しています。たとえば、既存のある要素が get の対象になった場合、その要素がリンクリストの先頭に移動します。

この実装は同期化されません

スレッドセーフでないので、気をつけましょう。Collections.synchronizedMap を使うのもありですし、ReentrantReadWriteLock 等を使って高速化を図るのもありかもしれません。

ソース例

ソース

package jp.objectfanatics.commons.util;

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;

/**
 * LRU(Least Recently Used)アルゴリズムを持つ {@link Map} です。
 * 
 * @param <K>
 *            the type of keys maintained by this map
 * @param <V>
 *            the type of mapped values
 * @author beyondseeker
 * @version $Id: LruLinkedHashMap.java 60 2008-05-19 15:55:05Z beyondseeker $
 */
@SuppressWarnings("unchecked")
public class LruLinkedHashMap<K, V> extends LinkedHashMap<K, V> {
	
	/**
	 * Serial Version UID
	 */
	private static final long serialVersionUID = 1L;
	
	/**
	 * 最大エントリ数
	 */
	protected final int maxEntries;
	
	/**
	 * エントリの退避を行わないように初期化します。
	 */
	public LruLinkedHashMap() {
		this.maxEntries = Integer.MAX_VALUE;
	}
	
	/**
	 * コンストラクタ
	 * 
	 * @param maxEntries
	 *            最大エントリ数。最大エントリ数が Integer.MAX_VALUE の場合はエントリの退避を行いません。
	 */
	public LruLinkedHashMap(int maxEntries) {
		this.maxEntries = maxEntries;
	}
	
	/**
	 * コンストラクタ
	 * 
	 * @param maxEntries
	 *            最大エントリ数。最大エントリ数が Integer.MAX_VALUE の場合はエントリの退避を行いません。
	 * @param initialCapacity
	 * @param loadFactor
	 * @param accessOrder
	 */
	public LruLinkedHashMap(int maxEntries, int initialCapacity, float loadFactor, boolean accessOrder) {
		super(initialCapacity, loadFactor, accessOrder);
		this.maxEntries = maxEntries;
	}
	
	/**
	 * コンストラクタ
	 * 
	 * @param maxEntries
	 *            最大エントリ数。最大エントリ数が Integer.MAX_VALUE の場合はエントリの退避を行いません。
	 * @param initialCapacity
	 * @param loadFactor
	 */
	public LruLinkedHashMap(int maxEntries, int initialCapacity, float loadFactor) {
		super(initialCapacity, loadFactor);
		this.maxEntries = maxEntries;
	}
	
	/**
	 * コンストラクタ
	 * 
	 * @param maxEntries
	 *            最大エントリ数。最大エントリ数が Integer.MAX_VALUE の場合はエントリの退避を行いません。
	 * @param m
	 *            the map whose mappings are to be placed in this map
	 */
	public LruLinkedHashMap(int maxEntries, Map<? extends K, ? extends V> m) {
		super(m);
		this.maxEntries = maxEntries;
	}
	
	/**
	 * 現在のエントリ数が最大エントリ数を超えている場合には true を返します。
	 */
	@Override
	@SuppressWarnings("unchecked")
	protected boolean removeEldestEntry(Entry eldest) {
		return size() > maxEntries;
	}
	
}