hash - ハッシュ値を予約する

Question

特定のキーに対して 32 ビットのハッシュ値を作成する既存の (C++) ハッシュ関数を使用する必要があります。関数は非常に複雑です。

ここで、1 つの値を予約する必要があります。つまり、ハッシュ関数がこの値を出力しないようにする必要があります。

既存のハッシュ関数の複雑なロジックを理解/変更せずに安全に行う方法はありますか?

どうもありがとう...

Answer 1

決してゼロを返さないハッシュ関数が必要な場合の最も簡単な方法:

int result;

hash = compute_hash_one_way();  // Hopefully it's not zero
if (hash) return hash;          // In which case we return it
hash = compute_hash_another_way(); // Try something else
if (hash) return hash;             // If that was good, return that
return 8675309; // We know THAT's not zero

2 番目のハッシュ計算は特別なものである必要はありません。基本的に、入力に多少依存するゼロ以外の値が利用可能な場合、定数を返すよりもそれを使用することもできますが、本当に厄介な高速ハッシュ関数を使用する方がよいでしょう (または元のハッシュがゼロを返した場合は常に定数を返すだけです) 2 番目のハッシュの計算に非常に多くの時間を費やして、外部コードが元のハッシュがゼロであると推測する可能性があります。元のハッシュが良好な場合、元のハッシュがゼロを返したときに定数を返しても、その定数は 40 億分の 1 ではなく、20 億分の 1 の入力に対してのみ返されることに注意してください。

[ちなみに、私が GetHashCode または hashcode の仕様を .NET/Java で書いていたとしたら、優れたハッシュ関数が本質的に瞬時にゼロを返すことができるのであれば、0 だけを返すよう強く推奨したでしょう。たとえば、ゼロを返さないために必要な余分な時間Integer.GetHashCode()は、ほとんどの場合GetHashCode、値ゼロで冗長に呼び出すのに費やされる可能性のある時間を超えますが、ゼロを返す文字列ハッシュのようなものは、場合によってはパフォーマンスに大きな影響を与える可能性があります。]

Answer 2

「オプションの」キーが必要なようです。あなたはそうするでしょう

hash = hash_combine(has_value()? 1 : 0, has_value()? hash(value()) : 0);

または、主張する場合は、ビット数を 31 に減らすことができます

compromised_hash = SHIFT_RIGHT(raw_hash) ^ raw_hash; // just an example.

これで、MSB は常に空になります。そうでない場合: あなたは特別なマーカーを持っています。これを作成して、ハッシュ ドメインを 1 要素だけ削減するのは簡単ではありません (ハッシュ raw 関数を変更できない場合)。