问题标签 [hash-collision]

使用我的 web 应用程序，我将具有哈希生成文件名的缓存文件存储在各种子目录中，以优化性能水平。我知道我可以提高性能的一种方法是确保生成的名称遵循 8.3 文件名结构，这样 NTFS 就不必生成短文件名（我无法在注册表中设置它）。

为了做到这一点，尽管我必须将哈希（我在想 SHA1）修剪为 8 个字符，但显然这会大大增加冲突的可能性。我想知道碰撞的概率是多少？

我在这里看到了关于完整 SHA1 哈希冲突率的答案，但我的数学很糟糕，所以计算这个值远远超出了我的范围。

据此，在哈希表中搜索的时间复杂度为 O(1)。

但是，如果发生碰撞，那么显然这应该是 O(1) + 一些东西。

我的问题是：

当你说

从散列表中，散列函数应用于 someKey，并直接从该位置检索数据。

但是想象一下分离链接用于冲突解决。并想象 someKey 和 someOtherKey 在我们的散列函数应用于它们之后具有相同的输出。假设它是值“25”。

所以当我说

我将从位置“25”获取数据。这使它成为 O(1)。伟大的。

然而当我说

现在someOtherKey链接到someKey所在的位置。

当对someOtherKey应用散列时，我得到 25。

我如何获得我需要的价值？内部是什么？还有别的表吗？算法流程如何？是否有其他表用于存储所有碰撞？

谢谢你。我希望我的问题很清楚！

此代码块读取字典文件并将其存储在散列数组中。这个散列数组使用链表冲突解决。但是，由于某种难以理解的原因，阅读在中间停止了。（我假设在创建链表时会出现一些问题。）当数据存储在空的散列数组元素中时，一切正常。

createList并且addNode都是ADT功能。前者以函数指针（compare是我在函数内部构建的main函数）作为参数，后者以列表名称和 void 类型数据作为参数。compare排序链表。请找出我的问题。

我有一个代码，它使用循环多项式滚动哈希 (Buzhash) 来计算 n-gram 源代码的哈希值。如果我使用小的散列值（7-8 位），那么会有一些冲突，即不同的 n-gram 映射到相同的散列值。如果我将哈希值中的位增加到 31，那么就有 0 次冲突 - 所有 ngram 都映射到不同的哈希值。

我想知道为什么会这样？冲突是否取决于文本中 n-gram 的数量或 n-gram 可以具有的不同字符的数量，还是 n-gram 的大小？

在散列 n-gram（使用滚动散列）时如何选择散列值的位数？

相关链接：http ://en.wikipedia.org/wiki/Hopscotch_hashing

Hopscotch 哈希表看起来很棒，但我在文献中没有找到这个问题的答案：如果我的邻域大小为 N 并且（由于渎职或非常倒霉）我插入 N+1 个元素，所有这些元素都散列到相同的确切值？

我需要一个加密安全的散列函数，它具有与 MD5 相似的属性，即：128 位大小和速度快。由于 MD5 本身现在已经很糟糕了，我想使用另一个哈希。这些天，SHA1 实际上比 MD5 快，至少在我的计算机上（试试openssl speed md5 sha1你的），所以我想我可以从 SHA1 输出中取出前 128 位并完成。但是，我不确定安全和碰撞的影响。

1. 这样的散列函数是否比真正的 128 位散列函数更不安全？
2. 这样的散列函数是否比真正的 128 位散列函数更容易发生冲突？

_{ps 也欢迎关于良好快速 128 位哈希替代方案的替代建议，即使它们有点超出原始问题的范围。}

我正在开发一款游戏，其中游戏世界中的每一件事都由一个全球唯一标识符表示。

这些 id 每个都为 64 位，是通过将创建时间、机器网络地址和随机数哈希在一起生成的。根据维基百科关于生日问题的文章，两亿条记录的哈希冲突概率为 0.1%。

由于我不太可能获得那么多记录，因此可以认为没有哈希值会发生冲突。但我不希望这样，而是让我的应用程序处理罕见的 id 冲突情况，从而处理哈希冲突。

否则，这种行为将是非常不受欢迎的，因为游戏世界中两个独立的事物会产生联系，从而共享它们的属性，如位置、运动、健康点等。

如何处理哈希冲突？它们通常如何处理？

我需要通过散列一些数据来生成全局唯一 ID。

一方面，我可以使用时间戳和网络地址的组合，这是独一无二的，因为每台计算机只能同时创建一个 id。但由于这些数据太长，我需要对其进行哈希处理，因此可能会发生冲突。（附带说明一下，如果时间戳不够准确，我们也可以输入一个随机数。）

另一方面，我可以只使用一个随机数并对其进行哈希处理。这不应该带来与第一种方法完全相同的哈希冲突概率吗？有趣的是，这种方法会更快并且更容易实现。

使用唯一数据而不是随机数据时，在哈希冲突方面是否存在差异？（顺便说一句，我不会使用标准描述的真实 GUID，但我的只会是 64 位长。但这不应该影响问题。）

问题

我有一个文本文件，其中每行包含一个字符串（换行符 \r\n）。该文件使用 CRC16 以两种不同的方式进行保护。

1. 4096 字节块的 CRC16
2. 32768字节块的CRC16

现在我必须修改这些 4096 字节块中的任何一个，所以它（块）

• 包含特定字符串
• 不改变文本文件的大小
• 具有与原始块相同的 CRC 值（对于包含此 4k 块的 32k 块相同）

除了这些限制之外，只要文件本身不破坏其格式，我就可以对块进行填充所需的任何修改。我认为最好使用任何完全填充的 4k 块，而不是最后一个块，因为它可能真的很短。

问题

我应该如何开始解决这个问题？我想的第一件事是某种蛮力，但不是需要很长时间才能找到导致两个 CRC 值保持不变的变化吗？可能有一种数学方法可以解决这个问题吗？

它应该在几秒钟或最多时间内完成。一会儿。

我现在知道有一天内置实用程序可用，例如 Apache commons lang 的 HashCodeBuilder，但我试图了解如何自己实现它，并在http://en.wikipedia.org/wiki/Java_hashCode遇到了 Employee 类的 hascode 函数示例()

在谷歌的任何地方，都建议使用相同的技术，例如将非零值与奇数素数相乘，然后将其与实例变量相加（对实例变量执行此操作）。

问题：-

1）为什么我们不能将employeeId作为hascode返回，因为它会是独一无二的。它简单并且服务于hascode目的。同意，如果它不是唯一的，我们可能需要这种技术。那正确吗？

2）即使员工ID不是唯一的，为什么建议乘以奇数素数？为什么取任何该死的整数都不被认为是好的？

更新：-

彼得我运行了你提到它打印的例子

[0、32、64、96、128、160、192、224、288、256、352、320、384]

[0、32、64、96、128、160、192、224、288、256、352、320、384]

我假设现在的输出正如你所期望的那样理解你在回答中提到的概念

[373、343、305、275、239、205、171、137、102、68、34、0]

[0、34、68、102、137、171、205、239、275、305、343、373]

正如您在评论中所建议的那样，此示例表明即使是唯一的哈希码也可以最终出现在同一个存储桶中。这个例子是如何证明这种行为的？你的意思是整数 373 和整数 0 最终在同一个桶中吗？

在这个例子中质数有什么帮助，而 34 又如何没有帮助？