问题标签 [hash-collision]

我想测试第 3 方（包括“闭源”）工具（如同步、重复数据删除......）在存在具有相同大小和摘要校验和的文件（流行的 CRC32、MD5、SHA-1 .. 。 ETC）。其中一些散列方法具有已知的漏洞，因此存在产生冲突的方法。

您是否知道此类数据集的来源（除了蛮力尝试创建一些:)）或用于创建此类数据集的生成器吗？

为了明确这一点：我对具有相同校验和、文件大小但内容不同的文件集感兴趣！

代码：

现在，根据我的理解，由于两种情况下的键值put相同，即a必然会发生冲突，因此会发生链接。[如果我错了，请纠正我]。

现在，如果我想检索映射到键值的所有值的列表，a我该如何获取它？

现在只有我的println版画v。

我正在用 C++ 实现一个 Hashtable 类。我使用的冲突解决方法是带有延迟删除的线性探测。我已经看到了这个的实现，但对插入方法有疑问。哈希表的每个单元格都有一个状态（活动、已删除、空）。由于某些原因，我在插入新元素时看到了实现中的某些原因，它们对键进行哈希处理，然后探测表，直到找到 EMPTY 单元格（或直到找到已经包含相同键的单元格）。

示例代码：

我的问题是：是否有理由不停止并插入已标记为已删除的单元格？换句话说，在findPos方法中，为什么不将 while 语句更改为，while(data[currentPos].state==ACTIVE && data[currentPos].key!=key)以便当我们找到带有键的单元格或第一个删除/空单元格时循环结束。然后在插入中，测试单元格的状态。如果 active 条目已经存在，则返回 false；否则插入元素。

我正在通过 Java 对哈希表的 put 方法的实现，并遇到了这个：

虽然我知道检查冲突需要一个键，但为什么 Java 会存储键的哈希值并检查它？

我对哈希概念有一些理解问题，如下所示：

假设，我已经实现了将键作为数字的哈希表（一维数组，比如A[100] ）。我有一个简单的哈希函数H(Key) % Table_Size，它将目标索引返回到哈希表中（同时访问与此特定键关联的值）。

假设，我想将0（键）存储到表中。当我将此键传递给H（哈希函数）时，它会返回随机索引，例如 25。

数组 A 中的这个位置有 2 种可能性（索引为 25）：

1. A[25] 包含除0以外的一些键，已存储（以前）
2. A[25] 包含0

第一种可能性有冲突并且很容易识别（因为当前密钥：0 和已存储的密钥：k 不同），所以第一个没有问题。

但是，对于第二个，我怎么知道天气是否有碰撞？

据我所知，哈希表或数组将是主内存的一部分。假设 A[25] 存储在内存位置 500 中。

我怎么知道这个位置（500）实际上是空的还是已经被其他键填充了？

存储单元的什么状态或值代表EMPTY或NULL或UNUSED位置？

而且，如果我想将0作为密钥存储到此位置进行碰撞检查怎么办？

我目前假设如果任何内存位置是EMPTY或NULL或UNUSED，那么它将处于 RESET 状态（所有单元格都是 0）。这是真的 ？

这可能是个愚蠢的问题，但我想知道在这种情况下如何检查碰撞。

--

提前致谢！！（海得拉巴海泰因）

当使用 adler32() 作为散列函数时，应该会遇到罕见的冲突。

我们可以对碰撞概率进行精确的数学运算，但粗略地说，由于它是一个 32 位的散列函数，因此 在数千个项目的样本集上
不应该有很多碰撞。

几乎不是这种情况。

这是一个示例：让我们使用中间包含日期的字符串，例如

其中日期的格式为 yyyy-mm-dd，并在 2012 年循环。

这个例子中有 91 次碰撞！

更糟糕的是：有 7 个案例发生了 3 个日期冲突。

这么常用的hash函数怎么表现这么差？
还是我错过了什么？

以下是上述示例的详细结果：

我想为给定的字符串创建一个唯一的哈希，我想知道 md5 和 sha1 的重复哈希是否存在差异。

为了论证起见，让我们假设以下代码：

sha1 和 md5 之间发生这种情况的概率是否存在差异？另外：如果我使用重叠很大的字符串（“blabla1”、“blabla2”），有区别吗？

顺便提一句。我对算法的安全性不感兴趣，我只想创建一个尽可能唯一的哈希。

GUID's在（128 位）或GUID's（160 位）的 SHA1 散列之间是否有更多发生冲突的机会？我的观点是 a 的机会更少GUID（即使少了 32 位），因为它有一些特殊的机制来确保它（几乎，因为不能保证）是唯一的（例如：时间戳）

注意：我已经知道 aGUID不太可能与另一个发生冲突GUID，请不要再讨论这个问题。

如果 B 是 const 且 C 是变量，如何找到 A？（如果没有解决方案可以更改C）

A 是双字，B 是双字，C 是字节！= 0

Edit1：在 GalacticJello 的回答之后，我有另一个问题：有没有办法在没有循环的情况下做到这一点（简化表达式）？

为什么我需要这个：我正在尝试为

目前我有一个生成随机 C 然后搜索 A 的循环。（我使用生成随机值 [for A] 的循环搜索 A 并检查上述表达式是否为真）

Edit2：这是我当前用于搜索冲突的代码，我现在正在测试..

我正在为一个项目实现一个哈希表，使用 3 种不同类型的探测。现在我正在研究线性。

对于线性探测，我了解探测的工作原理，我的导师暗示他希望步长为 1。问题是，不允许重复。所以我必须在插入之前“搜索”一个值，对吗？但是，如果表格被使用到所有单元格都被“占用”或“删除”怎么办？然后为了搜索特定键以确保它不在表中，我将不得不搜索整个表。这意味着搜索操作（以及扩展的插入操作）是 O(n)。

这似乎不对，我想我误解了一些东西。

我知道我不必在二次探测中遇到同样的问题，因为表格需要至少有一半是空的，并且它只会探测确定数量的元素。对于双重哈希，我不确定这将如何工作，因为我还需要搜索表以证明要插入的密钥不存在。但是，如果没有一个单元格“从未被占用”，我怎么知道如何停止搜索？

所以：在开放散列中，表中的每个条目过去都已被占用，是否需要 O(n) 探针来搜索元素（如果不允许重复则插入）？