再ハッシュ

2025年10月21日

再ハッシュ

英語表記: Rehashing

概要

再ハッシュとは、ハッシュテーブル（連想配列を実現するためのデータ構造）の格納効率が低下した際、テーブルのサイズを自動的に拡大し、すべてのデータを新しいテーブルに再配置する処理のことです。この処理は、データ構造（ハッシュと連想配列）の根幹である「高速なアクセス性能」を維持するために不可欠なメカニズムです。具体的には、データが増加した結果、ハッシュ関数が導き出す格納位置が重複する「衝突（コリジョン）」の発生率を低減させる目的で実施されます。

詳細解説

再ハッシュは、私たちが扱うデータ構造の中でも特に重要なハッシュテーブルの性能を保証するために組み込まれた、巧妙な解決策です。この概念を理解するためには、まずデータ構造（リスト、スタック、キュー、ツリー）という大分類の中で、ハッシュテーブルがなぜ高速なのかを再確認する必要があります。

再ハッシュが必要となる背景

ハッシュテーブルは、キー（鍵）から格納位置（インデックス）を一瞬で計算する「ハッシュ関数」を利用することで、理論上O(1)という驚異的な平均アクセス時間を実現します。しかし、格納するデータ量が増加し、テーブルの容量が固定されていると、異なるキーが同じインデックスを指してしまう「衝突」が避けられません。

この衝突が増えると、データを探す際に、そのインデックス位置からさらに連結リストを辿る、あるいは空いているセルを探すといった余計な処理（衝突解決処理）が必要になり、結果としてアクセス時間がO(1)からO(N)に近づき、性能が大きく低下してしまいます。

負荷率（ロードファクタ）と実行タイミング

再ハッシュを実行するかどうかを判断する基準となるのが、「負荷率（Load Factor）」です。負荷率は、「格納されているデータ数」を「テーブルの総バケット数（容量）」で割った値です。

$$\text{負荷率} = \frac{\text{格納データ数}}{\text{テーブル容量}}$$

この負荷率が、システムが設定した閾値（一般的には0.7や0.75など）を超えると、衝突が多発し始めていると判断され、性能維持のために再ハッシュの実行が決定されます。これは、ハッシュテーブルの効率を保つための自己監視機能のようなものだと捉えてください。

再ハッシュの動作プロセス

再ハッシュの処理は、以下のステップで実行されます。このプロセスにおいて、分類の末端である「ハッシュ関数」の役割が非常に重要になります。

新しいテーブルの準備: 現在のテーブル容量よりもはるかに大きな容量を持つ、新しい配列（バケット）がメモリ上に確保されます。通常、容量は元のテーブルの2倍など、指数関数的に増やされます。
既存データの取り出し: 現在のハッシュテーブルに格納されているすべてのデータ（キーと値のペア）を一つずつ取り出します。
ハッシュ関数の再適用: 取り出したデータに対し、新しいテーブルのサイズを考慮に入れたハッシュ関数を適用し直します。ハッシュ関数の計算自体は変わらなくても、インデックスを決定するために行う「テーブルサイズによる剰余演算（モジュロ演算）」の分母が変わるため、結果としてデータが格納されるインデックス位置はほとんどすべて変化します。
新しいテーブルへの格納: 計算された新しいインデックス位置にデータを格納します。このとき、既存の衝突解決策（連結法やオープンアドレス法など）に基づき、新しい位置へきれいに配置されます。
テーブルの切り替え: すべてのデータが新しいテーブルへ移動し終わると、古いテーブルは破棄され、新しいテーブルがハッシュテーブルとして運用を開始します。

この処理は一時的にCPUリソースを大量に消費しますが、完了後はバケットに大幅な余裕が生まれるため、衝突が減少し、ハッシュテーブルは再び高速なアクセス性能を取り戻すことができるのです。これは、データ構造の設計者が性能とメモリ効率のバランスを取るために考え抜いた、非常に洗練された仕組みだと言えます。

具体例・活用シーン

再ハッシュは、プログラミング言語の内部で連想配列（Pythonの辞書型、JavaのHashMapなど）を利用する際に、裏側で常に発生している処理です。私たちが意識しなくても、データ構造の効率を守ってくれている、縁の下の力持ちのような存在です。

図書館の棚卸しと配置換え（メタファー）

私は、再ハッシュを「図書館の引っ越しと棚卸し」に例えるのが、初心者の方にもっとも理解しやすいと考えています。

小さな図書館（初期ハッシュテーブル）: 地域の小さな図書館には、1,000冊の本を収めるための本棚（バケット）が100個しかありませんでした。本のタイトル（キー）から「何番棚」かを決める司書（ハッシュ関数）がいますが、本が増えるにつれて、一つの棚に10冊も20冊も積み重ねられるようになります（衝突）。
性能低下: 利用者が本を探しに来ても、司書は「35番棚にあるよ」と教えますが、利用者は積み重なった本の中から目的の1冊を探し出すのに時間がかかってしまいます。これがハッシュテーブルの性能低下です。
再ハッシュの決断（負荷率超過）: 図書館長（システム）は、利用者からの苦情が増えたため、「もうこのままではダメだ！」と判断します。これが負荷率の閾値超過です。
大きな建物への引っ越し（再ハッシュ実行）: 図書館長は、新しく200個の本棚がある、大きな新しい建物を用意します。そして、図書館を一時的に閉鎖し、すべての本を一度取り出します。
新しい配置の決定（ハッシュ関数の再適用）: 司書は、新しい200個の本棚に合わせて、本のタイトルから「今度は新しい200個の本棚のどこに置くべきか」を決め直し、本を再配置します。
結果: 新しい図書館は本棚に余裕ができ、司書が「この本は187番棚にあるよ」と教えれば、利用者はすぐに目的の1冊を見つけられるようになります。

このように、再ハッシュは、一時的なコスト（引っ越し作業）をかけてでも、長期的なアクセス効率を確保するための戦略的なデータ構造のメンテナンス作業なのです。

資格試験向けチェックポイント

IT Passport試験、基本情報技術者試験、応用情報技術者試験において、ハッシュテーブルの効率に関する問題は頻出です。再ハッシュに関連して押さえておくべきポイントを以下にまとめます。

目的理解の徹底: 再ハッシュの最大の目的は、データ件数の増加に伴う衝突の増加を解消し、ハッシュテーブルの本来の性能（平均アクセス時間O(1)）を維持・回復することである、と正確に理解してください。単に容量を増やすだけではない点が重要です。
トリガーは負荷率: 再ハッシュが開始される条件として、「負荷率（ロードファクタ）」が特定の閾値を超えたとき、という概念が問われます。負荷率の計算式（データ数 ÷ 容量）を覚えておきましょう。
処理コストのトレードオフ: 再ハッシュの処理自体は、テーブル内の全データを移動させるため、一時的に大きな処理時間（高コスト）がかかります。試験では、「再ハッシュは常に高速である」といった誤った選択肢が出ることがあるため、一時的な遅延が発生するトレードオフの関係性を理解しておく必要があります。
ハッシュ関数の再利用: 再ハッシュ時には、新しいテーブルサイズに合わせてハッシュ関数が「再適用」されます。特に、剰余演算（データ % テーブルサイズ）を利用している場合、テーブルサイズが変わることで、同じキーでも新しいインデックスが生成されることを理解しておきましょう。これは、ハッシュ関数の文脈で再ハッシュを考える上で最も重要な点です。