HashMap の実装ってどうなってるの？

# HashMap の実装って
# どうなってるの？

@YujiSoftware

---

# 目次

- HashMap について
- HashMap の実装を理解しよう！
  - データ構造
  - 各メソッドの挙動
  - 効率良く使うためのコツ

https://yuji.software/hashmap/
]

---

# HashMap って何？

- Map インタフェースの**最もよく使われる実装** 
 ↑ Key から Value を取得するためのもの
- 特徴
 - **高速**
 - 理想的には、計算量が *O(1)*
 - Key は一意
 - 重複した Key を格納しようとすると、上書きになる
 - 順序の保証はない

---

# HashMap の実装を理解しよう！

---

# 説明に使用するコード

「プログラミング言語」と「リリース年」のペアを格納

```java
var map = new HashMap<String, Integer>();
map.put("Java", 1995); // 1個目のデータを格納
map.put("JavaScript", 1995); // 2個目のデータを格納
… 中略 …
System.out.println(map.get("Java")); // 取得して表示
map.put("C", 1972); // 13個目のデータを格納

for (var entry : map.entrySet()) {
  System.out.println(entry); // ループして取得
}
```

---

# HashMap の中身

- 主なフィールド変数を**4つ**持っている（詳細は次ページ）

```java
Node[] table;
int size;
float loadFactor;
int threshold;
```

---

# フィールド変数（テーブル）

```java
Node[] table;
```

- データを保持する配列
 - 配列の各要素のことを** Bin **と呼ぶ
- 容量（配列サイズ）は、コンストラクタの引数で指定できる
 - ただし、**2の乗数に切り上げる**（理由は後述）
 - デフォルトコンストラクタの場合、容量は **16**

<hr>
![table](img/entry_1.svg)
 
---

# フィールド変数（テーブル）

- それぞれの Bin は、 Node  または null を保持する
 -  Node  は、`key` / `value` / `hash` / `next` を保持する

<hr>

![table](img/entry_4.svg)

---

# フィールド変数（サイズ）

```java
int size;
```
- 現在、保持しているデータ数

---
# フィールド変数（負荷係数としきい値）

```java
float loadFactor;
```

- 負荷係数（テーブルを再構築する割合）
 - コンストラクタの引数で指定できる
 - デフォルトコンストラクタの場合、**0.75**

```java
int threshold = (int)(table.length * loadFactor);
```
- しきい値
 - データ数がこの値を超過したら再構築する（後述）

---

# データを追加

```java
map.put("Java", 1995)
```

1. **どの Bin に格納するか**決める
  1. `key.hashCode()`  で値を取得
  2. hash を計算
  3. 格納する Bin を決定
2. **すでに同一の key が格納済みか**判定する
  3. 格納済み → 値を上書き  
  3. 未格納 →  Node  を作成して格納

---

# どの Bin に格納するか

```java
// 1. key（今回は "Java"）の hashCode を取得
int x = key.hashCode();
//  ↑ 2301506

// 2. hash を計算
int hash = hash(x);
//  ↑ 2301537

// 3. 格納する Bin を決定
int i = indexFor(hash);
//  ↑ 14

```

---

# indexFor メソッドの内容

- どの Bin に格納するか決める（今回は 0〜15 のいずれか） 
 → `key.hashCode() % table.length` を求める？
 - でも、割り算（余りを求める計算）は遅い
- そこで、**テーブル容量を必ず2の乗数とする**
 - これなら、余りを求める **= 下位ビットを取得する**だけ
 - つまり、AND でマスクするだけ

```java
static int indexFor(int h, int length) {
  return h & (length-1);
}
```

---

# hash メソッドの内容

- オブジェクトによっては `hashCode()` の下位ビットがあまり変化しない実装になっていることがある
 - Float とか （例えば、1.0f と 2.0f で下位ビットが同じ）
- そこで、`hashCode()` の**上位ビットの値を下位ビットに XOR で集めた値**を hash とする
- ただし、**key が null の場合は 0 とする**

---

# hash メソッドの詳細

```java
static final int hash(Object key) {
  int h;
  return (key == null) ? 0 
               : (h = key.hashCode()) ^ (h >>> 16);
}
```

`"Java".hashCode()` （= 0x00231E42）の場合

<table class="bitmap">
 <tr>
 <td>h</td>
 <td class="cyan">0</td><td class="cyan">0</td><td class="cyan">0</td><td class="cyan">0</td>
 <td class="cyan">0</td><td class="cyan">0</td><td class="cyan">0</td><td class="cyan">0</td>
 <td class="cyan">0</td><td class="cyan">0</td><td class="cyan">1</td><td class="cyan">0</td>
 <td class="cyan">0</td><td class="cyan">0</td><td class="cyan">1</td><td class="cyan">1</td>
 <td>0</td><td>0</td><td>0</td><td>1</td>
 <td>1</td><td>1</td><td>1</td><td>0</td>
 <td>0</td><td>1</td><td>0</td><td>0</td>
 <td>0</td><td>0</td><td>1</td><td>0</td>
 </tr>
 <tr>
 <td>h >> 16</td>
 <td></td><td></td><td></td><td></td>
 <td></td><td></td><td></td><td></td>
 <td></td><td></td><td></td><td></td>
 <td></td><td></td><td></td><td></td>
 <td class="cyan">0</td><td class="cyan">0</td><td class="cyan">0</td><td class="cyan">0</td>
 <td class="cyan">0</td><td class="cyan">0</td><td class="cyan">0</td><td class="cyan">0</td>
 <td class="cyan">0</td><td class="cyan">0</td><td class="cyan">1</td><td class="cyan">0</td>
 <td class="cyan">0</td><td class="cyan">0</td><td class="cyan">1</td><td class="cyan">1</td>
 </tr>
 <tr style="border-top: 3px double #555;">
 <td>XOR</td>
 <td>0</td><td>0</td><td>0</td><td>0</td>
 <td>0</td><td>0</td><td>0</td><td>0</td>
 <td>0</td><td>0</td><td>1</td><td>0</td>
 <td>0</td><td>0</td><td>1</td><td>1</td>
 <td>0</td><td>0</td><td>0</td><td>1</td>
 <td>1</td><td>1</td><td>1</td><td>0</td>
 <td>0</td><td>1</td><td>1</td><td>0</td>
 <td class="pink">0</td><td class="pink">0</td><td class="pink">0</td><td class="pink">1</td>
 </tr>
 <tr>
 <td colspan="33" style="border: none; text-align: end; line-height: 2">この値を使う↑</td>
 </tr>
