バケット

【ばけっと (bucket)】

値(キー)をもつ要素の集合を値によって分類するときに使うデータ構造. 値の種類の数 $k$ が小さいときに適している. リスト構造により実現すると, 要素の挿入, 取り出しが O$(1)$ 時間で実行できる. また, バケットを使用したバケットソート, ラディックスソートは, $k$ が小さい場合に効率が良く, 特に $k=$O$(1)$ のときには線形時間となる.