c# - 既知の最大アイテム数と固定キーサイズを持つ効率的な固定サイズの「非可逆」ハッシュテーブル

Question

キーとして常に 128 ビットの整数を持ち、要素の最大数があるという事実を考えると、完全なハッシュ関数を作成することは可能ですか?

GUID をキーとして保存したいのですが、固定サイズでリンク リストのないソリューションが必要です。つまり、衝突が発生すると、2 番目の要素が失われます。

誰かがこれを行うハッシュ関数を推奨できますか?

Answer 1

キーとして常に128ビット整数を使用し、要素の数が最大であるという事実を考えると、完全なハッシュ関数を作成することは可能ですか？

キーのエントロピー（変数に含まれる情報の期待値）がハッシュの結果が対応できるものよりも大きい場合、答えはノーです。キーのエントロピーがハッシュの結果に対応できるエントロピー以下の場合、答えは「はい」です。

つまり、たとえばハッシュ関数が16ビットの結果（65536の可能な値）を生成し、128キー変数が最大65536以下の異なる値を想定できる場合（したがって、128ビットキーのエントロピーは最大10です） -ビット）そのようなハッシュ関数が存在するよりも。一方、キーが65535を超える個別の値を想定できる場合、それを65535以下のバケットにハッシュする方法はありません。

誰かがこれを行うハッシュ関数を推奨できますか？

キーのエントロピーが非常に低いために実行できることを知っていたとしても、キーが想定できる可能な値がわからないと、それを実行できるハッシュ関数を誰も提供できません。