キーと分布が事前にわかっていて、高速検索辞書を作成したいとします。アイテムを挿入し、削除することはありません。
たとえば、ここに頻度のあるキーがあります
- xyz 1000
- abc 5
- アブド 20
適切なハッシュは、xyz を 1 つのバケットに、abc,abd をバケット 2 にマップする最初の文字の単純な関数です。xyz は分布を支配するため、それに焦点を当てます。1 文字だけを見る方が、3 文字すべてを見るよりも高速です。また、ルックアップ中にバケット内の要素の数が 1 であるため、検索しているキーがそのバケットにある必要があることが確実にわかります。xyz と xyz を比較する必要はありません。
キーとディストリビューションが事前にわかっているため、完全なハッシュを使用できますが、ハッシュ関数は遅くなる可能性があります。
私は最適な解決策を探しているのではなく、実用的な解決策を探しています。