Do long string keys in a Dictionary cause performance problems?

Question

I thinking about using a Dictionary<string, object> for looking up values by a string key. Based on my knowledge the longer keys the longer it takes to do lookups in a dictionary. My keys can be pretty long, like /page-1/page-2/page-3/page-4 ... and so on where each name can be pretty long by them self.

What performance hit can I expect when using long string keys in a Dictionary? What mechanism causes these costs?

Answer 1

Each time you access a key in that dictionary the input you pass in must be hashed. .NET does not cache string hash codes. Hashing is a linear operation in the input string length. 10 times the length is about 10 times the hashing cost.

The same goes for equality comparisons. When the dictionary finds that two hash codes are equals (this happens on every successful lookup and on each key collision) it must compare the strings. This is again a linear operation but a very fast one.

Those are pretty much the only costs that long keys cause.

I can't tell you whether this is fast enough or not for your use case. You'll have to measure. The answer depends on the key length and how often you access the dictionary.

Answer 2

This is how HashCode is computed for string.

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;
  }
}

So as we can see hash code computation cost depends directly on a length of a string.