ハッシュテーブル
概要
ハッシュテーブル (hashtable) はさまざまなデータ型のキーをハッシュ化 (hashing) して効率的に管理し検索するためのデータ構造である。一般にキー \(x\) と関連する任意の値 \(y\) (サテライトデータ) を保持して \(y\) を効率的に検索するために用いられる。これは \(x \mapsto y\) を表しているため写像 (map) の具体的な表現の一つと考えることもできる。
ハッシュテーブルが探索木と異なるのは、検索の典型的な期待実行時間が定数時間 \(O(1)\) となることである。
Table of Contents
導入
ハッシュテーブルには 2 種類がある。静的 (static) ハッシュテーブルは内容が変化しないことを前提としており、高速な検索操作のみをサポートする。動的 (dynamic) ハッシュテーブルは検索に加えて挿入と時に削除をサポートし、それぞれの操作はそれなりの性能で動作することが求められる。
参考文献
- Avrim Blum, Manuel Blum. Universal and Perfect Hashing, CMU 15-451 Algorithms Lecture 10, 2011 Fall.