均一に分散された整数キーまたは均一に分散された整数にマップできるキーがある場合、連想コンテナーにバケット配列を簡単に使用できることを知っています。特定の負荷係数を確保するのに十分な大きさの配列を作成できれば (コレクションが動的すぎないことを前提としています)、キーの衝突の予想数は制限されます。
編集:文字列は [0..1] の範囲の位置分数と同等であると考えています。そのため、乗算と結果の下限を取ることで、任意の整数範囲にマップできます。
また、試行と同様に、プレフィックス クエリを効率的に実行することもできます。少なくとも 1 つの要素を含む最初のバケットに到達する前に順次スキップする必要がある、特定のプレフィックスに対応する空のスロットの予想数も、定数によって制限されると (証明を知らずに) 推測します (これも、選択された負荷係数)。
そしてもちろん、最悪の場合の定数時間でスタブ クエリを実行し、出力に敏感な線形期待時間のみで範囲クエリを実行できます (前の段落からの密度の推測が実際に正しい場合)。
では、試行の利点は何ですか？
分布が均一である場合、より良い結果をもたらすものは何もありません。しかし、私は間違っているかもしれません。
分布に補償されていない大きなスキューがある場合 (事前の確率がないか、最悪のケースだけを見ているため)、バケット配列のパフォーマンスは低下しますが、試行も大幅に不均衡になり、任意の長さの文字列で最悪のケースのパフォーマンスが線形になる可能性があります。したがって、データにどちらの構造を使用するかは疑問です。
だから私の質問は -正式に実証できるバケット配列に対する試行のパフォーマンス上の利点は何ですか? それらの利点を引き出すのは、どのような種類のディストリビューションですか?
異なるスケールで自己相似構造を持つ分布を考えていました。それらはフラクタル分布と呼ばれるものだと思いますが、私はそれについて何も知らないことを告白します。ディストリビューションがあらゆる規模でクラスター化する傾向がある場合は、各ノードの負荷率を同じに保ち、必要に応じて密集した領域にレベルを追加することで、優れたパフォーマンスを提供できる可能性があります。これは、バケット アレイではできないことです。
ありがとう