辞書
summary:
辞書[Dictionary]とは,キー[key]と値[value]のペアを管理するデータ構造である.この構造は連想配列[associative array]やマップ[map],ハッシュマップ[hash map],ハッシュテーブル[hash table]とも呼ばれる.辞書においては,各キーが一意であり,それに対応する値が格納される.一般に,キーを用いて迅速に値を検索できるため,効率的なデータ管理が可能となる.
辞書の基本的な操作
辞書では一般的に以下の基本操作が提供される：
- 挿入[Insertion]: 新しいキーと値のペアを追加する
- 検索[Lookup]: キーを指定して対応する値を取得する
- 削除[Deletion]: 指定されたキーとその値を辞書から削除する
- 更新[Update]: 既存のキーに対する値を新しい値に変更する
- 存在確認[Membership Check]: 特定のキーが辞書に存在するかどうかを判定する[例: key in dict ]
これらの操作は,多くの実装において平均的な時間複雑度が $O(1)$ ,つまり定数時間で実行される.ただし,最悪の場合は $O(n)$ となることもある.
内部実装
辞書はほとんどの場合,ハッシュテーブルを用いて実装されている.ハッシュテーブルでは,キーを特殊な関数[ハッシュ関数]で処理して整数値[ハッシュ値]に変換し,この値を用いて内部配列のインデックスを決定する.
ハッシュ衝突への対処法
ハッシュ衝突[複数のキーが同じハッシュ値を生成する状況]への対処法には,主に以下の方法がある：
- チェイニング[Chaining]: 同じハッシュ値を持つ要素を連結リストで管理する
- オープンアドレッシング[Open Addressing]: 衝突が発生した場合に別の場所を探して格納する
- 線形探索法[Linear Probing]
- 二次探索法[Quadratic Probing]
- ダブルハッシング[Double Hashing]
- パーフェクトハッシュ[Perfect Hashing]: 事前にキーの集合が固定されている場合に衝突を完全に回避する方法
キーの制約条件
辞書のキーには通常,不変[immutable]なデータ型 のみが使用できる.これはハッシュ値の計算と検索の一貫性を保つためである.多くの実装では,キーがハッシュ可能[hashable]であることが要求される.つまり,キーはハッシュ関数で処理できる必要がある.
カスタムオブジェクトをキーにする場合
一部のプログラミング言語[特にPython]では,ユーザー定義オブジェクトを辞書のキーとして使用することも可能である.ただし,その場合は __hash__ メソッドと __eq__ メソッドを適切にオーバーライドする必要がある.
Mathematics is the language with which God has written the universe.
