C# ListDictionary

What is the point of the ListDictionary collection in the System.Collections.Specialized namespace? This type represents a non-generic C# Dictionary that is implemented with a linked list. For small collections, it is better than collections such as Hashtable.

This page shows the use of the C# ListDictionary type. It provides a simple benchmark.

Example

The ListDictionary can be used in basically the same way as the Hashtable. You can Add and Remove elements and use the Count property. The key difference is in its performance characteristics. In small collections, it will be faster than a Hashtable with the same data.

Program that uses ListDictionary [C#]

using System;
using System.Collections; // For Hashtable.
using System.Collections.Specialized; // For ListDictionary.
using System.Diagnostics;

class Program
{
    static void Main()
    {
	ListDictionary list = new ListDictionary();
	list.Add("dot", 1);
	list.Add("net", 2);
	list.Add("perls", 3);

	Hashtable hash = new Hashtable();
	hash.Add("dot", 1);
	hash.Add("net", 2);
	hash.Add("perls", 3);

	Console.WriteLine("ListDictionary.Count: {0}", list.Count);
	Console.WriteLine("Hashtable.Count: {0}", hash.Count);
	Console.WriteLine();

	const int max = 10000000;
	var s1 = Stopwatch.StartNew();
	for (int i = 0; i < max; i++)
	{
	    object a = list["perls"];
	}
	s1.Stop();
	var s2 = Stopwatch.StartNew();
	for (int i = 0; i < max; i++)
	{
	    object a = hash["perls"];
	}
	s2.Stop();
	Console.WriteLine(((double)(s1.Elapsed.TotalMilliseconds * 1000000) /
	    max).ToString("ListDictionary: 0.00 ns"));
	Console.WriteLine(((double)(s2.Elapsed.TotalMilliseconds * 1000000) /
	    max).ToString("Hashtable: 0.00 ns"));
    }
}

Output
    (Times will depend on your machine.)

ListDictionary.Count: 3
Hashtable.Count: 3

ListDictionary: 17.69 ns
Hashtable: 51.14 ns

Results. You can see that the ListDictionary was faster for looking up an element in a small collection. The Hashtable was slower. If the size of the collections was expanded dramatically, you would see that the Hashtable would become much faster. The Hashtable's time would remain fairly constant while the ListDictionary's time would increase linearly.

Pratical experience

I have spent a lot of time trying to reduce times in C# programs. I have found that types in System.Collections.Generic are much better overall than those in System.Collections and System.Collections.Specialized. I recommend people never write new programs with types such as ListDictionary and Hashtable.

As for implementing Dictionary collections with Lists, this can improve performance. But it raises the possibility of a grossly degenerate performance situation if your program needs to process much more data and still look up elements.

Therefore, my recommendation is to use List for when you need to store elements that do not need to be searched for, and Dictionary for when lookups are required. If you need to add or remove elements, the Dictionary is better because these operations require less memory access.

Summary

The ListDictionary collection from System.Collections.Specialized is not something most developers should spend much time on. It may introduce degenerate behavior into your program unless you are careful with it, and its performance benefits are minimal at best. Modern types from System.Collections.Generic are better in nearly all programs.