ハッシュテーブル（ハッシュ表）とは？仕組みと衝突の対処をPythonで作ってわかりやすく解説

ハッシュテーブル（ハッシュ表）とは、キーを「ハッシュ関数」で数値に変換し、その数値を配列の番地として値をしまうデータ構造です。キーから置き場所を計算で直接求めるので、データが何件あっても平均してほぼ一定の時間で検索・追加・削除ができます。

Pythonの辞書（dict）、JavaのHashMap、JavaScriptのMapなど、多くの言語の「キーと値の組」を扱う仕組みの中身がこれです。この記事では、仕組みを図の代わりにPythonの実行結果で確かめながら、衝突（コリジョン）とその対処、配列を広げるタイミング、実際の言語での実装までを順に説明します。コードはPython 3.12で実行しました。

ハッシュテーブルを一言でいうと

ロッカーが並んだ部屋を想像してください。荷物（値）を預けるとき、名前（キー）から決まった計算でロッカー番号を出し、その番号の箱に入れます。取り出すときも同じ計算をすれば番号が分かるので、端から順に箱を開けて探す必要がありません。

用語	意味	ロッカーのたとえ
キー（key）	値を探すための名前	預けた人の名前
値（value）	しまっておくデータ	荷物
ハッシュ関数	キーから数値を計算する関数	名前から番号を出す決まり
バケット（bucket）	配列の1マス	ロッカーの1つの箱
衝突（collision）	違うキーが同じ番号になること	2人の番号がかぶる

「ハッシュテーブル」「ハッシュ表」「ハッシュマップ」はほぼ同じものを指します。「連想配列」はキーで値を引ける仕組み全般の呼び名で、その代表的な実装がハッシュテーブルです。

ハッシュ関数で置き場所を決める

まず、ごく単純なハッシュ関数を作ってみます。文字の文字コードを足し合わせて、配列の大きさ（ここでは8）で割った余りを番号にします。

def simple_hash(key, size):
    # 文字コードを足し合わせて、表の大きさで割った余りを使う
    return sum(ord(ch) for ch in key) % size

for word in ["apple", "lemon", "melon", "peach"]:
    print(word, simple_hash(word, 8))

apple 2
lemon 3
melon 3
peach 1

余りは必ず 0〜7 になるので、8マスの配列のどこかを指します。ここで lemon と melon がどちらも 3 になりました。使っている文字が同じ（並び順だけ違う）ので、文字コードの合計が一致したためです。これが「衝突」です。

良いハッシュ関数の条件は、同じキーからは必ず同じ数値が出ること、計算が速いこと、そしてキーがばらばらの番号に散らばることです。上の関数は3つ目が弱く、文字の並べ替えだけで衝突します。実用のハッシュ関数は文字の位置も計算に入れて、こうした偏りを減らしています。

衝突の対処法：チェイン法とオープンアドレス法

キーの種類は無限にあり、配列のマスは有限なので、衝突をゼロにすることはできません。対処法は大きく2つあります。

方式	やり方	長所	短所	採用例
チェイン法（連鎖法・分離連鎖法）	1つのマスにリストを持たせ、衝突した要素をつないでいく	実装が簡単。削除も素直に書ける	リストをたどる分の手間とメモリがかかる	JavaのHashMap
オープンアドレス法（開番地法）	ふさがっていたら決まった規則で別の空きマスを探す	配列だけで済み、メモリの並びがよい	表が埋まるほど探す回数が急に増える。削除に工夫が要る	Pythonのdict（CPython）

JavaのHashMapは、OpenJDKのソースコード（HashMap.java）の実装メモによると、ふだんはマスごとに要素をつなぐ方式で、1つのマスに要素が増えすぎると（しきい値は8個）木構造に切り替えて探す手間を抑えています。

オープンアドレス法で空きを探す規則には、1つずつ隣を見る線形探査、間隔を2乗で広げる二次探査、2つ目のハッシュ関数で間隔を決めるダブルハッシュなどがあります。CPythonのdictは、ソースコード（Objects/dictobject.c）のコメントによると、ハッシュ値の上位ビットも混ぜながら次の番号を計算する独自の探査を使っています。

Pythonで小さなハッシュテーブルを作る

仕組みを確かめるため、チェイン法のハッシュテーブルを40行ほどで書いてみます。負荷率（後述）が0.75を超えたら、配列を2倍に広げて入れ直す処理も入れています。

