JavaのMapについて

概要

JavaのCollections Framework は多くの便利なMap実装を提供しています。

ここではそれらについて簡単に紹介していきます。

Collections Framework におけるMapの全容

Collections Frameworkで提供しているMap系のインターフェース、抽象クラス、具象クラスの全容は以下のようです。

インターフェースは下記の5つです。

インターフェース名	どんな機能？
Map	1対1に紐づくkey,valueを持つ
SortedMap	keyの順番でソートしているMap
NavigableMap	keyによる検索結果で最も近いものを返せるMap
ConcurrentMap	putIfAbsent, remove, replace について並行処理を安全にできるMap
ConcurrentNavigableMap	ConcurrentMapにNavigableMapの機能がついたMap

抽象クラスには AbstractMap があり、これはTemplate Method的な役割を果たしています。

具象クラスを(勝手に)分類するとこんな感じでしょうか。

• keyにhashCodeを使う系
  • HashMap
  • LinkedHashMap
• 順序がある系
  • TreeMap
• 並行処理系
  • ConcurrentHashMap
  • ConcurrentSkipListMap
• 特殊系
  • EnumMap
  • WeakHashMap
  • IdentityHashMap

keyにhashCodeを使う系

MapのキーにはhashCodeを使うので、keyに値するクラスのhashCodeを適切に実装していれば、O(1)でデータ検索できます。

HashMap

個人的には一番よく見るMapの実装です。
keyにもvalueにもnullを入れることができるようです。

jshell> HashMap<String, String> a = new HashMap<String, String>();
a ==> {}

jshell> a.put(null, null);
$2 ==> null

jshell> a.get(null);
$3 ==> null

jshell> a.size();

LinkedHashMap

こちらもkeyにもvalueにもnullを入れることができます。

このMapは投入された順序を記憶できます。
ただし、すでにMapに登録されているものの順序を上書きすることはできません。

jshell> LinkedHashMap<String, String> b = new LinkedHashMap<String, String>();
b ==> {}

jshell> b.put("1", "one");
$6 ==> null

jshell> b.put("2", "two");
$7 ==> null

jshell> for (Map.Entry<String, String> entry: b.entrySet()){
   ...>     System.out.println(entry.getKey());
   ...>     System.out.println(entry.getValue());
   ...> }
1
one
2
two

jshell> b.put("1", "one");
$9 ==> "one"

jshell> for (Map.Entry<String, String> entry: b.entrySet()){
   ...>     System.out.println(entry.getKey());
   ...>     System.out.println(entry.getValue());
   ...> }
1
one
2
two

順序がある系

TreeMap

こちらのMapは、containsKey、get、put、remove に O(log(n)) の時間がかかります。

指定したkeyの値以下で一番keyに近いentryを返す、みたいなことが容易にできます。
競プロで役立ちそうですね。

jshell> c.put(1, "one");
$19 ==> null

jshell> c.put(100, "one hundred");
$20 ==> null

jshell> c.put(200, "two hundred");
$21 ==> null

jshell> c.floorEntry(150).getValue();
$22 ==> "one hundred"

TreeMapはnullをkeyにできません。(valueにnullを入れることはできます。)

