「Hello Algo」で学ぶハッシュテーブル完全総まとめ：衝突・負荷率・拡張・ハッシュアルゴリズムの要点をQ&Aで体系的に整理

ハッシュテーブルは、key を入力すると $O(1)$ 時間で value を取得できる「高速な辞書構造」であり、あらゆるプログラミング言語の基盤として使われています。本記事は、『Hello Algo』日本語版のハッシュテーブル章のまとめを軸に、ハッシュ衝突の本質、負荷率と拡張の仕組み、チェイン法・オープンアドレス法の得失、ハッシュアルゴリズムに求められる性質までを、リポジトリ内の実装コードを参照しながら整理します。読み終えると、「なぜ $O(1)$ なのか」「いつ $O(n)$ に劣化するのか」といった設計上の問いに、根拠を持って答えられるようになります。

ハッシュテーブルの本質：key から value への $O(1)$ マッピング

ハッシュテーブルの核心は、キー key と値 value の対応関係を構築し、key を入力すると対応する value を $O(1)$ 時間で取得できる点にあります。

• 検索：key を入力 → $O(1)$ で value を取得
• 追加：キーと値のペアを末尾バケットへ → $O(1)$
• 削除：該当キーと値のペアを除去 → $O(1)$
• 走査：全キーと値のペア、キーのみ、値のみを列挙

配列・連結リストでは検索・削除に $O(n)$ かかるのに対し、ハッシュテーブルは追加・検索・削除・更新がすべて $O(1)$ 平均で実現できる点が最大の特徴です。この基本操作の詳細と各言語のコード例は、ハッシュテーブル解説で確認できます。

実際の「教科書的実装」として、本リポジトリの array_hash_map.py は buckets 配列（100 バケット）と hash_func（key % 100）だけでハッシュテーブルを構成し、get / put / remove / entry_set / key_set / value_set という一連の操作を提供しています。put は既存キーなら値を上書き、新規ならバケットへ格納する「追加と更新の一体操作」であり、多くの言語組み込みハッシュテーブルの設計思想と一致します。

ハッシュ衝突とは何か、なぜ必ず起こり得るのか

ハッシュ関数は key を配列インデックスへ写像し、対応するバケットへアクセスして value を取り出します。ところが、異なる 2 つの key が同じ配列インデックスになることがあり、これをハッシュ衝突（ハッシュ衝突）と呼びます。衝突が起きると検索結果が誤るため、何らかの衝突処理が必須になります。

衝突が構造的に避けられない理由はシンプルです。ハッシュ関数の最後のステップは「配列長 $n$ での剰余」であり、入力空間（key のとり得る値の総数）は出力空間（配列の長さ）よりはるかに大きいからです。つまりハッシュテーブルの本質は「大きな状態空間を小さな空間へ写像する」ことであり、その代償として衝突の可能性が常に残ります。

なお、衝突の起こりやすさはハッシュ関数の質と容量設定に依存し、最良・最悪のケースを図解した資料として、ハッシュ衝突の最良・最悪条件や衝突の概念図も章内で参照できます。

負荷率と拡張：衝突を緩和する仕組み

ハッシュテーブルの容量が大きいほど衝突確率は低くなるため、拡張（リサイズ）によって衝突を緩和できます。しかし配列の拡張と同様に、全要素の再配置を伴うためコストは大きくなります。

衝突の深刻さを測る指標が**負荷率（load factor）**で、要素数 ÷ バケット数 と定義されます。これは「テーブルがどれだけ埋まっているか」を表し、拡張を発動する条件として多用されます。

本リポジトリのチェイン法実装 hash_map_chaining.py は、その典型例です。

• 初期容量 capacity = 4、負荷率しきい値 load_thres = 2.0 / 3.0、拡張倍率 extend_ratio = 2
• put のたびに load_factor() がしきい値を超えていないか検査し、超えたら extend() を実行
• extend() は容量を 2 倍にした新バケット配列へ全ペアを再挿入

def put(self, key: int, val: str):
    # 負荷率がしきい値を超えたら、リサイズを実行
    if self.load_factor() > self.load_thres:
        self.extend()
    # ... バケットへ挿入

def extend(self):
    buckets = self.buckets                  # 元のテーブルを一時保存
    self.capacity *= self.extend_ratio      # 容量を2倍に
    self.buckets = [[] for _ in range(self.capacity)]
    self.size = 0
    for bucket in buckets:                  # 全ペアを再ハッシュして再挿入
        for pair in bucket:
            self.put(pair.key, pair.val)

