algorithm - 完美哈希构建

Question

我们为什么不使用 SHA-1、md5Sum 和其他标准加密哈希值进行哈希处理。它们足够聪明，可以避免碰撞，而且不可恢复。所以与其想出一组新的哈希函数，它可能会发生冲突，我们为什么不使用它们。我能想到的唯一原因是他们需要说大密钥，比如 32 位。但仍然避免冲突，所以查找肯定是 O(1)。

Answer 1

1. 因为它们非常慢，有两个原因：
   1. 它们的目标是在密码学上是安全的，而不仅仅是一般的防碰撞
   2. 它们产生的哈希值比您在哈希表中实际需要的值大得多
2. 因为它们处理非结构化数据（八位字节/字节流），但您需要散列的对象通常是结构化的，并且首先需要线性化

Answer 2

我们为什么不使用 SHA-1、md5Sum 和其他标准加密哈希值进行哈希处理。他们足够聪明，可以避免碰撞......

错了，因为：

• 两个输入 cam 仍然碰巧具有相同的哈希值。假设散列值是 32 位，一个出色的通用散列例程（即不利用对一组实际键的洞察力）仍然有至少 1/2^32 的机会为任何 2 返回相同的散列值键，然后 2/2^32 与其中一个发生碰撞的机会，因为第三个键被散列，3/2^32 与第四个等发生冲突。
• 拥有不同的哈希值与将哈希值映射到哈希表中的不同哈希桶是完全不同的事情。散列值通常被修改为表大小以选择一个桶，所以充其量 - 并且再次用于通用散列 - 将元素添加到散列表时发生冲突的机会是#preexisting-elements / table-size。

所以与其想出一组新的哈希函数，它可能会发生冲突，我们为什么不使用它们。

因为在选择使用哈希表而不是二叉树时，速度通常是程序员的目标。如果哈希值在数学上计算起来很复杂，那么它们可能比使用更容易（但仍然不是特别）容易发生冲突但计算速度更快的哈希函数花费更长的时间。也就是说，有时在哈希上付出更多的努力可以获得回报——例如，当哈希表存在于磁盘上时，查找和读取记录的 I/O 成本使哈希计算工作相形见绌。

antti 对数据也提出了一个有趣的观点......通用哈希例程通常处理具有特定起始地址和字节数的二进制数据块（它们甚至可能要求字节数是 2 或 4 的倍数） . 在许多应用程序中，需要散列的数据将与不得包含在散列中的数据混合在一起 - 例如缓存值、文件句柄、指向其他数据或虚拟调度表的指针/引用等。一个常见的解决方案是单独散列所需字段并组合散列键 - 可能使用异或。由于可能有一些位字段应该在与其他不应该被散列的数据相同的内存字节中进行散列，因此您有时需要自定义代码来提取这些值。尽管如此，即使事先需要一些复制和填充，

我能想到的唯一原因是他们需要说大密钥，比如 32 位。

在所有其他条件相同的情况下，密钥越大越好，但如果哈希函数在数学上是理想的，那么它的任何 N 个位 - 其中 2^N >= # 个哈希桶 - 将产生最小的冲突。

但仍然避免碰撞，所以查找肯定是 O(1)。

再次，如上所述的错误。

（顺便说一句......我在上面的几个地方强调了通用性。那只是因为在一些微不足道的情况下，您可能对需要散列的键有一些了解，这使您可以将它们完美地定位在可用的散列桶中. 例如，如果您知道键是数字 1000、2000、3000 等直到 100000，并且您至少有 100 个哈希桶，您可以简单地将哈希函数定义为 x/1000，并且知道您将拥有完美的散列无冲突。知道所有键映射到不同的散列表桶的这种情况被称为“完美散列” - 根据您的问题标题 - 像 md5 这样的良好通用散列不是完美散列，实际上它使在不知道完整的可能键集的情况下谈论完美散列是没有意义的）。