Remove from Dictionary by Key and Retrieve Value

Question

Is there a way to remove an entry from a Dictionary (by Key) AND retrieve its Value in the same step?

For example, I'm calling

Dictionary.Remove(Key);

but I also want it to return the Value at the same time. The function only returns a bool.

I know I can do something like

Value = Dictionary[Key];
Dictionary.Remove(Key);

but it seems like this will search the dictionary twice (once to get the value, and another time to remove it from the dictionary). How can I (if possible) do both WITHOUT searching the dictionary twice?

Answer 1

Starting with .NET Core 2.0, we have:

public bool Remove (TKey key, out TValue value);

https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.dictionary-2.remove?view=netcore-2.0#System_Collections_Generic_Dictionary_2_Remove__0__1__

Note this API hasn't been included in .NET Standard 2.0 and .NET Framework 4.7.

Answer 2

Because they both have the desired missing method I tried Microsoft's ConcurrentDictionary and C5 from University of Copenhagen http://www.itu.dk/research/c5/ and I can tell with, at least with my use case it was super slow (I mean 5x - 10x slower) compared to Dictionary. I think C5 is sorting both keys and values all the time and Concurrent Dictionary is "too worried" about the calling thread.. I am not here to discuss why those two incarnations of Dictionary are slow. My algorithm was seeking and replacing some entries whereas the first keys would be removed and new keys would be added (some sort of Queue)... The only think left to do was to modify original .Net mscorelib's Dictionary. I downloaded the source code from Microsoft and included the Dictionary class in my source code. To compile I also need to drag along just the HashHelpers class and ThrowHelper class. All that was left was to comment out some lines (e.g. [DebuggerTypeProxy(typeof(Mscorlib_DictionaryDebugView<,>))] and some resource fetching). Obviously I had to add the missing method to the copied class. Also do not try to compile Microsoft Source code you will be doing that for hours, I was lucky enough to get it going.

   public bool Remove(TKey key, out TValue value)
    {
        if (key == null)
        {
            ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
        }

        if (buckets != null)
        {
            int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
            int bucket = hashCode % buckets.Length;
            int last = -1;
            for (int i = buckets[bucket]; i >= 0; last = i, i = entries[i].next)
            {
                if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key))
                {
                    if (last < 0)
                    {
                        buckets[bucket] = entries[i].next;
                    }
                    else
                    {
                        entries[last].next = entries[i].next;
                    }
                    entries[i].hashCode = -1;
                    entries[i].next = freeList;
                    entries[i].key = default(TKey);
                    value = entries[i].value;
                    entries[i].value = default(TValue);
                    freeList = i;
                    freeCount++;
                    version++;
                    return true;
                }
            }
        }
        value = default(TValue);
        return false;
    }

Lastly I modified the namespace to System.Collection.Generic.My In my algorithm I only had two lines where I was getting the value than remove it in the next line.. replaced that with the new method and obtained a steady performance gain of 7%-10%. Hope it helps this use case and any other cases where re-implementing Dictionary from scratch is just not what one should do.