しきい値の具体的な値は言語によって異なり、章内解説では「Java では負荷率が 0.75 を超えると容量を 2 倍に拡張する」と述べられています。本リポジトリの実装では 2/3 を採用しており、このようにしきい値と拡張倍率は「性能と空間使用率のトレードオフ」として設計者が決定するパラメータであることが分かります。

拡張が衝突を緩和する原理は後述の Q&A で詳しく扱いますが、その概念図として再ハッシュのイメージが章内に用意されています。

衝突解決戦略 1：チェイン法（チェイン方式）

チェイン法は、単一要素のバケットを連結リストに変換し、衝突したすべての要素を同じ連結リストへ格納する方式です。要素の追加は連結リストの末尾へ $O(1)$ で行え、検索はリスト内の線形走査で行います。

本リポジトリのチェイン法実装では、get が該当バケットの連結リスト（Python の list）を走査して key を照合します。

def get(self, key: int) -> str | None:
    index = self.hash_func(key)
    bucket = self.buckets[index]
    for pair in bucket:                     # バケットを走査
        if pair.key == key:
            return pair.val
    return None

ただし、連結リストが長すぎると検索効率は $O(n)$ に劣化します。この問題への対処として、章内解説では「連結リストを AVL 木または赤黒木に変換し、検索操作を $O(\log n)$ に最適化できる」と述べられています。実例として、Java の HashMap は JDK 1.8 以降、配列長が 64 かつ連結リスト長が 8 に達すると赤黒木へ変換されます。この方式の構造はチェイン法の図で視覚的に確認できます。

衝突解決戦略 2：オープンアドレス法（オープンアドレス方式）

オープンアドレス法は、衝突時に複数回の探索（プロービング）を行って空きバケットを探す方式です。代表的な手法として、固定ステップ幅で順次探す線形探索と、複数のハッシュ関数を切り替える**二重ハッシュ（多重ハッシュ）**があります。

• 線形探索：実装が単純。ただし、要素を直接削除できず（後述の削除マークが必要）、連続したデータ塊ができるクラスタリングが発生しやすいという欠点があります。
• 二重ハッシュ：複数のハッシュ関数で探索位置を分散させるため、線形探索よりクラスタリングが起きにくい反面、ハッシュ関数の計算量が増えるというトレードオフがあります。

オープンアドレス法で重要なのが**「要素を直接削除できない」**という制約です。削除した箇所を単純に空にしてしまうと、後続要素の探索系列が途切れて見つからなくなるためです。本リポジトリの hash_map_open_addressing.py では、削除済みを表す専用の TOMBSTONE（墓石）マーカーを導入しています。

self.TOMBSTONE = Pair(-1, "-1")   # 削除済みマーク

def remove(self, key: int):
    index = self.find_bucket(key)
    if self.buckets[index] not in [None, self.TOMBSTONE]:
        self.buckets[index] = self.TOMBSTONE  # 削除マーカーで上書き
        self.size -= 1

find_bucket は線形探索でバケットを辿りつつ、最初に見つけた TOMBSTONE の位置を記録します。削除済みとマークされた領域は再利用可能で、新要素の挿入時にその位置へ配置すれば、探索系列を変えずに空間利用率も維持できます。この削除・マーク・再利用の流れはオープンアドレス法の削除図で図解されています。

なお、オープンアドレス法ではバケットが None か TOMBSTONE か Pair かの判別が重要になるため、put 時の上書き判定や extend 時の再挿入処理でも TOMBSTONE を明示的に除外しています。

言語ごとの実装戦略の違い

プログラミング言語ごとに、異なるハッシュテーブル実装が採用されています。 章内まとめでは代表例として以下が挙げられています。

• Java の HashMap：チェイン法を採用（前述のとおり、リストが長くなると赤黒木へ変換）
• Python の dict：オープンアドレス法を採用

同じ「ハッシュテーブル」という名前でも、衝突処理の戦略が異なれば、削除の可否、クラスタリング傾向、最悪時の挙動まで変わるため、言語をまたいで比較しながら読むと設計思想の違いが見えてきます。詳細はハッシュ衝突の解説を参照してください。

ハッシュアルゴリズムに求められる性質と代表的なアルゴリズム

ハッシュテーブルで使うハッシュアルゴリズムには、主に次の性質が求められます。