class HashTable:
    """チェイン法（連鎖法）で衝突を処理する、学習用のハッシュテーブル"""

    def __init__(self, size=8):
        self.size = size
        self.buckets = [[] for _ in range(size)]
        self.count = 0

    def _index(self, key):
        return sum(ord(ch) for ch in key) % self.size

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for pair in bucket:
            if pair[0] == key:          # 同じキーなら上書き
                pair[1] = value
                return
        bucket.append([key, value])     # 新しいキーなら末尾に追加
        self.count += 1
        if self.count / self.size > 0.75:   # 負荷率が0.75を超えたら広げる
            self._resize(self.size * 2)

    def get(self, key):
        for k, v in self.buckets[self._index(key)]:
            if k == key:
                return v
        raise KeyError(key)

    def _resize(self, new_size):
        old = [pair for bucket in self.buckets for pair in bucket]
        self.size = new_size
        self.buckets = [[] for _ in range(new_size)]
        self.count = 0
        for k, v in old:
            self.put(k, v)
        print(f"-- サイズを{new_size}に拡張 --")

    def show(self):
        for i, bucket in enumerate(self.buckets):
            print(i, bucket)


t = HashTable()
for word, price in [("apple", 150), ("lemon", 120), ("melon", 800), ("peach", 300)]:
    t.put(word, price)
t.show()
print("melon =", t.get("melon"))
for word, price in [("grape", 500), ("kiwi", 100), ("mango", 400)]:
    t.put(word, price)
t.show()

実行結果です。

0 []
1 [['peach', 300]]
2 [['apple', 150]]
3 [['lemon', 120], ['melon', 800]]
4 []
5 []
6 []
7 []
melon = 800
-- サイズを16に拡張 --
0 []
1 [['peach', 300]]
2 [['apple', 150], ['mango', 400]]
3 []
4 [['kiwi', 100]]
5 []
6 []
7 []
8 []
9 []
10 []
11 [['lemon', 120], ['melon', 800]]
12 []
13 []
14 []
15 [['grape', 500]]

3番のマスに lemon と melon が並んでいるのがチェイン法の衝突処理です。get(“melon”) は3番のマスだけを見て、その中のリストを先頭からたどって見つけています。7件目の mango を入れた時点で 7÷8 が0.75を超えたので、配列が16マスに広がり、全部の要素が新しい番号に入れ直されました。サイズが変わると割る数が変わるので、置き場所も変わります。

計算量：なぜ速いのか、いつ遅くなるのか

操作	平均	最悪	参考：配列を先頭から探す場合
検索	O(1)	O(n)	O(n)
追加	O(1)	O(n)	末尾への追加ならO(1)
削除	O(1)	O(n)	O(n)

O(1) は「データの件数が増えても手間がほぼ変わらない」、O(n) は「件数に比例して手間が増える」という意味です。Python公式WikiのTimeComplexityでも、dictの平均時間は「衝突がまれになる程度にハッシュ関数が十分よい」ことを前提にしていると書かれています。全部のキーが同じ番号に集まると、1本の長いリストを端から探すのと同じになり、O(n) まで落ちます。

実際に、100万件のリストと辞書で「最後の要素があるか」を調べる時間を比べました（Apple M2、Python 3.12.15）。

import timeit

n = 1_000_000
keys = [f"user{i}" for i in range(n)]
as_list = keys
as_dict = dict.fromkeys(keys)
target = f"user{n - 1}"   # 最後の要素を探す

t_list = timeit.timeit(lambda: target in as_list, number=10) / 10
t_dict = timeit.timeit(lambda: target in as_dict, number=10) / 10
print(f"list: {t_list * 1000:.3f} ms")
print(f"dict: {t_dict * 1000:.6f} ms")

list: 5.386 ms
dict: 0.000150 ms

数値は環境や実行ごとに変わりますが、リストは100万件を先頭から比べるのに対し、辞書はハッシュ値から置き場所を計算するだけなので、桁違いの差になります。

負荷率とリサイズ

負荷率（ロードファクター）は「入っている要素の数 ÷ マスの数」です。高いほどメモリの無駄は減りますが、衝突が増えて遅くなります。そこで実際の実装は、負荷率が一定を超えると配列を広げて入れ直します。

