问哈希值什么时候会冲突？

EN

如果要散列的项目比插槽多，那么就会发生散列冲突。但是如果你有一个糟糕的散列算法，那么即使当项目/插槽比率非常小的时候，你也会看到冲突。一个好的散列算法(包括您将在野外看到的大多数散列算法)将尝试将产生的散列尽可能均匀地分布在整个输出空间中，从而最大限度地减少冲突。

请注意，哈希冲突并不是世界末日。例如，当在哈希表中使用时，它只是意味着一个插槽中存储了多个项，并且表代码将不得不更多地遍历以查找或添加目标项，从而略微增加了查找时间。

你会看到人们将MD5称为一种“坏掉的”哈希算法，而实际上，它只是一种糟糕的密码哈希算法。它会比你自己做的要好。

散列函数的目的是随机地将项分配到容器中。对于任何好的散列函数，哪个容器是哪个容器并不“重要”，因为它们必须是不可区分的。

这不适用于“完美散列”实现，它试图比随机分布做得更好-不像你提到的算法。

正如Michael提到的，碰撞发生在项目和插槽一样多之前很久。如果您想要处理birthday paradox，则必须具有优雅的冲突处理(或完美的散列)。

我认为使用哈希函数的应用程序是一个重要的区别。例如，散列容器中频繁的冲突可能会降低性能。密码学中频繁的冲突将产生更具破坏性的后果(参见：cryptographic hash function on Wikipedia)。

即使使用“像样的”散列算法，冲突也相对容易发生。例如，在Java中，

String s = new String(new char[size]);

始终哈希为0。也就是说，在Java语言中，所有只包含\0的字符串都散列为0。

至于“是哪个容器有关系吗？”，这又取决于应用程序。您可以设计散列函数，将“相似”的对象散列到附近的值。例如，当您想要搜索相似的对象时，这是很有用的。只需将它们全部散列，看看它们会落在哪里。在这种情况下，碰撞或接近碰撞是理想的，因为它将相似的对象分组。

在其他应用程序中，您甚至希望对象中最轻微的更改都会导致完全不同的哈希值。例如，在密码学中就是这种情况，您希望尽可能确定某些内容没有被修改。在这种情况下，很难找到散列为相同值的不同对象。