1. 決定性：同じ key からは常に同じ出力が得られること
2. 高効率：計算コストが小さく、$O(1)$ 検索の定数項を小さく保てること
3. 均一分布：key がバケット全体に均等に散らばり、衝突を最小化できること

一方、**暗号学の文脈では、さらに「耐衝突性」と「雪崩効果（アバランシェ効果）」**が求められます。入力がわずかに変わると出力が大きく変わる性質を雪崩効果と呼び、安全性の根幹を担います。

ハッシュ値の均一分布を最大化するための実践的な工夫として、ハッシュアルゴリズムは通常、大きな素数を法（modulus）として用います。本リポジトリの simple_hash.py は、加算・乗算・XOR・回転の 4 種類のシンプルなハッシュを比較実装しており、いずれも法として大きな素数 1000000007 を使っています。

def mul_hash(key: str) -> int:
    hash = 0
    modulus = 1000000007          # 大きな素数を法として利用
    for c in key:
        hash = 31 * hash + ord(c) # 乗算のたびに前の値を31倍（多項式ハッシュ）
    return hash % modulus

31 * hash + ord(c) の形は文字列ハッシュの代表的な設計であり、連続した文字列全体に値が依存するため、単純な加算ハッシュより分布が均一になりやすい構造です。

一般的なハッシュアルゴリズムとしては、MD5、SHA-1、SHA-2、SHA-3 などが挙げられます。章内では、MD5 はファイル完全性の検証に、SHA-2 はセキュリティ用途やプロトコルでよく用いられると整理されています。なお、暗号学的ハッシュは「衝突を発見することが現実的に困難」であることを目的としている点で、テーブルのインデックス計算用ハッシュとは目的が異なる点に注意が必要です。

さらに、プログラミング言語は通常、各データ型に対して組み込みのハッシュアルゴリズムを提供し、ハッシュテーブルのバケットインデックス計算に用います。本リポジトリの built_in_hash.py は、Python の hash() が整数・真偽値・小数・文字列・タプル・オブジェクトに対してそれぞれ異なるハッシュ値を返すことを確認するコードです。このとき、通常ハッシュ可能（ハッシュ化可能）なのは不変オブジェクトだけです。Python のタプルはハッシュ可能ですが、リストのような可変オブジェクトは値が変わるとハッシュ値の一貫性が崩れるためハッシュ化できません。

Q&A で深掘りするハッシュテーブルの設計論

まとめ章の Q&A は、ハッシュテーブルへの理解を「使える」段階から「設計を説明できる」段階へ引き上げてくれます。ここでは 7 つの問いをそれぞれ整理します。

Q1：ハッシュテーブルの時間計算量が $O(n)$ になるのはどのような場合？

ハッシュ衝突が深刻な場合です。チェイン法では衝突した要素が同一連結リストに蓄積され、検索がリストの線形走査になるため $O(n)$ に劣化します。逆に、ハッシュ関数の設計が適切で、容量設定が合理的で、衝突が比較的均等な場合は $O(1)$ が保たれます。言語組み込みのハッシュテーブルを使う実務では、通常は $O(1)$ とみなしてよい、というのが教科書的な結論です。

Q2：なぜハッシュ関数 $f(x) = x$ を使わないのか？ 衝突がなくなるのでは？

$f(x) = x$ なら各要素は一意のバケットインデックスに対応し、これは配列と等価になります。しかし、入力空間（key の全可能性）は出力空間（配列長）よりはるかに大きいため、ハッシュ関数の最後のステップはほぼ常に「配列長での剰余」になります。言い換えれば、ハッシュテーブルの目的は大きな状態空間を小さな空間へ写像し、$O(1)$ の検索効率を提供することであり、「写像」である以上 $f(x) = x$ のような完全一意マップは非現実的なのです。

Q3：底層は配列・連結リスト・二分木なのに、なぜ効率がそれらより高いのか？

第一に、時間効率が高くなる一方で空間効率は低くなります。ハッシュテーブルには常に一定割合の未使用バケット（空き領域）が存在し、空間を犠牲に時間を得ています。

第二に、効率向上が効くのは特定の用途に限られます。ある機能が同じ時間計算量で配列や連結リストによって実装できるなら、通常そちらのほうが速いのです。なぜならハッシュ関数の計算自体にコストがかかり、時間計算量の定数項が大きいからです。

