CODEWITHSUNDEEP
c#.net
Serve Laurijssen
Serve Laurijssen

Reputation: 9733

performance of two Dictionary retrievals vs one key retrieval

I have this legacy code where there's often this pattern of a dictionary of string to dictionary of string to some object.

Dictionary<string, Dictionary<string, someobject>>

retrieval of an object is then always based on two times TryGetValue

Dictionary<string, Dictionary<string, Dealer>> dicDealers ...

if (dicDealers.TryGetValue(lab, out dealers))
  dealers.TryGetValue(dealerNumber, out dealer);

Now I was thinking it should be more efficient when the two string keys are combined into a key struct with two string members so the objects get retrieved in one go. So I created a Key struct which overrides GetHashCode and Equals calculating a hash on bots key members.

public struct Key<T>
{
    private T mKey1;
    private T mKey2;

    public Key(T t, T u)
    {
        mKey1 = t;
        mKey2 = u;
    }

    public override bool Equals(object obj)
    {
        if (obj == null) return false;

        Key<T> rhs = (Key<T>)obj;

        return mKey1.Equals(rhs.mKey1) && mKey2.Equals(rhs.mKey2);
    }

    public override int GetHashCode()
    {
        int hash = 17;

        hash = ((hash << 5) - hash) + mKey1.GetHashCode();
        hash = ((hash << 5) - hash) + mKey2.GetHashCode();
        return hash;
    }
}

Now you can do it at once.

Key<string> key = new Key<string>(lab, dealerNumber);

if (dicDealers.TryGetValue(key, out someobject))
{
...
}

I thought it should be faster but it turns out both ways are about as fast. How can that be? Can I do something to make the second technique run faster?

Upvotes: 2

Views: 241

Answers (1)

Hans Passant
Hans Passant

Reputation: 941525

You are trying to improve a method that has amortized O(1) complexity. That's a tall task, you can never get more efficient than O(1), there is no algorithm that is O(1/x).

The only thing you could improve is the Oh. A dictionary's Oh is determined by the cost of GetHashCode() and how well the hash code is distributed. You are again fighting a battle that's very hard to win. String.GetHashCode() is written in hand-optimized code and produces a very good hash.

And you did not in fact make your GetHashCode() more efficient, it costs the same as two GetHashCode() calls in the original version. So yes, you certainly should expect your version to take as much time.

Trying to produce a better version is a long shot. You'd have to have special knowledge of the strings, like knowing that only the 1st character is required for a good hash so you can take a shortcut on calculating the hash on the entire string. That's uncommon and a bit dangerous, a poor hash code distribution is detrimental. Most of all, it is not necessary. The core mistake you made was trying to improve code that didn't require improvement. Only ever consider doing this when a profiler told you that TryGetValue() is the critical code.

Upvotes: 7

Related Questions