我想使用单向散列算法(无冲突)将 32 位整数转换为 36 位整数。
任何人都可以解释如何做到这一点？
最佳答案
“单向”意味着，“很难”弄清楚 x 确实给出了哈希结果 h(x)。由于术语“硬”没有明确定义，因此也没有明确定义什么是单向函数。
“无碰撞”意味着，对于每对 x 和 y，h(x) 与 h(y) 不同，其中 x 与 y 不同。这是一个尖锐的定义，但很难证明 h(x) 是否真的是单向函数。您必须比较每对两个 32 位数字的哈希结果并测试它们是否不同。
最好的方法是计算所有可能的 h(x) 并将它们与它们的 x 一起存储在一个数组中。然后按 h(x) 对数组进行排序，然后遍历此列表并测试两个邻居是否具有相同的 h(x)。如果你没有找到相同的邻居，你的哈希函数就没有冲突。
但是: 如果你真的能做到这一点，你的函数就不能真的是一个单向函数，因为你刚刚生成的证明无碰撞的列表是一个非常快速的查找表，它可以让你找到 x log(n) 的搜索时间中的每个 h(x)。这甚至可能比从 x 计算 h(x) 更快。
所以让我们弄清楚，这需要多长时间
32 位整数是 0 到 4294967295 之间的数字。假设从 x 计算 h(x) 需要 0.1 毫秒。根据散列算法，即使在便宜的笔记本上也是现实的。所以在 1 秒内你会得到 10,000 个散列数字，而在一天内你会得到 864,000,000 个数字。计算所有可能的数字并将它们存储在光盘上只需要 5 天时间。
每个条目有 4 个字节的 32 位数字和 5 个字节的 36 位哈希。使 9 字节。所以完整的表有 38,654,705,664 个字节。这是 38 GB。您可以将其存储在每个低预算的笔记本上。对这张表进行排序需要几分钟，这不计入我们计算所需的 5 天。
因此，在二手 200 美元笔记本电脑上构建这张 table 绝对没有问题。一旦你有了它，就很容易证明它是否真的没有碰撞，但是通过构建这个表，你也证明了它不是一个单向函数!
那么最好的解决方案是什么？
在第 1 步之后，列表将包含 6.25% 的碰撞(大约 2.684 亿次碰撞)。在每次迭代中，您将碰撞次数减少到第 16 部分。大约需要 8 次迭代才能消除所有冲突。
这个 38 GB 的表现在是你超快的绝对无冲突的哈希函数。它与任何 32 位到 36 位哈希函数一样是单向的。含义:对于给定的 h(x)，不可能有其他无碰撞的哈希函数更难找到 x。
关于algorithm - 将 32 位整数转换为 36 位整数的单向哈希(无冲突)？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11624940/