第三に、ハッシュテーブルの時間計算量は劣化し得ます。チェイン法では連結リストや赤黒木での検索を伴うため、$O(n)$ への劣化リスクが構造的に残ります。「ハッシュテーブルが常に最速」ではなく、用途に応じた構造選択が重要だと分かります。

Q4：二重ハッシュにも「要素を直接削除できない」欠点はある？ 削除マーク領域は再利用できる？

二重ハッシュもオープンアドレス法の一種であり、オープンアドレス法はすべて「要素を直接削除できない」という共通の欠点を持ちます。そのため削除のマーク付け（TOMBSTONE 方式）が必要になります。そして削除済みマークの領域は再利用できます。新要素を挿入し、ハッシュ関数が削除マーク位置を指し示したなら、その位置に新要素を配置してよいのです。こうすることで、ハッシュテーブルの探索系列を変えずに保ちつつ、空間利用率も確保できます。本リポジトリの hash_map_open_addressing.py の find_bucket は、この「最初に見つけた TOMBSTONE へ新要素を移動させる」ロジックを直接実装しています。

Q5：なぜ線形探索で要素を探すときにハッシュ衝突が発生するのか？

検索時はハッシュ関数で該当バケットとキーと値のペアを見つけますが、バケット内の key が探している key と一致しなければ、それはすでにハッシュ衝突が起きていることを意味します。つまり衝突とは「別の key が先にこのバケットを占有していた」状態であり、そのため線形探索法は事前に設定したステップ幅で順に下へ探索し、正しいキーと値のペアを見つけるか、空きバケットに到達して見つからないと判断するまで続けます。

Q6：なぜハッシュテーブルの拡張でハッシュ衝突を緩和できるのか？

ハッシュ関数の最後のステップは、多くの場合配列長 $n$ での剰余で、出力値をインデックス範囲内に収めます。拡張後は配列長 $n$ が変化するため、key に対応するインデックスも変化します。その結果、もともと同じバケットに衝突していた複数の key が、拡張後は複数のバケットに分散されることがあり、これが衝突緩和の原理です。一方で、この「インデックス再計算」こそが拡張を $O(n)$ の高コスト操作にしている原因でもあります。

Q7：効率的な読み書きなら配列を直接使えばよいのでは？

その通りで、key が連続した小範囲の整数であれば配列を直接使うのが最もシンプルで高効率です（たとえば「0〜99 の学生番号」のようなケース）。しかし key が文字列など他の型の場合、配列のインデックスにはできないため、ハッシュ関数で key を配列インデックスへ写像し、バケット配列を通じて要素を格納する必要があります。この「ハッシュ関数 ＋ バケット配列」という構造こそがハッシュテーブルなのです。

まとめ：ハッシュテーブル理解のチェックリスト

本記事で整理した内容を、確認用チェックリストとしてまとめます。

• 入力 key から $O(1)$ で value を検索できるのがハッシュテーブルの最大の利点
• 基本操作は検索・追加・削除・走査の 4 系統
• ハッシュ関数は key を配列インデックスへ写像し、対応バケットから value を取得する
• 異なる key が同じインデックスになる現象がハッシュ衝突
• 容量が大きいほど衝突確率は下がり、拡張で緩和できるがコストは大きい
• **負荷率（要素数 ÷ バケット数）**が拡張の発動条件として多用される
• チェイン法は衝突要素を連結リスト化し、長大化時は赤黒木化で $O(\log n)$ へ改善
• オープンアドレス法は複数回の探索で処理。線形探索は削除不能・クラスタリングの欠点、二重ハッシュは計算量増の欠点
• 言語ごとに実装が異なる（例：Java HashMap はチェイン法、Python dict はオープンアドレス法）
• ハッシュアルゴリズムには決定性・高効率・均一分布が必須で、暗号用途では耐衝突性と雪崩効果も要求される
• 均一分布のために大きな素数を法とすることが多い
• MD5・SHA-1・SHA-2・SHA-3 などの代表アルゴリズムは用途が異なる
• 組み込みのハッシュは不変オブジェクトに限定されるのが一般的

より深く学びたい読者は、本リポジトリ内のハッシュテーブル・ハッシュ衝突・ハッシュアルゴリズムの各章本文、およびチェイン法・オープンアドレス法の完全実装コード hash_map_chaining.py と hash_map_open_addressing.py を実際に実行して動作を確認することをおすすめします。