4

我很好奇是否有一些简单和/或众所周知的哈希方法具有以下属性：

  1. 它将一个 32 位 int 转换为另一个 32 位 int
  2. 没有两个不相等的输入产生相同的输出
  3. 从输出来看，两个输入相似（在差异和位掩码方面）不应该立即显而易见，这意味着 hash(a) 和 hash(a+1) 应该有很大不同的输出，hash(a ) 和散列(a & 0x100000)。（这排除了简单地与随机值进行异或运算。）

虽然这样的系统显然在理论上必须存在，但在实践中是否存在？

4

5 回答 5

5

实践中有很多！

一个简单的解决方案是将输入乘以任何奇数，并取结果的底部 32 位。那是：

y = (x * YOUR_ODD_NUMBER) & 0xffffffff;

不过，这确实有一些弱点。它总是将零映射到零，如果您选择像 3 这样的小数字，那么映射将相当明显（类似地，如果您选择像 0xffffffff 这样的大数字，您将得到另一个明显的映射），并且最低有效位不会改变. 通常低位可以影响高位，但高位不能影响低位。

另一种方法是多次异或具有自身移位版本的数字：

x ^= x >> YOUR_FIRST_SHIFT;
x ^= x << YOUR_SECOND_SHIFT;
y = x ^ (x >> YOUR_THIRD_SHIFT);

您可以尽可能多地堆叠这些琐碎的操作，以试图隐藏各个阶段的弱点。即使一个操作本身不是很好，它也可以在更复杂的操作链中做出有用的贡献。例如，具有某个常数的异或将避免仅通过乘法将零映射到零的问题，并且移位和异或技术允许低位受到高位的影响。

如果您查看PRNG，您会发现其中很多的句点与它们的状态几乎相同。他们通过按照您指定的方式排列他们的状态来实现这一点——通过一个状态与下一个状态之间的关系不太明显的 1:1 映射——然后他们呈现该状态的一部分（或全部）作为一个伪随机数。一些 PRNG 和散列也以回火阶段结束，在那里他们执行这些映射中的另一个以隐藏他们自己的一些弱点。

如果你在一个循环中运行你的哈希函数，在每次迭代中将 y 反馈给 x，那么你就有了一个 PRNG，你可以使用dieharder之类的工具来测试它的随机性。

并非所有 PRNG 都具有理想的长周期属性，并且该属性对于良好的哈希函数不是必需的，但一些 PRNG 算法可以成为执行操作的有用思想来源，并且它们具有全面的分析。

于 2013-05-25T00:26:12.573 回答
3

尝试反转数字的二进制表示：

17(10) = 1110(2) -> 10111(reversed, set first bit as indicator) = 23
18(10) = 10010(2) -> 101001 = 41

或将前半部分与后半部分互换：

17(10) = 11|10(2) -> 1011 = 11
18(10) = 100|10(2) -> 10100 = 20

我不确定，但它似乎对你有用。

于 2013-05-06T12:47:21.653 回答
2

一个简单的解决方案是制作一个位顺序更改数组。一些加密功能基于这种方法。

uint8_t arr[32]={4,7,24,9,15,3,...}; // an order you know
uint32_t orgVal;
uint32_t modVal =0;
uint32_t pos = 1;

for (int i=0; i<32;i++) {
  modVal += (orgVal&pos)? (1>>arr[i]):0;
  pos*=2;
}

（代码是从头开始制作的，没有 IDE 或测试；它可能无法正常工作）

正如评论中所指出的，如果您查看这些位，差异将是最小的：0 和 1 的数量将是相同的。要解决此问题，您可以考虑同时使用 bit order change 和 xor。那么原始值和结果值之间的差异将更加显着。

于 2013-05-06T12:43:19.183 回答
0

一个简单的方法：hash(x) = rotate-shl(x, K1) xor C

您可以结合几个简单的操作来获得更“随机”的结果，例如rotate-shl/shr、bit-reverse、xor等not。

于 2013-05-06T15:25:49.760 回答
0

这个很简单，但可能效率不高：

  • 随机排列所有 32 位整数。
  • 保存（相当大的）表。

现在你可以用两种方式应用它，只有有表的人才能知道数字应该是多少。

于 2013-05-06T13:23:59.610 回答