JavaのMapについて

# 概要

[JavaのCollections Framework](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/doc-files/coll-reference.html) は多くの便利なMap実装を提供しています。

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

## Collections Framework におけるMapの全容

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

```plantuml
interface Map {
}
abstract class AbstractMap implements Map {
}
interface SortedMap extends Map {
}

interface NavigableMap extends SortedMap {
}

interface ConcurrentMap extends Map {
}
interface ConcurrentNavigableMap extends ConcurrentMap, NavigableMap {
}

class HashMap extends AbstractMap implements Map {
}

class TreeMap extends AbstractMap implements Map ,NavigableMap, SortedMap {
}

class LinkedHashMap extends HashMap implements Map {
}

class ConcurrentHashMap extends AbstractMap implements ConcurrentMap {
}
class ConcurrentSkipListMap extends AbstractMap implements ConcurrentNavigableMap {
}
class WeakHashMap extends AbstractMap implements Map{
}
class IdentityHashMap extends AbstractMap implements Map{
}
class EnumMap extends AbstractMap {
}
```

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

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


抽象クラスには `AbstractMap` があり、これは[Template Method](https://ja.wikipedia.org/wiki/Template_Method_%E3%83%91%E3%82%BF%E3%83%BC%E3%83%B3)的な役割を果たしています。
 
具象クラスを(勝手に)分類するとこんな感じでしょうか。

- keyにhashCodeを使う系
    - [HashMap](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/HashMap.html)
    - [LinkedHashMap](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/LinkedHashMap.html)
- 順序がある系
    - [TreeMap](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/TreeMap.html)
- 並行処理系
    - [ConcurrentHashMap](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/concurrent/ConcurrentHashMap.html)
    - [ConcurrentSkipListMap](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/concurrent/ConcurrentSkipListMap.html)
- 特殊系
    - [EnumMap](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/EnumMap.html)
    - [WeakHashMap](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/WeakHashMap.html)
    - [IdentityHashMap](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/IdentityHashMap.html)

## keyにhashCodeを使う系

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

### HashMap

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

```java
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に登録されているものの順序を上書きすることはできません。

```java
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を返す、みたいなことが容易にできます。
競プロで役立ちそうですね。

```java
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の状態を変えにくるような処理でも原子性のある処理を行います。

```java
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

[スキップリスト](ttps://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%AD%E3%83%83%E3%83%97%E3%83%AA%E3%82%B9%E3%83%88)なるアルゴリズムで実装されているみたいです。

複数スレッドから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です。
[このページ](http://www.ne.jp/asahi/hishidama/home/tech/java/weak.html)の説明が分かりやすいと思います。

どこで使うんだ？？と思って[spring](https://github.com/spring-projects/spring-framework)を調べてみると、[AbstractClassGenerator](https://github.com/spring-projects/spring-framework/blob/025eaf688f1c1269cd51139b7b1beadf2c103f35/spring-core/src/main/java/org/springframework/cglib/core/AbstractClassGenerator.java#L41) なるクラスで使われていました。

```java
	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が具体的にどんな場面で使われているかを掘っていけば面白そうですね。