为何String.GetHashCode复杂度为O(1)？Dictionary字符串键插入性能疑问

一、为什么Dictionary.Add被认为是O(1)复杂度，而String.GetHashCode()可能需要遍历字符？ #

首先得明确两个复杂度的参考维度：

• Dictionary.Add的O(1)是相对于字典中已有元素的数量而言的平均情况复杂度——意思是不管字典里已有10个还是10000个元素，添加新元素时平均需要执行的操作次数是固定的，和元素总数无关。
• 而String.GetHashCode()的计算时间是相对于字符串本身的长度的：.NET不同版本的字符串哈希实现有差异，早期版本会遍历所有字符，现在的实现会对长字符串做采样优化（只取部分字符计算），但不管哪种方式，字符串越长，哈希计算的耗时都会增加，也就是哈希计算的复杂度是O(k)，k为字符串长度。

这两个维度并不冲突，Dictionary.Add的O(1)描述的是和元素数量的关系，并没有忽略键本身的处理成本。

二、插入超长字符串和空字符串速度一样吗？插入时间是否依赖string键的长度？ #

不一样，插入时间确实和键的长度有关：

• 哈希计算环节：空字符串的哈希计算几乎瞬间完成，而超长字符串哪怕有采样优化，也需要处理更多字符，耗时更长。
• 哈希冲突后的相等性比较：如果两个字符串哈希码相同（冲突），字典会调用string.Equals()确认是否为同一个键，这个操作需要遍历字符对比，长字符串的对比耗时显然比空字符串或短字符串高。

所以实际插入时，键字符串越长，整体耗时大概率会更高。

内容的提问来源于stack exchange，提问作者Nikita Aznauryan