Hashtable/Dictionary碰撞问题

Question

Hashtable/Dictionary碰撞问题

4

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

因此，像以下字符串：

blur
Blur
b
Blur_The_Shades_Slightly_With_A_Tint_Of_Blue

...

- Joan Venge

5个回答

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。非常短，但请注意，即使是完美的哈希函数也无法产生冲突，因此这个限制可以防止任何可能性的碰撞。

这基本上是理论性的，就像我之前提到的那样，并不确定它在任何设计考虑中有多大用处。话虽如此，希望它能从理论角度帮助您理解这个问题，然后您可以添加实际考虑因素（例如，非完美哈希函数，分布的不均匀性）。

- Noldorin

+1 我非常喜欢你的数学，我自己也做了一些。你介意我将你的数学集成到我的答案中，以包括完美哈希的实际限制吗？ - ShuggyCoUk

@ShuggyCoUk：没问题...我很想看看你的成果。 :) - Noldorin

集成并在注释中进行归属，现在已经变成了社区维基，如果您愿意，请随意编辑。谢谢。 - ShuggyCoUk

3

通用哈希

假设采用最优的通用哈希（1），为长度为H位的哈希函数计算S个长度为L且每个字符有W位的字符串在哈希表中发生冲突的概率，可以根据哈希表大小（即桶数）'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框架对字符串哈希函数的实现并不是很好（因为它可能会更好），但对于绝大多数用户来说可能是可以接受的，并且计算效率相当高。

另一种方法：完美哈希

如果您愿意，您可以生成所谓的完美哈希，但这需要提前完全知道输入值，因此通常没有用。与上述数学类似，我们可以显示即使完美哈希也有其局限性：

回想一下长度为L的54 ^ 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的值，但在实践中限制值集可能非常困难，您必须提前知道所有这些值，否则就会退化为字符串 ->哈希的数据库，并在遇到新字符串时添加到其中。

对于这个练习，通用哈希是最优的，因为我们希望减少任何碰撞的概率，即对于任何输入，它从一组可能性 R 中产生输出 x 的概率为 1/R。
请注意，对哈希（和内部桶）进行最优化处理相当困难，但您应该期望内置类型在合理的情况下是可行的，尽管不总是理想的。
在这个例子中，我避免了闭散列和开散列的问题。这确实与所涉及的概率有关，但影响不大。

- ShuggyCoUk

此答案现已反映了Noldorin在完美哈希方面的努力，因此现在是社区维护的。 - ShuggyCoUk

1

哈希算法并不保证唯一性。考虑到可能的字符串数量远远超过哈希表中的位置数（对于长度为n的字符串，即使忽略特殊字符、空格、大小写、非英文字符等，也有26^n种可能），因此无法实现这样的保证。它只能保证良好的分布。

- Steve B.

0

如果您的键是字符串（例如字典），则将使用它的GetHashCode()方法。这是一个32位整数。Hashtable默认为1个键对值的加载因子，并增加桶的数量以维持该加载因子。因此，如果您确实看到冲突，它们应该倾向于发生在重新分配边界周围（并且在重新分配后不久减少）。

- Shea

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jon Skeet · Accepted Answer

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

你可能不会遇到冲突，但string.GetHashCode中使用的算法没有具体说明，且可能会更改。（特别是在.NET 1.1和.NET 2.0之间就有所变化，这给那些假设它不会变化的人带来了问题。）

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

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