はじめに
Javaを学んでいると、必ず出てくる HashMap。
でも、こう思いませんか？
- 「使い方はわかるけど、内部で何してるの？」
- 「
putやgetの仕組みってどうなってるの？」 - 「なぜ高速なの？」
この記事では、そんな疑問を図解＆例付きでスッキリ解消！
Javaの HashMap の中身を、基礎からしっかり解説します。
HashMapは何のためにあるの？
- 「キー」と「値」をペアで管理するデータ構造
- たとえば「名前 → 年齢」や「商品名 → 在庫数」などを保存するのに使います
- 最大の特徴は、高速な検索（平均 O(1)）
HashMapの内部構造（図解）
構成要素：
| 要素 | 説明 |
|---|---|
table（配列） | バケットの配列（Node[]） |
| バケット | 同じインデックスにあるデータの入れ物 |
| ノード | キー、値、ハッシュ、nextを持つ |
next | バケット内でノードをつなぐ |
| TreeBin | ノードが多いと赤黒木に変化 |
データ追加（put）の流れ
|
1 2 |
map.put("apple", 100); |
この1行で内部ではこんなことが起きています！
- ハッシュ値を計算（
"apple".hashCode()） - 補正処理で分散を改善（
h ^ (h >>> 16)） - インデックスを計算（
hash & (table.length - 1)） - そのインデックスのバケットを見る
- 空いていればそのままノードを入れる
- 他のノードがあれば「衝突処理」へ
- 衝突があれば：
equals()でキー比較し、上書き or 新規追加 - バケットが混みすぎたら：リスト → 赤黒木（TreeBin）に変換
- 容量オーバーなら：table を 2倍に拡張（再ハッシュ）
データ取得（get）の流れ
|
1 2 |
int price = map.get("apple"); |
- ハッシュ値を計算して
- インデックスを求めて
- 該当バケットのノードを順に見て
equals()でキーが一致すれば値を返す！
ポイント：検索も高速！O(1)で取得できることが多い
衝突とは？なぜ起きる？
「違うキーが同じインデックスに入る」＝これが衝突（コリジョン）
たとえば：
|
1 2 |
map.put("orange", 300); // "apple"と同じバケットに入るかも？ |
→ その場合、next を使って「つなげる（チェーン）」方式になります
ノードが多すぎると…木に変身！？
- バケット内のノード数が8以上（Java 8以降）になると
- リンクリスト → 赤黒木（TreeBin） に変換！
- 探索が O(n) → O(log n) に高速化！
これが HashMap の 「賢い設計」ポイントです。
配列が足りなくなったら？
- HashMapは自動で容量を増やします！
- 要素数が一定（初期容量 × 負荷率 0.75）を超えると
resize()という処理が走り、tableのサイズが 2倍 になります
nullキーやnull値は使える？
はい、使えます！
- キーに
null→ OK（ただし1個だけ） - 値に
null→ OK（何個でも）
|
1 2 3 |
map.put(null, 999); map.put("x", null); |
実際のNode構造は？
|
1 2 3 4 5 6 7 |
static class Node<K,V> { final int hash; final K key; V value; Node<K,V> next; } |
この構造が HashMap の「中身そのもの」！
よくある質問Q&A
Q. なぜハッシュ値に補正をかけるの？
→ 偏りを防ぐため。hashCode() だけだと分布が悪くなるケースがあるから！
Q. HashMap の速度が遅くなるときはある？
→ 衝突が多くてチェーンが長くなると、O(n)に近づくことがある。初期サイズを大きめにしておくと安心！
Q. Hashtable との違いは？
→ HashMap は 非同期（高速）。Hashtable は 同期処理あり（遅いが安全）。
初心者がまず知っておくべきことまとめ
HashMapは内部に「配列＋ノード＋チェーン」でできている- キーの
hashCode()でバケットを決定 - 衝突があればチェーンでつなぐ
- ノードが多ければ木に変換
- 再ハッシュや補正など、細かい工夫がいっぱい！
自分でも動かして学ぼう！
|
1 2 3 4 5 |
Map<String, Integer> map = new HashMap<>(); map.put("apple", 100); map.put("banana", 200); System.out.println(map.get("apple")); // 100 |
実際にコードを書いて、内部で何が起きているかイメージしながら学ぶのが一番！
本気で学びたい人へ
HashMapのような内部構造の理解はJava中級者への第一歩！
- 自分で調べて学びたいなら → 絶対にJavaプログラマーになりたい人へ。
- 独学が不安・コードレビューしてほしい人は → サイゼントアカデミー
コメント