jshell> c.put(null, "one");
|  例外java.lang.NullPointerException
|        at Objects.requireNonNull (Objects.java:208)
|        at TreeMap.put (TreeMap.java:809)
|        at TreeMap.put (TreeMap.java:534)
|        at (#23:1)

jshell> c.put(300, null);
$24 ==> null

並行処理系

computeIfAbsent や computeIfPresent で原子性のある処理ができます。

ConcurrentHashMap

以下のような、複数スレッドから同時に computeIfPresent でvalueの状態を変えにくるような処理でも原子性のある処理を行います。

import java.util.concurrent.ConcurrentHashMap;

public class Main {
    //    public static HashMap<String, Integer> map = new HashMap<>();
    public static ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

    static {
        map.put("key", 1);
    }

    public static void main(String[] args) throws InterruptedException {
        Thread thread1 = new Thread(new MyTask());
        thread1.start();
        Thread thread2 = new Thread(new MyTask());
        thread2.start();

        thread1.join();
        thread2.join();

        System.out.println(map.get("key")); //ConcurrentHashMapを利用したら常に 201。HashMap だと不定。

    }

}

class MyTask implements Runnable {
    public void run() {
        for (int i = 0; i < 100; i++) {
            Main.map.computeIfPresent("key", (key, value) -> value + 1);
        }
    }
}

keyにもvalueにもnullは受け付けないようです。

jshell> d.put("a", null);
|  例外java.lang.NullPointerException
|        at ConcurrentHashMap.putVal (ConcurrentHashMap.java:1011)
|        at ConcurrentHashMap.put (ConcurrentHashMap.java:1006)
|        at (#27:1)

jshell> d.put(null,"a");
|  例外java.lang.NullPointerException
|        at ConcurrentHashMap.putVal (ConcurrentHashMap.java:1011)
|        at ConcurrentHashMap.put (ConcurrentHashMap.java:1006)
|        at (#28:1)

ConcurrentSkipListMap

スキップリストなるアルゴリズムで実装されているみたいです。

複数スレッドからMapへの同時アクセスがある場合でも、登録、更新、削除が安全に行えます。

keyにもvalueにもnullは受け付けないようです。

特殊系

EnumMap

keyがEnumに限られるMap。

keyをnullにすることはできないが、valueをnullにすることはできます。

jshell> public enum DayOfWeek {
   ...>     MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY
   ...> }
|  次を作成しました: 列挙型 DayOfWeek

jshell> EnumMap<DayOfWeek, String> e = new EnumMap<>(DayOfWeek.class);
e ==> {}

jshell> e.put(null, null);
|  例外java.lang.NullPointerException: Cannot invoke "Object.getClass()" because "key" is null
|        at EnumMap.typeCheck (EnumMap.java:736)
|        at EnumMap.put (EnumMap.java:264)
|        at (#33:1)

jshell> e.put(DayOfWeek.MONDAY, null);
$34 ==> null

WeakHashMap

keyの参照に紐づくオブジェクトがkey以外から参照されなくなった上でGCが起きるとMapから消える、という性質を持ったMapです。
このページの説明が分かりやすいと思います。

どこで使うんだ？？と思ってspringを調べてみると、AbstractClassGenerator なるクラスで使われていました。

	private static volatile Map<ClassLoader, ClassLoaderData> CACHE = new WeakHashMap<ClassLoader, ClassLoaderData>();

変数名から察するに何らかのキャッシュなんでしょう。。深追いするのはやめました(できなかった)。

WeakHashMapはkeyにもvalueにも　null　を入れることができます。

jshell> WeakHashMap<Integer, String> g = new WeakHashMap<>();
g ==> {}

jshell> g.put(null, "a");
$2 ==> null

jshell> g.put(1, null);
$3 ==> null

jshell> g.size();
$4 ==> 2

IdentityHashMap

keyの一致を判定する方法が他と異なるMapです。
他のMapが同値か否か(k1.equals(k2))で判断しているところを、IdentityHashMapは同一か否か(k1 == k2)で判断します。

jshell> HashMap<Integer, String> hash = new HashMap<>();
hash ==> {}

jshell> IdentityHashMap<Integer, String> identity = new IdentityHashMap<>();
identity ==> {}

jshell> hash.put(1, "one");
$29 ==> null

jshell> hash.get(new Integer(1));
|  警告:
|  java.lang.IntegerのInteger(int)は推奨されておらず、削除用にマークされています
|  hash.get(new Integer(1));
|           ^------------^
$30 ==> "one"

jshell> identity.put(1, "one");
$31 ==> null

jshell> identity.get(new Integer(1));
|  警告:
|  java.lang.IntegerのInteger(int)は推奨されておらず、削除用にマークされています
|  identity.get(new Integer(1));
|               ^------------^
$32 ==> null

IdentityHashMapはkeyにもvalueにもnullを入れることができます。

おわりに

Collections Framework内のMapをざっと見てみました。
各Mapが具体的にどんな場面で使われているかを掘っていけば面白そうですね。