2010年07月21日

LRUのMap

表題の通り、LRU (Least Recently Used)アルゴリズムを持つMapが欲しかった。

自作する前に、既にありそうなので探してみると、

org.apache.commons.collections.LRUMap

があったので、早速使ってみようと思ったが、commons-collections-3.2.1では、@deprecatedで非推奨になっていた。

どうも、同期処理が不安定っぽい。

仕方ないので、別の方法を模索してみたところ、LinkedHashMapを利用して、スマートにLRUアルゴリズムを実現する方法があった。

方法とは、LinkedHashMapを継承して、removeEldestEntryをオーバーライドするだけだ。

デフォルト:

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
  return false;
}

オーバーライド例:

private static final int MAX_ENTRIES = 3;

protected boolean removeEldestEntry(Map.Entry eldest) {
  return size() > MAX_ENTRIES;
}

このメソッドはマップが一番古いエントリを削除する場合、true を返すようだ。
だから、削除したい条件を判定してやるだけで良いみたい。

へぇー。

テストしてみたところ期待通りの動作をした。

LRUMap<String, String> map = new LRUMap<String, String>(3);

map.put("test1","value1");
map.put("test2","value2");
map.get("test1");
map.put("test3","value3");
map.put("test4","value4");
map.get("test1");
map.put("test5","value5");

System.out.println(map);

結果:{test4=value4, test1=value1, test5=value5}

でも、LinkedHashMap自身は同期化されないので何らかの対策は必要かも。

まあメソッドにsynchronized指定をするか、

Map<String, String> cacheMap = Collections.synchronizedMap(new LRUMap<String, String>(3));

のように同期化されたマップを作ればいいだろう。

今回は、LinkedHashMapの勉強になりました。

以上。

posted by hana at 10:20| Comment(0) | TrackBack(0) | JAVA | このブログの読者になる | 更新情報をチェックする
×

この広告は1年以上新しい記事の投稿がないブログに表示されております。