「ハッシュ表」の版間の差分
ナビゲーションに移動
検索に移動
Albeit-Kun (トーク | 投稿記録) |
|||
| (2人の利用者による、間の2版が非表示) | |||
| 1行目: | 1行目: | ||
| − | 【はっしゅひょう (hash table)】 | + | '''【はっしゅひょう (hash table)】''' |
値(キー)をもつ<math>n\,</math> 個の要素の集合に対し, 挿入・削除・検索の3つの機能を高速化したデータ構造. 値をハッシュキーと呼ばれるいくつかのキーで分類し, それぞれの要素を連結リストなどにより保持する. 挿入と削除をO<math>(1)\,</math> 時間で行い, 検索は, 最悪の場合はO<math>(n)\,</math> となるが, ハッシュキーを適切に設定すれば平均的に O<math>(1)\,</math> となることが多い. 辞書データの保持に多く使われ, 辞書のデータを頭文字をハッシュキーとして保持する, などの例がある. | 値(キー)をもつ<math>n\,</math> 個の要素の集合に対し, 挿入・削除・検索の3つの機能を高速化したデータ構造. 値をハッシュキーと呼ばれるいくつかのキーで分類し, それぞれの要素を連結リストなどにより保持する. 挿入と削除をO<math>(1)\,</math> 時間で行い, 検索は, 最悪の場合はO<math>(n)\,</math> となるが, ハッシュキーを適切に設定すれば平均的に O<math>(1)\,</math> となることが多い. 辞書データの保持に多く使われ, 辞書のデータを頭文字をハッシュキーとして保持する, などの例がある. | ||
| + | |||
| + | [[Category:組合せ最適化|はっしゅひょう]] | ||
2008年11月13日 (木) 13:40時点における最新版
【はっしゅひょう (hash table)】
値(キー)をもつ 個の要素の集合に対し, 挿入・削除・検索の3つの機能を高速化したデータ構造. 値をハッシュキーと呼ばれるいくつかのキーで分類し, それぞれの要素を連結リストなどにより保持する. 挿入と削除をO 時間で行い, 検索は, 最悪の場合はO となるが, ハッシュキーを適切に設定すれば平均的に O となることが多い. 辞書データの保持に多く使われ, 辞書のデータを頭文字をハッシュキーとして保持する, などの例がある.
