C# - Dictionary Remove Method

Remove, Dictionary. In C#, Dictionary and List both have Remove methods, but the performance dramatically differs. We see how removal methods perform.

List Remove

Dictionary advantage. If a program needs to remove elements from a collection often, using a Dictionary may be worthwhile. The benchmark here helps us understand this.

Dictionary

List

Example. It is important to know the syntax for removing an entry from a Dictionary. We do not need to know the value for the key, or any index value—just the key itself.

Step 1 This program creates a dictionary with 2 entries, each with a different key.

Step 2 The program calls Remove to eliminate one key, and displays the Dictionary before and after.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // Step 1: create a dictionary.
        var entries = new Dictionary<string, int>();
        entries.Add("bird", 10);
        entries.Add("cat", 20);

        foreach (var entry in entries)
        {
            Console.WriteLine($"BEFORE: {entry}");
        }

        // Step 2: remove an entry.
        entries.Remove("bird");

        foreach (var entry in entries)
        {
            Console.WriteLine($"AFTER:  {entry}");
        }
    }
}BEFORE: [bird, 10]
BEFORE: [cat, 20]
AFTER:  [cat, 20]

Benchmark. This program first adds 100,000 integers to a List and then those same integers to a Dictionary. Next it loops over those 100,000 ints and removes them all by value.

Benchmark

Version 1 We remove from the List by calling RemoveAt. We remove the element at index 0.

Version 2 We remove from the Dictionary by calling Remove. We remove all entries.

Result The total milliseconds for the removal of all elements is displayed at the program's termination. The Dictionary version was much faster.

using System;
using System.Collections.Generic;
using System.Diagnostics;

class Program
{
    const int _max = 100000;
    static void Main()
    {
        var list = new List<int>();
        for (int i = 0; i < _max; i++)
        {
            list.Add(i);
        }

        var dictionary = new Dictionary<int, int>();
        for (int i = 0; i < _max; i++)
        {
            dictionary.Add(i, i);
        }

        var s1 = Stopwatch.StartNew();
        // Version 1: remove from List.
        for (int i = 0; i < _max; i++)
        {
            list.RemoveAt(0);
        }
        s1.Stop();
        var s2 = Stopwatch.StartNew();
        // Version 2: remove from Dictionary.
        for (int i = 0; i < _max; i++)
        {
            dictionary.Remove(i);
        }
        s2.Stop();
        Console.WriteLine(s1.Elapsed.TotalMilliseconds);
        Console.WriteLine(s2.Elapsed.TotalMilliseconds);
    }
}384.1117    List
  0.7749    Dictionary

Discussion. A List is a contiguous collection of elements. When you remove an element from it, all following elements must be copied forward. This requires allocations and computations.

And The Dictionary contains each element indexed with a hash code using a bucket array.

Thus This means when an element is removed, only a small array (of collisions) will need to be changed.

Summary. The List collection has a slow Remove method when it contains lots of data. The Dictionary collection meanwhile has a fast Remove method.