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); } }
実行結果はこちら。
- 0,1,2,3,4を追加。
- 1,2,3にアクセスすることで後ろへ。
- 5,6,7を追加。0,2,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}