静的サイズのヘプレスハッシュマップを持つことは理論的に可能ですか？

Question

コンパイル時にサイズがわかっていて、スタックまたはグローバル変数に格納されている、成長不能なハッシュマップを作成したいとします。これの主な使用例は、RAMが32kを超えるマイクロコントローラのハッシュマップです。

理論的にも可能ですか？私はある程度の充実感で、衝突が多すぎる可能性があることを知っています。しかし、あなたがそれほど多くない場合、私はまだそれが価値があると思います。

Answer 1

私はなぜそれができないのか分かりません。キーがすべて事前にわかっている場合、理論的にはハッシュテーブルサイズのオーバーヘッドを排除して完全なハッシュを見つけることができます。

キーは動的ですが、ヒープ割り当てを避けたい場合は、既存のメモリを使用するオープンアドレス方式を使用します。ハッシュテーブルの値の数を明示的に追跡し、新しい挿入が十分に満たされたらそれを拒否したいとします（たとえば、パフォーマンスがあまりにも悪くならないように80％がおそらく最大値です）。