hash - 保留哈希值

Question

我需要使用现有的（C++）散列函数，它为给定的键创建 32 位散列值。功能极其复杂。

现在我需要保留一个值，即散列函数永远不会输出这个值。

在不理解/更改现有哈希函数的复杂逻辑的情况下，是否有一种安全的方法？

非常感谢...

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

第二个哈希计算不需要什么花哨的东西；基本上，如果一个人有任何可用的非零值，有点取决于输入，那么最好使用它而不是返回一个常数，但使用一个非常糟糕的快速散列函数可能会更好（甚至如果原始值返回零，则总是返回一个常量）而不是花费大量时间计算第二个哈希值，以至于外部代码可能会推断出原始哈希值为零。请注意，如果原始散列是好的，即使在原始散列返回零时返回一个常数，也只会导致该常数返回 20 亿分之一的输入，而不是 40 亿分之一的输入。

[顺便说一句，如果我在 .NET/Java 中编写了 GetHashCode 或 hashcode 的规范，我强烈建议一个好的散列函数应该只返回零，前提是它基本上可以立即返回零。在大多数情况下，例如从不返回零所需的额外时间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 个元素的哈希域（除非您可以更改哈希原始函数）