代码之家 › 专栏 › 技术社区 › Joel Coehoorn

为什么String.GetHashCode的复杂度为O(1)

gethashcode dictionary string .net c#

Joel Coehoorn · 技术社区 · 6 月前

我想在字典中使用字符串作为键类型。喜欢 Dictionary<string, string> .

据我所知,如果我想添加一个新对象,它首先会计算密钥的哈希码。因此,Add方法的复杂性归结为 String.GetHashCode() 方法。

我无法得到的是,如果要计算它,我们仍然需要迭代所有字符,它怎么能是O(1)呢?

https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.dictionary-2.add?view=net-9.0

简而言之,我的问题是:添加一个很长的字符串是否和添加一个空字符串一样快?换句话说,插入元素的时间是否取决于插入键的长度(字符串类型)?

2 回复 | 直到 6 月前

dan-kli 6 月前

我认为你混淆了插入字典和字典键哈希计算的复杂性。

String.GetHashCode() 对于字符串的长度(哈希码计算)是O(n),但对于字典的整体插入操作是O(1)步,因为您不必迭代字典的元素。

你写的 "...and then compares it against already existing" ,没有必要这样做,无论如何你都会覆盖现有的值。一旦计算出哈希值,就可以简单地将键和值插入到O(1)处的字典中。

(正如评论中指出的那样,一个例外是如果 capacity of the dictionary increases ,则必须重新分配内部数组,插入操作变为O(n)操作。)

Joel Coehoorn 6 月前

如果我想添加一个新对象,它首先计算密钥的哈希码,然后将其与已经存在的对象进行比较。

不必。它不必与现有密钥进行比较。如果它必须查看关键字,插入不可能是O(1),因为时间会随着关键字数量的增加而增加(不是O(N),因为它可以使用更有效的搜索算法,但也不是O(1”))。

相反,哈希值还决定了字典中的特定存储位置,因此字典可以直接将元素值设置在正确的位置,而无需检查其他哈希值 ^* ,因此保持O(1)插入。如果此位置已经存储了一个现有元素,则根据您的平台/实现,它将覆盖或抛出异常(C#将 throw an ArgumentException )

我无法得到的是,如果要计算它,我们仍然需要迭代所有字符,它怎么能是O(1)呢?

谈论哈希码计算。从字典的角度来看,这无关紧要。字典只看到并引用哈希。计算生成哈希的时间不是工作,根据类型的不同,哈希也可能是O(1),或者可能更糟糕。字符串确实需要检查字符,哈希计算将为O(n),但字典可以 假设哈希 .

字典只关注随着字典中元素数量的增加而增加的复杂性,其中元素是字符串作为单个单元,而不是单个字符。单个元素的复杂性取决于它们的类型,词典可以使用 任何东西 作为一个键,而不仅仅是一个字符串,如果字典插入时间是对话的一部分,那么试图谈论字典插入时间将是愚蠢的,因为我们总是必须回到可以想象到的最糟糕的类型。

^{*字典类型有

时间效率高

,但有时空间

效率低下的

…但只针对引用,而不是整个对象,而且由于数学没有你想象的那么多。}