HashMap、TreeMap、LinkedHashMapの違いとLRU

BY | コメントをどうぞ

HashMap、TreeMap、LinkedHashMapについて。

  • HashMapはその名前の通り、キーからハッシュ値を算出して管理するため、順序は不定となる。
  • TreeMapはキーの自然順序付けによってソートされる。
  • LinkedHashMapは、HashMapとLinkedListの両方で管理するため、挿入された順番を保持する。

例えば、次のソースを実行する。

import java.util.*;

public class MapTest {
    public static void main(String[] args) {
        test(new HashMap());
        test(new TreeMap());
        test(new LinkedHashMap());
    }
    static void test(Map map) {
        System.out.println(map.getClass().toString());
        test(map, 1, 1);
        test(map, 40, 2);
        test(map, 70, 3);
        test(map, 100, 4);
        test(map, 3, 5);
        test(map, 2, 6);
        test(map, 8, 7);
        test(map, 6, 8);
        test(map, 9, 9);
        test(map, 5, 10);
    }
    static void test(Map map, int key, int value) {
        map.put(key, value);
        System.out.println(map);
    }
}
  • HashMapはバラバラに追加される。
  • TreeMapはキーでソートされた状態で追加される。
  • LinkedHashMapは追加された順番を保持される。
class java.util.HashMap
{1=1}
{1=1, 40=2}
{1=1, 70=3, 40=2}
{1=1, 100=4, 70=3, 40=2}
{1=1, 100=4, 70=3, 3=5, 40=2}
{1=1, 2=6, 100=4, 70=3, 3=5, 40=2}
{1=1, 2=6, 100=4, 70=3, 3=5, 8=7, 40=2}
{1=1, 2=6, 100=4, 70=3, 3=5, 6=8, 8=7, 40=2}
{1=1, 2=6, 100=4, 70=3, 3=5, 6=8, 8=7, 9=9, 40=2}
{1=1, 2=6, 100=4, 70=3, 3=5, 5=10, 6=8, 8=7, 9=9, 40=2}
class java.util.TreeMap
{1=1}
{1=1, 40=2}
{1=1, 40=2, 70=3}
{1=1, 40=2, 70=3, 100=4}
{1=1, 3=5, 40=2, 70=3, 100=4}
{1=1, 2=6, 3=5, 40=2, 70=3, 100=4}
{1=1, 2=6, 3=5, 8=7, 40=2, 70=3, 100=4}
{1=1, 2=6, 3=5, 6=8, 8=7, 40=2, 70=3, 100=4}
{1=1, 2=6, 3=5, 6=8, 8=7, 9=9, 40=2, 70=3, 100=4}
{1=1, 2=6, 3=5, 5=10, 6=8, 8=7, 9=9, 40=2, 70=3, 100=4}
class java.util.LinkedHashMap
{1=1}
{1=1, 40=2}
{1=1, 40=2, 70=3}
{1=1, 40=2, 70=3, 100=4}
{1=1, 40=2, 70=3, 100=4, 3=5}
{1=1, 40=2, 70=3, 100=4, 3=5, 2=6}
{1=1, 40=2, 70=3, 100=4, 3=5, 2=6, 8=7}
{1=1, 40=2, 70=3, 100=4, 3=5, 2=6, 8=7, 6=8}
{1=1, 40=2, 70=3, 100=4, 3=5, 2=6, 8=7, 6=8, 9=9}
{1=1, 40=2, 70=3, 100=4, 3=5, 2=6, 8=7, 6=8, 9=9, 5=10}

LinkedHashMapのremoveEldestEntry

LinkedHashMapでは、removeEldestEntry()を実装することで、マップが管理する最大数を制御することが出来る。以下のコードでは、最大数5を超えたエントリーは古いものから削除される。

import java.util.*;

class LinkedHashMap5 extends LinkedHashMap {
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > 5;
    }
}

public class MapTest {
    public static void main(String[] args) {
        test(new LinkedHashMap());
        test(new LinkedHashMap5());
    }
    static void test(Map map) {
        System.out.println(map.getClass().toString());
        test(map, 1, 1);
        test(map, 40, 2);
        test(map, 70, 3);
        test(map, 100, 4);
        test(map, 3, 5);
        test(map, 2, 6);
        test(map, 8, 7);
        test(map, 6, 8);
        test(map, 9, 9);
        test(map, 5, 10);
    }
    static void test(Map map, int key, int value) {
        map.put(key, value);
        System.out.println(map);
    }
}

LinkedHashMap5では、removeEldestEntryが実装されているため、最大でも5個しか保持せず、一番古いエントリーから削除されている。

