4

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

所以字符串如下：

blur
Blur
b
Blur_The_Shades_Slightly_With_A_Tint_Of_Blue

...

4

5 回答 5

15

不能保证单个字母之间不会发生冲突。

您可能不会，但未string.GetHashCode指定其中使用的算法，并且可能会更改。（特别是它在 .NET 1.1 和 .NET 2.0 之间发生了变化，这让那些认为它不会改变的人感到很痛苦。）

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

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

于 2009-04-09T18:15:36.793 回答
3

给定一个完美的散列函数（您通常不会拥有，正如其他人所提到的），您可以找到保证没有两个字符串会产生冲突的最大可能字符数，如下所示：

可用的唯一哈希码数 = 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。确实很短，但是请注意，在给定完美散列函数的情况下，此限制甚至可以防止发生冲突的最微小机会。

然而，正如我所提到的，这在很大程度上是理论上的，我不确定它在任何设计考虑中可能有多少用途。话虽如此，希望它可以帮助您从理论角度理解问题，在此之上您可以添加实际考虑因素（例如不完美的哈希函数，分布的不均匀性）。

于 2009-04-09T18:29:10.473 回答
3

通用哈希

要计算S长度字符串L与W每个字符位的冲突概率，以及H假设最佳通用哈希( 1 ) 的长度位哈希，您可以根据大小（桶数）“N”的哈希表计算冲突概率。

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

我们试图将S物品放入N桶中。这成为一个众所周知的问题，生日悖论

解决各种概率和桶数的问题是有启发性的，但假设我们有 10 亿个桶（在 32 位系统中大约有 4GB 内存），那么我们只需要 37K 条目就可以达到 50% 的机会至少是一个碰撞。鉴于试图避免哈希表中的任何冲突显然是荒谬的。

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

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

另一种方法：完美哈希

如果您希望您可以生成所谓的完美哈希，这需要提前完全了解输入值，但通常不太有用。与上述数学类似，我们可以证明即使是完美的哈希也有其局限性：

回想 54 ^ Lstrings of length的限制L。然而，我们只有H大约 40 亿个不同数字的位（我们假设为 32）。因此，如果您可以真正拥有任何字符串和任意数量的字符串，那么您必须满足：

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. 在这个例子中，我避免了封闭和开放寻址的问题。这确实对所涉及的概率有一些影响，但并不显着

于 2009-04-09T20:23:40.497 回答
1

哈希算法不应该保证唯一性。鉴于潜在的字符串（n 长度为 26^n，甚至忽略特殊字符、空格、大写、非英语字符等）比哈希表中的位置多得多，因此无法实现这样的保证. 它只应该保证良好的分布。

于 2009-04-09T18:22:04.033 回答
0

如果您的键是一个字符串（例如，一个字典），那么它的 GetHashCode() 将被使用。那是一个 32 位整数。Hashtable 默认使用 1 键来评估负载因子，并增加存储桶的数量以保持该负载因子。因此，如果您确实看到冲突，它们应该倾向于发生在重新分配边界附近（并在重新分配后不久减少）。

于 2009-04-09T18:21:05.190 回答