Hashtable / Dictionary碰撞

仅使用标准英文字母和下划线,可以最多使用多少个字符,而不会在哈希表/字典中引起潜在的冲突。

所以字符串如:

blur Blur b Blur_The_Shades_Slightly_With_A_Tint_Of_Blue 

无法保证您不会在单个字母之间发生碰撞。

可能不会,但未指定string.GetHashCode使用的算法,并且可能会更改。 (特别是它在.NET 1.1和.NET 2.0之间发生了变化,它使人们认为它不会改变。)

请注意,哈希代码冲突不会阻止设计良好的哈希表工作 – 您应该仍然能够获得正确的值,如果它们具有相同的哈希值,则可能需要使用相等性检查多个密钥码。

任何依赖哈希码唯一的字典都缺少有关哈希码的重要信息,IMO :)(除非它在非常特殊的条件下运行,它绝对知道它们是唯一的,即它使用完美的哈希函数 。)

给定一个完美的散列函数 (你通常不会像其他人提到的那样),你可以找到保证没有两个字符串会产生碰撞的最大可能字符数,如下所示:


可用的唯一哈希码的数量= 2 ^ 32 = 4294967296(假设哈希码使用32位整数)字符集的大小= 2 * 26 + 1 = 53(拉丁字母表中的大写字母为26,加上下划线)

那么你必须考虑长度为l (或更小)的字符串总共有54 ^ l表示。 请注意,基数是54而不是53,因为字符串可以在任何字符之后终止,为每个字符添加额外的可能性 – 而不是它会大大影响结果。

采取不。 作为最大字符串表示数的唯一哈希码,您可以得到以下简单的等式:

54 ^ l = 2 ^ 32

并解决它:

 log2 (54 ^ l) = 32 l * log2 54 = 32 l = 32 / log2 54 = 5.56 

(其中log2是基数2的对数函数。)

由于字符串长度显然不能是分数,因此您可以使用不可分割的部分,使最大长度仅为5 。 确实很短,但是观察到这种限制可以防止在给定完美散列函数的情况下最远的碰撞机会。


然而,正如我所提到的,这在很大程度上是理论上的,而且我不确定在任何设计考虑中它可能有多大用处。 这样说,希望它能帮助你从理论的角度理解这个问题,在此基础上你可以添加实际的思考(例如非完美的哈希函数,分布的非均匀性)。

通用哈希

为了计算长度为L且每个字符为W位的S字符串与长度为H位的散列的冲突的概率,假设最佳通用散列 ( 1 ),您可以根据大小的哈希表(桶的数量)计算冲突概率“N`。

首先,我们可以假设一个理想的散列表实现( 2 ),它将散列中的H位完美地分成可用的桶N3 )。 这意味着除了作为N的限制之外, H变得毫无意义。 W和’L’只是S上限的基础。 对于更简单的数学,假设字符串长度< L仅使用特殊的空字符填充到L。 如果我们感兴趣我们感兴趣的是最坏的情况,这是54 ^ L (26 * 2 +’_’+ null),显然这是一个荒谬的数字,实际的条目数比字符集和长度更有用因此,我们将简单地工作,好像S本身就是一个变量。

我们试图把S项放入N桶。 这就成了一个众所周知的问题,即生日悖论

解决这个问题的各种概率和桶的数量是有启发性的,但假设我们有10亿桶(因此在32位系统中大约4GB内存),那么我们只需要37K条目才能达到至少一个50%的几率碰撞。 鉴于试图避免哈希表中的任何冲突变得明显荒谬。

所有这些并不意味着我们不应该关心哈希函数的行为。 显然,这些数字假设是理想的实现 ,它们是我们获得多少好的上限。 糟糕的哈希函数可以在某些区域产生更糟糕的冲突,通过永远或很少使用它来浪费一些可能的“空间”,所有这些都可能导致哈希值低于最佳值,甚至降低到看起来像列表的性能但是有更糟糕的常数因素。

.NET框架的字符串散列函数的实现并不是很好(因为它可能更好),但对于绝大多数用户来说可能是可以接受的并且计算起来相当有效。

另一种方法:完美哈希

如果您希望能够生成所谓的完美哈希,则需要事先充分了解输入值,但这并不常见。 与上述数学相似,我们可以certificate即使是完美的哈希也有其局限性:

回想一下54 ^ L长度为L字符串的限制。 然而,我们只有H比特(我们假定为32),这是大约40亿个不同的数字。 所以,如果你真的有任何字符串和任意数量的字符串,那么你必须满足:

 54 ^ L <= 2 ^ 32 

并解决它:

 log2 (54 ^ L) <= 32 L * log2 54 <= 32 L <= 32 / log2 54 <= 5.56 

由于字符串长度显然不能是分数,因此最大长度为5,确实非常短。

如果你知道你将只有一组远低于40亿的字符串,那么完美的散列可以让你处理L任何值,但是在实践中限制这组值可能非常困难,你必须全部了解它们。提升或降级到数据库的字符串 - >哈希并在遇到新字符串时添加到它。


  1. 对于这个练习,通用散列是最佳的,因为我们希望减少任何冲突的概率,即对于任何输入,它从一组可能性R中输出x的概率是1 / R.

  2. 请注意,在散列(和内部分段)上做一个最佳工作是相当困难的,但是你应该期望内置类型是合理的,如果不总是理想的话。

  3. 在这个例子中,我避免了封闭和开放寻址的问题。 这确实对所涉及的概率有一定影响,但并不显着

哈希算法不应该保证唯一性。 鉴于你的哈希表中有更多的潜在字符串(长度为26 ^ n,甚至忽略特殊字符,空格,大小写,非英语字符等),因此无法满足这样的保证。 。 它只能保证良好的分配。

如果你的密钥是一个字符串(例如,一个字典),那么将使用它的GetHashCode()。 这是一个32位整数。 Hashtable默认为1键来计算负载因子,并增加桶的数量以维持该负载因子。 因此,如果您确实看到了碰撞,则它们应该围绕重新分配边界发生(并且在重新分配后不久会减少)。