0Pricing
Java Academy · レッスン

HashMap の仕組み

バケット、ハッシュ、衝突です。

「HashMap の仕組み」はCoddyKit上の無料Java Academyレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはJava Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Java Academyコースには全4レッスンが含まれています。

HashMapが保持するもの

HashMapはキーと値のペアを保持し、検索、挿入、削除を平均O(1)で実行できます。

内部では、tableと呼ばれる配列を保持しています。この配列の各スロットをbucketと呼びます。

  • キーによって、エントリが入るバケットが決まります。
  • キーを検索したときに返されるのが値です。
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> ages = new HashMap<>();
        ages.put("Alice", 30);
        ages.put("Bob", 25);
        System.out.println(ages.get("Alice"));
    }
}

キーのハッシュ化

put(key, value)を呼び出すと、マップはkey.hashCode()を呼び出してintを取得します。

HashMapはそのビット列を内部関数で拡散し、ハッシュコードの分布が偏っていてもバケット全体に分散されるようにします。

  • 最終的な値をhash & (table.length - 1)で縮小し、バケットのインデックスを求めます。
  • テーブルの長さは常に2の累乗なので、このマスクが機能します。
public class Main {
    public static void main(String[] args) {
        String key = "Alice";
        int h = key.hashCode();
        int spread = h ^ (h >>> 16);
        int index = spread & (16 - 1);
        System.out.println("hashCode: " + h);
        System.out.println("bucket index: " + index);
    }
}

バケットの動作

各バケットには複数のエントリを格納できます。2つのキーが同じバケットに割り当てられることを衝突と呼びます。

衝突は通常発生するもので、想定された動作です。HashMapは、バケット内でエントリを連結して衝突を処理します。

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, String> m = new HashMap<>();
        for (int i = 0; i < 5; i++) {
            m.put(i, "v" + i);
        }
        System.out.println(m.size() + " entries stored");
    }
}

衝突とチェイン

Java 8より前は、衝突したすべてのエントリがバケット内の単方向リンクリストに格納されていました。

検索では、対応するキーが見つかるまでequals()を呼び出しながらリストをたどります。

  • 衝突が少ない場合：実質的にO(1)のままです。
  • 1つのバケットで衝突が多い場合：そのバケットではO(n)に近づくように性能が低下します。
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("FB", 1);
        m.put("Ea", 2);
        System.out.println("FB hash: " + "FB".hashCode());
        System.out.println("Ea hash: " + "Ea".hashCode());
        System.out.println(m.get("FB") + ", " + m.get("Ea"));
    }
}

FBとEaが衝突する理由

文字列"FB"と"Ea"は、Javaでは同じhashCode()を持ちます。これは衝突の典型的な例です。

ハッシュコードが同じでも、バケット内ではequals()によって区別されるため、マップはそれらを別々に保持します。

public class Main {
    public static void main(String[] args) {
        System.out.println("FB".hashCode() == "Ea".hashCode());
        System.out.println("FB".equals("Ea"));
    }
}

負荷係数

負荷係数は、テーブルが拡張されるまでにどの程度埋まるかを制御します。デフォルトは0.75です。

  • 容量16、負荷係数0.75の場合、12個のエントリに達するとサイズ変更が発生します。
  • 負荷係数を低くするとメモリを無駄に消費しますが、衝突を減らせます。
  • 負荷係数を高くするとメモリを節約できますが、衝突が増えます。
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(16, 0.75f);
        for (int i = 0; i < 12; i++) m.put(i, i);
        System.out.println("Stored " + m.size() + " entries");
    }
}

テーブルのサイズ変更

エントリ数がcapacity * loadFactorを超えると、テーブルのサイズが2倍になります。

既存のすべてのエントリは、新しく作られた大きなテーブルに再ハッシュされます。これはコストの高い処理なので、大きなマップでは事前にサイズを確保することが重要です。

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        // Pre-size to avoid repeated resizes
        Map<Integer, Integer> m = new HashMap<>(1024);
        for (int i = 0; i < 800; i++) m.put(i, i * 2);
        System.out.println("size = " + m.size());
    }
}

パフォーマンスのための事前サイズ設定

格納するエントリ数のおおよその見込みが分かっている場合は、初期容量を指定してサイズ変更の繰り返しを避けてください。

目安は、初期容量 = expectedSize / 0.75 + 1です。

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        int expected = 1000;
        int capacity = (int) (expected / 0.75) + 1;
        Map<Integer, String> m = new HashMap<>(capacity);
        System.out.println("Initial capacity hint: " + capacity);
        m.put(1, "ok");
        System.out.println(m.get(1));
    }
}

nullキーとnull値

HashMapでは、nullキーを1つと複数のnull値を使用できます。

  • nullキーは常にバケット0に入ります（ハッシュは0として扱われます）。
  • キーが存在しない場合と値がnullの場合を区別するには、getOrDefaultを使用してください。
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, String> m = new HashMap<>();
        m.put(null, "nullKeyValue");
        m.put("a", null);
        System.out.println(m.get(null));
        System.out.println(m.getOrDefault("missing", "default"));
    }
}

反復順序は保証されない

HashMapは反復順序について一切保証しません。順序はハッシュコードとバケットの配置によって決まります。

予測可能な順序が必要な場合は、LinkedHashMap（挿入順）またはTreeMap（ソート順）を使用してください。

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("one", 1);
        m.put("two", 2);
        m.put("three", 3);
        for (Map.Entry<String, Integer> e : m.entrySet()) {
            System.out.println(e.getKey() + "=" + e.getValue());
        }
    }
}

get() の検索経路まとめ

検索は次の手順で行われます：

  • hashCode() を計算し、ビットを拡散します。
  • マスクしてバケットのインデックスを求めます。
  • バケットをたどり、equals() でキーを比較します。
  • 一致する値を返し、一致しなければ null を返します。

適切な hashCode と正しい equals があれば、各手順を高速に実行できます。

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> stock = new HashMap<>();
        stock.put("apple", 50);
        stock.put("pear", 20);
        String key = "apple";
        Integer qty = stock.get(key);
        System.out.println(key + " -> " + qty);
    }
}

理解度チェック

HashMap がバケットを見つける仕組みを理解できているか確認してください。

まとめ

HashMap の内部動作について学びました：

  • キーはハッシュ化され、バケットに割り当てられます。
  • 衝突が発生した場合は、バケット内でエントリを連結して処理します。
  • ロードファクタ（0.75）に達すると、容量の倍増と再ハッシュが行われます。
  • あらかじめ適切な容量を確保すると、コストの高いリサイズを避けられます。また、反復処理の順序は保証されません。

次は、正しい equals がなければ hashCode だけでは不十分な理由を見ていきます。

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>(64);
        m.put("recap", 1);
        System.out.println("HashMap basics complete: " + m.get("recap"));
    }
}

よくある質問

「HashMap の仕組み」レッスンは無料ですか？

はい。「HashMap の仕組み」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Java Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Java Academyコースには全4レッスンが含まれています。

「HashMap の仕組み」で何を学びますか？

バケット、ハッシュ、衝突です。 ブラウザで直接実行するハンズオンコードでJava Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Java Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのJava Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。

「HashMap の仕組み」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このJava Academyレッスンでコードを書いて実行できますか？

はい。すべてのJava Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. HashMap の仕組み
  2. equals/hashCode の契約
  3. hashCode の実装
  4. ツリー化とパフォーマンス
← Java Academyに戻る