ハッシュ表：線形探索法

線形探索法はオープンアドレス法の一種です。キーを一つの配列に保存し、衝突時は一マスずつ後ろへ進み、末尾で折り返します。ハッシュの分布がよく実効占有率が低ければ、挿入・検索・削除は平均 O(1)。埋まるにつれ、クラスタリングが探索を長くします。

配列を駐車場、h(k) = k mod capacity を指定場所と考えてください。埋まっていれば次を探し、末尾の後は 0 へ戻ります。

線形探索法の仕組み

スロットは三状態です。空は未使用、使用中はキーあり、墓石は削除済み。墓石は再利用できますが、検索を止められません。同じ探査列のキーが後ろに残る可能性があるからです。

三操作は i = hash(k) から i = (i + 1) mod capacity で進み、最大一周です。

get(k) は一致で添字を返し、本当の空で未発見を返します。墓石や別キーなら続けます。空は対象がその位置を越えて挿入されていないことを示します。削除でこの情報を偽ってはいけません。

delete(k) は同じ検索をし、一致を墓石へ変えます。キーはなくなっても後続検索は通過できます。

insert(k) は最初の再利用候補 spot を覚えます。墓石があればその位置、なければ終了時の空です。最初の墓石で即書き込みはしません。先へ進み、既存キーなら変更なしで返します。空に達するか、一周して重複がないと分かってから記憶位置へ書きます。一致も空も墓石もなければ満杯の例外です。固定配列が全保存領域なので、これは実際の容量制約です。

表示容量 5–11、キー 1–99 は画面の制約です。一方、固定表の満杯処理はどの容量でも必要です。

操作をステップで追う

既定は容量 7、h(k) = k mod 7。ハッシュ、各スロットの探査、書き込み確定の順です。

1. insert(10)：10 mod 7 = 3。空の 3 へ 10 を書く。
2. insert(20)：h(20) = 6。空の 6 へ 20。
3. insert(17)：h(17) = 3。3 は 10 なので、空の 4 へ 17。
4. insert(24)：h(24) = 3。3 の 10、4 の 17 を越え、5 へ 24。3–5 が連続クラスタになる。
5. get(17)：3 から二回の探査で添字 4 に発見。
6. delete(10)：3 に一致し、空ではなく墓石へ変える。
7. 再び get(17)：3 の墓石を越え、4 で発見。3 を空にしていたら早く止まり、誤って未発見になる。
8. insert(31)：31 mod 7 = 3。3 の墓石を覚え、4 の 17、5 の 24、6 の 20 を調べ、空の 0 へ折り返す。重複なしと確認してから、覚えた 3 に 31 を書き、墓石を回収する。

カーソルはハッシュ位置から一マスずつ進み、検査中を強調します。墓石は専用の淡い印で、再利用できる位置と検索を終了できる空を区別します。

時間・空間計算量

n は有効キー数、m は容量です。

m と n が同じ桁なら最悪界を O(n) とも書きます。墓石が多い場合は生きたキーだけでなく容量で数えます。空間は O(m) で、各キーへの連結ポインターは不要です。

負荷率は α = n / m。占有率が 1 に近づくと探査が長くなります。成功検索と失敗検索の期待費用は異なり、線形探索には一次クラスタリングもあります。単一の 1 / (1 − α) だけで両方を表せません。

連続した使用中領域にハッシュされた新キーは後ろの空きを探し、挿入が領域を延長します。大きいクラスタほどさらに大きくなりやすく、既定の 3–5 が小さな例です。実装は約 0.7–0.75 などの閾値で拡張・再ハッシュすることがありますが、探査方式と性能目標による値で普遍ではありません。墓石も清掃対象の占有に含めます。

境界ケース

• 重複挿入：一致で書き込まず、上書きも複製もしない。
• 満杯：一周して空、墓石、一致がなければオーバーフロー。拡張可能な実装は通常その前に拡張する。
• キーなし：最初の空で停止。空がなくても m 回の上限で終わる。
• 墓石の蓄積：有効キーが少なくても多くの墓石を通過する。再ハッシュは有効キーだけを移し、墓石を除く。

よくある間違い

• 削除位置を空にする。 偽の切れ目で検索が止まり、後続キーが見つからなくなります。
• 最初の墓石へ即挿入する。 後ろに同じキーがあるかもしれません。位置を覚え、重複検査後に書きます。
• 剰余を忘れる。 i = (i + 1) mod capacity で折り返します。
• 墓石を再利用しない。 検索は通過し、挿入は回収します。永久に使用中として扱うとスロットを失います。
• 拡張・清掃をしない。 高占有率でクラスタがつながり、墓石も経路を伸ばします。占有率の監視と再ハッシュが期待性能を保ちます。