</table>

---

# データを格納

- 先程の計算により**1番目の Bin に格納する**
  - null なので、新しく Node を作って格納

![HashMap#put](img/entry_2.svg)

---

# もうひとつデータを追加

```java
map.put("Basic", 1964)
```

1. **どの Bin に格納するか**決める 
  1. `key.hashCode()`  で値を取得（= 63955982）
  1. hash を計算 （**= 63956929**）
  2. 格納する Bin を決定（**= 1**）
2. すでに同一の key が格納済み？
  3. 格納済み → 値を上書き  
  3. 未格納 →  Node  を作成して格納

---

# すでに1番目の Bin にデータがある

![HashMap#put](img/entry_2_1.svg)

同一の key が格納済み？ → hash が一致 かつ key が一致しているかどうか

```java
hash == node.hash && key.equals(node.key)
```

---
# 格納されていないので、 Node  を追加

- 新しく Node  を作成して、1番目の Bin に格納
  - すでに登録されている Node  の **next に格納**

<hr>
![HashMap#put](img/entry_3.svg)

---

# さらにデータを追加

```java
map.put("Go", 2011);        // 3個目のデータ
map.put("C#", 2002);        // 4個目のデータ
map.put("Smalltalk", 1980); // 5個目のデータ
map.put("Kotlin", 2011);    // 6個目のデータ
map.put("Python", 1991);    // 7個目のデータ
map.put("Ruby", 1995);      // 8個目のデータ
map.put("PHP", 1995);       // 9個目のデータ
map.put("Rust", 2013);      // 10個目のデータ
map.put("Fortran", 1956);   // 11個目のデータ
map.put("Perl", 1987);      // 12個目のデータ
```

---

# データを取得する

```java
map.get("Java")
```

1. どの Bin に格納されているか
  1. `key.hashCode()` で値を取得（= 2301506）
  2. hash を計算（**= 2301537**）
  3. 格納する Bin を決定（**= 1**）
2. **すでに同一の key が格納済み？**
  3. 格納済み → その値を返す
  3. 未格納 → null を返す

---

#  key に紐づく値を取得

- 1番目の Bin を起点に Node をたどる
  - **hash が一致** かつ **key が一致**する → **その value を返す**

<hr>
![HashMap#get](img/entry_3_1.svg)

---

# ℹ️ 効率良く使うためのヒント

- Bin 内のデータが少数（理想的には1個）だと効率が良い
 - 比較回数が少なくて済むから
- そのために、**hashCode の値が分散しているのがよい**

自作のオブジェクトをキーにする場合、 
**hashCode メソッドの実装に注意しましょう！**
 - できるだけ値が重複しないようにする
 - 周期性がないようにする（良くない例：必ず偶数になる）

---
## ⚠️ 良くない実装

- ひとつの Bin にすべてのデータが集中する

```java
public int hashCode() {
  return 1;
}
```

## 💡 簡単で良い実装

- `Objects.hash(Object... values)` を使用する
- [Lombok](https://projectlombok.org/) を使用する
- Record クラスを使用する（Java16 以降）

---

# さらにデータを追加

```java
map.put("C", 1972); // 13個目のデータ
```

* `threshold (=12)` を超えた   
→ **テーブルの再構築を行う**  
　→ これにより、ひとつの Bin に含まれるデータが減る

---

# 再構築（rehash）処理

1. **2倍**の容量のテーブル（Node配列）を作成
2. インデックスを再計算し、新テーブルに Node を格納
 * Bin が2分割される

<hr>

![HashMap の rehash](img/entry_rehash.svg)

---

# ℹ️ 効率良く使うためのヒント

- 13個以上格納するなら、**容量を指定する**
 - rehash が減らせるため
 - 指定する値は、負荷係数（loadFactor）の考慮が必要

```java
// 最低32個のデータを格納する場合、
// 32 * (1 / 0.75) = 43（切り上げ）を指定する
Map<String, Integer> map = new HashMap<>(43);

// Java19以降なら、格納個数を指定するメソッドが使える
Map<String, Integer> map = HashMap.newHashMap(32);
```

---

# ループして取り出し

```java
for (var e : map.entrySet()) 
```

- 各 Bin からノードを順に取り出す
  - Rehash などによって、順序は変わる

![HashMap の rehash](img/entry_loop.svg)

---

## ℹ️ なぜ順序を保証しないのか

- 順序の管理にコストがかかるから
  - HashMap の特徴のひとつである**速さが犠牲になる**

- 順序が必要なら、クラスを使い分ける
 - アクセス順序や挿入順序で取り出したいなら **LinkedHashMap** を使う
 - キーのソート順で取り出したいなら **TreeMap**を使う

---

# まとめ

- HashMap は、テーブル（配列）にデータを格納している
- 高速にデータを取得できる
 - そのためには、hashCode() メソッドの実装が大事！
- 最適な初期容量を指定すると、効率が良い