Do I have to hash twice in C#?

Question

I have code like the following:

class MyClass
{
    string Name;
    int NewInfo;
}

List<MyClass> newInfo = .... // initialize list with some values
Dictionary<string, int> myDict = .... // initialize dictionary with some values

foreach(var item in newInfo)
{
    if(myDict.ContainsKey(item.Name)) // 'A' I hash the first time here
         myDict[item.Name] += item.NewInfo // 'B' I hash the second (and third?) time here
    else
        myDict.Add(item.Name, item.NewInfo);
}

Is there any way to avoid doing two lookups in the Dictionary -- the first time to see if contains an entry, and the second time to update the value? There may even be two hash lookups on line 'B' -- one to get the int value and another to update it.

Answer 1

Yes - use Dictionary.TryGetValue. It takes an out parameter to receive the value, and returns whether or not the value was found. Here's your adjusted code:

foreach(var item in newInfo)
{
    int value;
    if (myDict.TryGetValue(item.Name, out value))
    {
        myDict[item.Name] = value + item.NewInfo;
    }
    else
    {
        myDict[item.Name] = item.NewInfo;
    }
}

However, we can do better than that in this particular case. If the key- isn't found, the out parameter is set to 0. As we're going to set the new value to either item.NewInfo or item.NewInfo + value we're really doing the same thing either way. We can ignore the return value of the method, and just use:

foreach(var item in newInfo)
{
    int value;
    myDict.TryGetValue(item.Name, out value);
    myDict[item.Name] = value + item.NewInfo;
}

That's quite unusual though - usually you would use the return value, obviously.

Digression

It's only because you're really doing a GetValueOrDefault operation that it works. In fact, that would be a valid pair of extension methods:

public static TValue GetValueOrDefault<TKey, TValue>
    (this IDictionary<TKey, TValue> dictionary, TKey key)
{
    TValue value;
    dictionary.TryGetValue(key, out value);
    return value;
}

public static TValue GetValueOrDefault<TKey, TValue>
    (this IDictionary<TKey, TValue> dictionary, TKey key,
     TValue customDefault)
{
    TValue value;
    if (dictionary.TryGetValue(key, out value))
    {
        return value;
    }
    else
    {
        return customDefault;
    }
}

At that point you could make your code clear and concise:

foreach(var item in newInfo)
{
    myDict[item.Name] = myDict.GetValueOrDefault(item.Name) + item.NewInfo;
}

(You could call GetValueOrDefault(item.Name, 0) for potentially more clarity.)

Back to the point...

Note that you're still doing two lookups - one to fetch the value and one to add/replace it. You can't really avoid that without making the TValue type argument something mutable, which you could change in place. That would be possible, but not terribly nice.

In the original code, you're potentially doing three lookups - one for ContainsKey, and then two (if the key is found) to replace the value. It's easier to see that if we expand the +=:

myDict[item.Name] = myDict[item.Name] + item.NewInfo;

(item.Name would only be evaluated once, but other than that it's the same.)

Another digression

It would be good to have an operation on Dictionary which did a "lookup and replace" based on a function to get the new value based on the old one, e.g.

bool Update(TKey key, Func<TValue, bool, TValue> replacementFunction)

where replacementFunction would be a function taking the current value (or the default value of TValue if the key wasn't found) and a Boolean to say whether or not the key was actually found, and returns the new value. The dictionary could then look up the key, call the replacement function and update the value in place. (This one can't be implemented as an extension method.)

Answer 2

No, you don't have to hash twice most of the time. The secret is that you store an object in the dictionary instead of just an int.

class Program
{
    static void Main(string[] args)
    {
        var newInfo = new List<MyClass>();
        var myDict = new Dictionary<string, MyClass>();

        foreach (var item in newInfo)
        {
            MyClass temp;
            if (!myDict.TryGetValue(item.Name, out temp))
            {
                temp = new MyClass() { Name = item.Name };
                myDict.Add(temp.Name,temp);
            }

            temp.NewInfo += 1;

        }

    }
}


class MyClass
{
    public string Name;
    public int NewInfo;
}