バケット

【ばけっと (bucket)】

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