• JavaのHashMapは、公式APIドキュメントで既定の負荷率を0.75とし、超えるとバケット数をおよそ2倍にして作り直すと説明しています（Java SE 25、2026年10月15日確認）。
• CPythonのdictは、ソースコードのコメントで負荷率を3分の2未満に保つとしています。オープンアドレス法は表が埋まると探す回数が急に増えるので、チェイン法より低めの値になっています。

入れ直しの瞬間だけは全要素を動かすので時間がかかりますが、たまにしか起きないため、ならすと1回あたりの追加はO(1)とみなせます。

Pythonのdictで知っておきたいこと

キーにできるのは「ハッシュ可能」なものだけ

print(hash(1), hash(2), hash(100))
try:
    {[1, 2]: "x"}
except TypeError as e:
    print("TypeError:", e)

1 2 100
TypeError: unhashable type: 'list'

リストのように中身を後から変えられるものは、変えた瞬間にハッシュ値が変わって置き場所が分からなくなるため、キーにできません。文字列・数値・タプル（中身もハッシュ可能なもの）はキーにできます。Python言語リファレンスのデータモデルでも、ハッシュ可能なコレクションではキーのハッシュ値が変わらないことが求められると説明されています。

文字列のハッシュ値は起動ごとに変わる

import subprocess, sys
for seed in ["1", "2"]:
    out = subprocess.run([sys.executable, "-c", "print(hash('apple'))"],
                         env={"PYTHONHASHSEED": seed}, capture_output=True, text=True)
    print(seed, out.stdout.strip())

1 3677379510239698077
2 -7482492162501164091

同じ ‘apple’ でも、シード（PYTHONHASHSEED）が違うと別のハッシュ値になります。Pythonのコマンドラインと環境のドキュメントによると、文字列とバイト列のハッシュのランダム化は既定で有効です。これは、わざと同じ番号に集まるキーを大量に送りつけて辞書をO(n²)の遅さにする攻撃を防ぐための仕組みです。ハッシュ値をファイルに保存して次回の起動で使う、といった書き方はしないでください。

順番は挿入順が保証されている

ハッシュテーブルは一般には順番を持ちませんが、Pythonのdictは組み込み型のドキュメントにあるとおり、バージョン3.7から挿入した順番で取り出せることが言語仕様として保証されています。「ハッシュテーブルなので順番はばらばら」という説明は、Pythonのdictには当てはまりません。

どこで使われているか

• 言語の標準機能：Pythonのdictとset、JavaのHashMapとHashSet、JavaScriptのMapとSetなど
• 重複チェック：一度見たものをsetに入れておき、2回目かどうかをすぐ判定する
• キャッシュ：計算結果や取得結果をキーで覚えておき、同じ要求に即答する
• データベースのハッシュインデックス：完全一致の検索に強い。範囲検索には向かない（詳しくはデータベースのインデックスとは？）

なお、パスワードの保存などで使う「ハッシュ化」は、同じハッシュ関数でも目的が違い、元に戻しにくいことや衝突を見つけにくいことが重視されます。こちらはハッシュ化とは？暗号化との違いで解説しています。辞書の基本的な使い方はPython辞書のget()の使い方が参考になります。

よくある質問

Q. ハッシュテーブルとは簡単にいうと何ですか？

キーをハッシュ関数で数値に変え、その数値を配列の番地にして値をしまうデータ構造です。置き場所を計算で求めるので、平均するとデータ量に関係なく速く検索できます。

Q. ハッシュテーブルと配列の違いは何ですか？

配列は0、1、2…という番号で値を取り出しますが、ハッシュテーブルは文字列などのキーで値を取り出せます。中身は配列で、キーから番号を計算する部分がハッシュ関数です。

Q. ハッシュの衝突とは何ですか？

違うキーからハッシュ関数で同じ番号が出てしまうことです。完全には防げないため、同じマスにリストでつなぐチェイン法や、別の空きマスを探すオープンアドレス法で対処します。

Q. Pythonの辞書はハッシュテーブルですか？

はい。CPythonのdictはオープンアドレス法のハッシュテーブルで実装されています。バージョン3.7からは挿入した順番で取り出せることも保証されています。

Q. ハッシュテーブルが遅くなるのはどんなときですか？

多くのキーが同じ番号に集まって衝突が増えたときです。負荷率が高すぎる場合や、ハッシュ関数が偏っている場合に起きやすく、最悪では端から探すのと同じO(n)になります。

あわせて読みたい

学習の進め方はPython学習のロードマップ、職種ごとの違いはエンジニアの職種の違いにまとめています。