问题标签 [hash-collision]

我正在做一个项目，我需要将数据从我们的系统同步到外部系统。我想要实现的是定期从自定义查询中仅发送更改的项目（行）。这个查询看起来像这样（但有更多的列）：

我想避免在同步之间必须一对一地比较每个字段。我的想法是，我可以为查询中的每一行生成一个散列，并将其与上一次同步的散列进行比较，这将只返回更改的行。我知道CHECKSUM函数，但它很容易发生冲突，有时可能会错过更改。但是我喜欢我可以制作一个临时表并使用的方式CHECKSUM(*)，这使得维护更容易（不必在查询和 CHECKSUM 中添加字段）：

我知道HASHBYTES函数（它支持 sha1、md5，它们不太容易发生冲突），但它只接受 varchar 或 varbinary，而不接受列列表或 * CHECKSUM 的方式。必须从查询中转换/转换每一列是一个痛苦......并且打开了错误的大门（例如忘记包含一个新字段）

我还注意到SQL Server 的变更数据捕获和变更跟踪功能，但对于我正在做的事情来说，它们似乎都很复杂和矫枉过正。

所以我的问题：是否有其他方法可以从满足我的条件的查询或临时表中生成散列？

如果没有，是否有其他方法可以实现这种工作（同步查询的差异）

我正在为 java 中的哈希映射构建一个复合键，并希望为这些对象中的每一个确定我自己的哈希码。我的问题是以下两种方法中最好的方法是什么。我的复合键具有三个 String 属性和一个 int 属性。

我必须有 className、methodName 和唯一编号，以保证每个键都有唯一的哈希码。我想采用碰撞机会最小的方法。我的直觉是，我“添加”到哈希映射函数的属性越多，发生冲突的可能性就越小。但是，我并不完全确定这是正确的。

我有一个使用线性探测的哈希表。我被赋予了erase(int key)使用以下准则编写函数的任务。

我也得到了一些完成任务的提示

• 重要的是要意识到插入函数将允许您向表中添加新条目，或更新表中的现有条目。

• 对于线性探测版本，请注意插入项目的代码有两个搜索。insert() 函数调用函数 findIndex() 来搜索表以查看该项目是否已经在表中。如果项目不在表中，则进行第二次搜索以找到表中的位置以插入项目。添加删除条目的功能将需要修改插入过程。搜索现有项目时，请确保搜索不会停止，因为该位置已被占用但由于该项目已被删除而现在为空。在搜索插入新项目的位置时，请使用第一个空位置 - 该位置是否曾被占用并不重要。

所以我开始写erase(key)，我似乎遇到了提示所指的问题，但我不确定这意味着什么。我将在一秒钟内提供代码，但是我为测试我的代码所做的是设置哈希表，以便它会发生冲突，然后我删除该键并重新哈希表，但它不会进入正确的位置。

例如，我在哈希表中添加了一些元素：

所以我所有的值都是空的，除了前 3 个索引。显然键 31 应该进入索引 1。但是由于键 1 已经存在，它会发生冲突并解决索引 0。然后我删除键 1 并重新哈希表，但键 31 保持在索引 0。

以下是可能值得一看的功能：

由于 insert 使用 findIndex，我也将其包括在内

这是我目前的擦除开始

有人可以解释我需要做什么才能使其正确重新散列吗？我理解哈希表的概念，但我似乎在这里做错了什么。

编辑

根据用户的建议：

我将大量对象（具有存储在对象的字节数组中的唯一值组合）存储在哈希映射（约 280 万个对象）中，并且在检查我是否有任何哈希码冲突（32 位哈希)，我很惊讶地发现没有，而在统计上，我有几乎 100% 的机会发生至少一次碰撞（参见http://preshing.com/20110504/hash-collision-probabilities/）。

因此，我想知道我检测碰撞的方法是否有问题，或者我是否非常幸运......

以下是我尝试从存储在地图中的 280 万个值中检测碰撞的方法：

这是对象创建哈希值的方法：

任何关于我做错了什么的想法/提示将不胜感激！

谢谢，托马斯

这个问题不需要任何代码，它只是一个关于 MD5 散列的概念性问题。

我的应用管理用户社区。

我使用 MD5 散列将任意长度的用户昵称减少为散列。我希望每个昵称的 MD5 都不同，因为这 MD5(nick)将是我对每个用户的用户 ID。

这总是正确的吗？我确定我遗漏了一些东西，从长远来看可能会发生冲突（数百万用户 === 数百万不同长度的不同刻痕）

我有一个随机数序列（比如 6 个字节）

我现在想从原始序列生成一个更短的序列（比如 3 个字节）

实现这一点的最佳方法是什么，以便保留原始序列的随机性。

假设我在原始序列上运行 SHA-1 哈希码，然后从哈希输出中获取一些字节。随机性是减少、增加还是保持不变。

基本问题是 - 随机数的哈希码是否会产生更少的随机性、更多的随机性或相同的随机性。

如果这是一个重复的问题，我们深表歉意；我发现的大多数都超出了我的想象，所以我可能错过了答案。

对于给定的哈希值，比如 MD5（128 位），与其中 10^12 个哈希值发生冲突的几率是多少？

我的数学不是很好，我想出了这个等式（我认为它是正确的）但不知道如何解决它：

Collision_Chance = 1 - (1 - (1 / 2^128) ) ^ (10^12)

我猜它在 10^-26 左右，这听起来对吗？

谢谢

编辑：我认为我的估计是非常错误的。见生日悖论

You have an empty ice cube tray which has n little ice cube buckets, forming a natural hash space that's easy to visualize.

Your friend has k pennies which he likes to put in ice cube trays. He uses a random number generator repeatedly to choose which bucket to put each penny. If the bucket determined by the random number is already occupied by a penny, he throws the penny away and it is never seen again.

Say your ice cube tray has 100 buckets (i.e, would make 100 ice cubes). If you notice that your tray has c=80 pennies, what is the most likely number of pennies (k) that your friend had to start out with?

If c is low, the odds of collisions are low enough that the most likely number of k == c. E.g. if c = 3, then it's most like that k was 3. However, the odds of a collision are increasingly likely, after say k=14 then odds are there should be 1 collision, so maybe it's maximally likely that k = 15 if c = 14.

Of course if n == c then there would be no way of knowing, so let's set that aside and assume c < n.

What's the general formula for estimating k given n and c (given c < n)?

我对多级数据完整性检查和更正感兴趣。使用多个纠错码的地方（它们可以是 2 个相同类型的代码）。我的印象是，如果使用的 2 个哈希码彼此正交，则使用 2 个代码的系统将实现最大效率。

是否有哪些代码与哪些代码正交的列表？或者您是否需要使用相同的散列函数但具有不同的参数或用法？

我希望第一级 ecc 将是一个 reed-solomon 代码，尽管我实际上无法控制第一个函数，因此我不能使用具有改进功能的单个代码。

请注意，我不关心加密安全性。

编辑：这不是

• 哈希函数何时相互正交？因为它本质上是在询问正交哈希函数的定义是什么。我想要哪些哈希函数是正交的示例。

我做了一个简单的散列函数（如果它可以被称为一个），它将一个字符串转换为一个双精度。

它的工作原理是取第一个字符的值并将其转换为双倍，然后将其与下一个字符的余弦相乘，然后与下一个字符的余弦相乘，依此类推......

这是功能：

那么如何计算这个函数中的碰撞概率呢？

我找到了一个公式，它是 1 - e^(k(k-1)/(2k))，但从我读到的内容，它只有在哈希函数是一个好的函数时才有效（它均匀地分布哈希值，就像一个好的 RNG ， 或类似的东西）。