Why is NameValueCollection.Remove(string key) so slow on large collections?

Question

I have a situation where I have a large collection of items stored in HttpApplicationState which internally uses a NameValueCollection to store key-value pairs. By large I mean in the order of hundreds of thousands of string items. In this particular scenario I am also trying to do a batch removal of keys (again, removing large chunks of items by key from the collection) but I am finding that is painfully slow to do.

I wrote the following samples to compare. The first code sample uses a NameValueCollection to remove all values by key:

NameValueCollection collection = new NameValueCollection();

// Setup
for (int i = 0; i < 100000; i++)
{
    collection.Add(i.ToString(), i.ToString());
}

// Remove
for (int i = 0; i < 100000; i++)
{
    collection.Remove(i.ToString());
}

Running this takes an age (in fact I gave up because it took too long). I then compared it with this version which uses a Dictionary<TKey, TValue>:

Dictionary<int, int> collection = new Dictionary<int, int>();

// Setup
for (int i = 0; i < 100000; i++)
{
    collection.Add(i, i);
}

// Remove
for (int i = 0; i < 100000; i++)
{
    collection.Remove(i);
}

The above sample runs so fast it might as well be instant.

So why do two different collections that to me look to do similar things work so differently?

Answer 1

Thanks to the BCL Reference Source I was able to determine why the NameValueCollection.Remove() method was taking so long. The following is a code snippet of the NameObjectCollectionBase.BaseRemove() method which is invoked:

if (name != null) {
    // remove from hashtable
    _entriesTable.Remove(name);

    // remove from array
    for (int i = _entriesArray.Count-1; i >= 0; i--) {
        if (_keyComparer.Equals(name, BaseGetKey(i)))
            _entriesArray.RemoveAt(i);
    }
}

Basically a Dictionary<TKey, TValue> works as a hash table which means that lookup by key is extremely fast. Whereas a NameValueCollection appears to work more like an array where indexes and keys are tracked. By removing hundreds of thousands of keys at a time this method will in fact loop through the entire internal array countless times to find the correct value to remove!

In the end I changed my code to not use a NameValueCollection and instead used a Dictionary<TKey, TValue> instead because of this.