ハッシュ表

提供: ORWiki
2008年11月13日 (木) 13:40時点におけるAlbeit-Kun (トーク | 投稿記録)による版
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
ナビゲーションに移動 検索に移動

【はっしゅひょう (hash table)】

値(キー)をもつ 個の要素の集合に対し, 挿入・削除・検索の3つの機能を高速化したデータ構造. 値をハッシュキーと呼ばれるいくつかのキーで分類し, それぞれの要素を連結リストなどにより保持する. 挿入と削除をO 時間で行い, 検索は, 最悪の場合はO となるが, ハッシュキーを適切に設定すれば平均的に O となることが多い. 辞書データの保持に多く使われ, 辞書のデータを頭文字をハッシュキーとして保持する, などの例がある.