问题标签 [hash-collision]

对于我们的每个二进制资产，我们生成一个 MD5 哈希。这用于检查某个二进制资产是否已经在我们的应用程序中。但是两种不同的二进制资产是否有可能生成相同的 MD5 哈希。那么两个不同的字符串是否有可能生成相同的 MD5 哈希？

我有一部分存储文件的应用程序。因为我们可能会添加许多相同的文件，所以我首先保留每个文件的哈希值。如果两个文件具有相同的哈希值，那么我们会丢弃一个，并且对该文件的两个“引用”都指向同一个物理文件。

1. 我应该担心多少哈希冲突？

2. 如果发生碰撞我该怎么办？到目前为止，我的代码的全部症结取决于没有两个具有相同哈希的不同文件。如果现在发生冲突，我的应用程序会抛出一个合法的不同文件并指向具有相同哈希的文件。

3. 我应该使用 MD5 以外的东西吗？SHA-1 是否有更好的碰撞率？

最多可以将 MD5 用作哈希而不担心发生冲突的可能性的字符串长度是多少？

这可能是通过为特定字符集中的每个可能的字符串生成一个 MD5 散列来计算的，长度增加，直到散列第二次出现（冲突）。没有冲突的字符串的最大可能长度将比冲突对中最长的字符少一个字符。

这是否已经针对 MD5、SHA1 等进行了测试？

如果在放入 HashMap 期间发生冲突，是调整地图大小还是将条目添加到该特定存储桶中的列表中？

我有一个需要为表格键入的自定义对象的问题。我需要生成一个唯一的数字键。我遇到了碰撞问题，我想知道是否可以利用字典来帮助我。假设我有一个这样的对象：

等等更多的领域。假设 Foo 和 Bar 是我的关键字段 - 如果它们在两个 Thingys 之间相等，那么这两个对象应该被认为是相等的（一个可能代表另一个对象的更新，而 Others 字段正在更新。）所以我有这些：

所以这在大多数情况下都有效，但在极少数情况下，实际上不同的两个 Thingy 具有相同的哈希码。

我的问题是：我可以使用 Dictionary <Thingy, int> 放入我的 Thingys 的位置，并使用从字典中出来的顺序值作为我的实际键吗？我想知道字典在检测到罕见的哈希码冲突时是否会调用我的 Equals 方法，确定对象实际上是不同的，并以不同的方式存储它们。然后我在查找它时进行成像，它会看到一个用于该哈希的存储桶并搜索正确的东西，再次使用 Equals 进行比较。

字典是这种情况，还是仅解决哈希码不同但（哈希％大小）相同的冲突？如果这行不通，有什么可能？

我已经阅读了很多关于 Hash Tables 以及如何在 C 中实现 on 的内容，我想我几乎已经掌握了所有概念，因此我可以开始编写自己的代码，我只是有几个问题尚未解决正确理解。

作为参考，我一直在阅读： http ://eternallyconfuzzled.com/jsw_home.aspx

1)正如我在上面的网站上所读到的，建议哈希表大小使用 2 或素数的幂。这基本上是一个数组，并且数组具有固定大小，因此我可以快速查找我正在寻找的值。如果我有一个大输入，我不能声明一个小数组，因为它不适合，如果我的输入数据不是那么大，我不能声明一个非常大的数组，因为它浪费了内存。

哈希表的最佳大小是多少？我应该根据什么做出决定？

2）另外，在那个网站上，有几个我还没有读完的散列函数。它还指出，最好使用一个众所周知的算法并自己动手。我可能会这样做，我将从该站点中选择一个并在我的代码上对其进行测试，看看它是否根据我的输入数据最大限度地减少了冲突。

困扰我的是我如何控制哈希范围？哈希不能返回大于哈希表大小的整数，否则我们将遇到严重问题。我该如何处理？

我当前的哈希表实现是使用线性探测，现在我想转向二次探测（后来也转向链接，也许还有双重哈希）。我已经阅读了一些文章、教程、维基百科等……但我仍然不知道我应该做什么。

基本上，线性探测的步长为 1，这很容易做到。在哈希表中搜索、插入或删除元素时，我需要计算一个哈希值，为此我这样做：

然后，在搜索、插入或删除时，我循环遍历表，直到找到一个空闲的存储桶，如下所示：

至于二次探测，我认为我需要做的是改变“索引”步长的计算方式，但这就是我不明白我应该怎么做的。我见过各种各样的代码，它们都有些不同。

此外，我还看到了一些二次探测的实现，其中散列函数被更改以适应它（但不是全部）。是否真的需要这种更改，或者我可以避免修改散列函数并仍然使用二次探测？

编辑： 阅读下面 Eli Bendersky 指出的所有内容后，我想我明白了。这是http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_hashtable.aspx的部分代码：

有两件事我没有得到......他们说二次探测通常使用c(i)=i^2. 然而，在上面的代码中，它做的更像是c(i)=(i^2-i)/2

我已准备好在我的代码上实现这一点，但我只会这样做：

...并不是：

如果有的话，我会这样做：

...因为我已经看到其他代码示例跳水了两个。虽然不明白为什么...

1）为什么要减去步骤？
2）为什么它会跳水2？

我正在散列大量文件，为了避免散列冲突，我还存储了文件的原始大小 - 这样，即使存在散列冲突，文件大小也不太可能相同。这是声音（哈希冲突同样可能是任何大小），还是我需要另一条信息（如果冲突更有可能与原始信息的长度相同）。

或者，更一般地说：无论原始文件大小如何，每个文件是否都可能产生特定的哈希？

现在我的哈希表计算插入到哈希表中的每个元素的数量。我使用这个计数和总哈希表大小来计算负载因子，当它达到 70% 时，我重新哈希它。

我在想也许我应该只计算插入的元素填充一个空插槽而不是所有它们。因为我使用的碰撞方法是单独的链接。因子负载不断增加，但如果可能存在一些冲突，则会在哈希表上留下大量空槽。

你可能在想，如果我有那么多冲突，也许我没有使用最好的散列方法。但这不是重点，我正在使用一种已知的散列算法，我在我的样本数据上测试了其中的 3 个，并选择了产生较少冲突的那个。

我的问题仍然存在。我应该继续计算插入的每个元素，还是只计算填充哈希表中空槽的元素？

我正在寻找 C 中的哈希表实现，它将其对象存储在（二维）数组而不是链表中。即如果发生碰撞，导致碰撞的对象将存储在下一个空闲行索引中，而不是推到链表的头部和第一个元素。

另外，对象本身必须被复制到哈希表中，而不是被指针引用。（对象不会在程序的整个生命周期中存在，但表会存在）。

我知道这样的实现可能有严重的效率缺陷，并且不是“标准的散列方式”，但是当我在一个非常特殊的系统架构上工作时，我需要这些特性。

谢谢