class java.util.LinkedHashMap
{1=1}
{1=1, 40=2}
{1=1, 40=2, 70=3}
{1=1, 40=2, 70=3, 100=4}
{1=1, 40=2, 70=3, 100=4, 3=5}
{1=1, 40=2, 70=3, 100=4, 3=5, 2=6}
{1=1, 40=2, 70=3, 100=4, 3=5, 2=6, 8=7}
{1=1, 40=2, 70=3, 100=4, 3=5, 2=6, 8=7, 6=8}
{1=1, 40=2, 70=3, 100=4, 3=5, 2=6, 8=7, 6=8, 9=9}
{1=1, 40=2, 70=3, 100=4, 3=5, 2=6, 8=7, 6=8, 9=9, 5=10}
class LinkedHashMap5
{1=1}
{1=1, 40=2}
{1=1, 40=2, 70=3}
{1=1, 40=2, 70=3, 100=4}
{1=1, 40=2, 70=3, 100=4, 3=5}
{40=2, 70=3, 100=4, 3=5, 2=6}
{70=3, 100=4, 3=5, 2=6, 8=7}
{100=4, 3=5, 2=6, 8=7, 6=8}
{3=5, 2=6, 8=7, 6=8, 9=9}
{2=6, 8=7, 6=8, 9=9, 5=10}

LinkedHashMapのaccessOrder

コンストラクタLinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)にのみaccessOrderを指定できる。その他のコンストラクタではaccessOrder=false。
10件putして、反対からgetしてみる。

import java.util.*;

public class LinkedHashMapAO extends LinkedHashMap {
    public static void main(String[] args) {
        test(new LinkedHashMap(16, 0.75f, false));
        System.out.println("");
        test(new LinkedHashMap(16, 0.75f, true));
    }
    static void test(Map map) {
        for (int i=0; i<10; i++) {
            map.put(i, i);
        }
        for (int i=0; i<10; i++) {
            map.get(10-i-1);
            System.out.println(map);
        }
    }
}

実行結果はこちら。前半は並び順（登録順）が変わらないが、後半はget()する度に後ろに移動していく。

{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}
{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}
{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}
{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}
{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}
{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}
{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}
{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}
{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}
{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}

{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}
{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 9=9, 8=8}
{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 9=9, 8=8, 7=7}
{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 9=9, 8=8, 7=7, 6=6}
{0=0, 1=1, 2=2, 3=3, 4=4, 9=9, 8=8, 7=7, 6=6, 5=5}
{0=0, 1=1, 2=2, 3=3, 9=9, 8=8, 7=7, 6=6, 5=5, 4=4}
{0=0, 1=1, 2=2, 9=9, 8=8, 7=7, 6=6, 5=5, 4=4, 3=3}
{0=0, 1=1, 9=9, 8=8, 7=7, 6=6, 5=5, 4=4, 3=3, 2=2}
{0=0, 9=9, 8=8, 7=7, 6=6, 5=5, 4=4, 3=3, 2=2, 1=1}
{9=9, 8=8, 7=7, 6=6, 5=5, 4=4, 3=3, 2=2, 1=1, 0=0}

LinkedHashMapによるLRU

removeEldestEntryとaccessOrderを組み合わせると、LRU(Least Recently Used)キャッシュができる。

import java.util.*;

public class LinkedHashMapLRU5 extends LinkedHashMap {
    public LinkedHashMapLRU5() { super(); }
    public LinkedHashMapLRU5(int i, float f, boolean b) { super(i, f, b); }

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

    public static void main(String[] args) {
        test(new LinkedHashMapLRU5(16, 0.75f, true));
    }
    static void test(Map map) {
        for (int i=0; i<5; i++) {
            map.put(i, i);
        }
        System.out.println(map);
        map.get(1);
        map.get(3);
        System.out.println(map);
        map.put(5, 5);
        map.put(6, 6);
        map.put(7, 7);
        System.out.println(map);
        map.get(1);
        map.get(3);
        map.get(5);
        map.get(7);
        System.out.println(map);
    }
}

実行結果はこちら。

  1. 0,1,2,3,4を追加。
  2. 1,2,3にアクセスすることで後ろへ。
  3. 5,6,7を追加。0,2,4は消える。
  4. 1,3,5,7にアクセスすることで後ろへ。
{0=0, 1=1, 2=2, 3=3, 4=4}
{0=0, 2=2, 4=4, 1=1, 3=3}
{1=1, 3=3, 5=5, 6=6, 7=7}
{6=6, 1=1, 3=3, 5=5, 7=7}

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

次のHTML タグと属性が使えます: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>