字典中的长字符串键会导致性能问题吗？

Question

我考虑使用Dictionary<string, object>来通过字符串键查找值。据我所知，键越长，在字典中查找的时间就越长。我的钥匙可能很长，就像/page-1/page-2/page-3/page-4 .以此类推，每个名字对他们来说都是很长的。

在字典中使用长字符串键时，性能会受到什么影响？是什么机制导致了这些成本？

Answer 1

每次访问字典中的密钥时，都必须对传入的输入进行散列。.NET不缓存字符串哈希码。散列是输入字符串长度中的线性操作。10倍的长度大约是散列成本的10倍。

平等比较也是如此。当字典发现两个哈希码相等时(在每次成功查找和每次键冲突上都会发生这种情况)，它必须比较字符串。这又是一个线性运算，但速度非常快。

这几乎是长钥匙造成的唯一费用。

我无法告诉您，对于您的用例来说，这是否足够快。你得量一下。答案取决于键的长度和访问字典的频率。

Answer 2

这是计算字符串的HashCode的方式。

public override unsafe int GetHashCode()
{
  if (HashHelpers.s_UseRandomizedStringHashing)
    return string.InternalMarvin32HashString(this, this.Length, 0L);
  fixed (char* chPtr = this)
  {
    int num1 = 352654597;
    int num2 = num1;
    int* numPtr = (int*) chPtr;
    int length = this.Length;
    while (length > 2)
    {
      num1 = (num1 << 5) + num1 + (num1 >> 27) ^ *numPtr;
      num2 = (num2 << 5) + num2 + (num2 >> 27) ^ numPtr[1];
      numPtr += 2;
      length -= 4;
    }
    if (length > 0)
      num1 = (num1 << 5) + num1 + (num1 >> 27) ^ *numPtr;
    return num1 + num2 * 1566083941;
  }
}

因此，我们可以看到，哈希代码的计算成本直接取决于字符串的长度。