Dictionary Performance

I tested performances of these classes :

A) Key-value keepers
- Dictionary
- SortedDictionary
- SortedList
B) Value keepers
- List
- HashSet
- List (Sorted and binary searched)

I inserted a number of random numbers to these classes and searched for numbers afterwards.
Below results show the average of 100 tests.

Item Count		5		10		50		100		1,000		10,000
Operation		Insert (µs)	Search (µs)	Insert (µs)	Search (µs)	Insert (µs)	Search (µs)	Insert (µs)	Search (µs)	Insert (µs)	Search (µs)	Insert (µs)	Search (µs)
Key-Value Holders(string - string)	Dictionary	3.97	12.81	4.33	11.20	8.75	15.10	12.78	20.04	111.49	116.07	1,037.95	1,082.61
	SortedDictionary	2.27	2.59	6.95	6.30	65.43	48.79	131.48	134.95	2,133.92	1,936.47	29,699.97	27,179.20
	SortedList	2.67	3.58	6.59	6.75	82.51	62.68	116.64	115.66	2,747.47	1,772.13	115,544.27	24,216.48
Value Holders(string)	List	2.46	12.04	2.60	11.89	3.61	42.94	4.62	141.05	33.44	11,644.09	263.98	1,166,795.60
	HashSet	0.84	1.67	1.33	1.70	6.53	5.93	9.76	10.84	78.95	103.39	914.99	1,085.26
	List(Sorted)	9.41	7.37	18.38	11.42	95.63	61.45	184.43	112.95	2,353.52	1,687.84	31,121.19	23,464.25

For value holder classes :
- ICollection.Add(item) method is used to insert items.
- ICollection.Contains(item) method is used to search for items

For key-value holder classes
- IDictionary.Add(key, item) method is used to insert items.
- IDictionary.ContainsKey(key) method is used to search for items.

RESULTS

If you want to keep key-value pairs, you obviously want to do search business.

If you keep less than 10 items of key-value pairs, search performance of sorted dictionary is the best. Above 10 items dictionary beats others in search business.

If you want to keep only values, there are two businesses : transferring the data, or searching the data.

If you are to insert the items to a list, transfer them to some other method, and in that method you loop through all items, List is the best tool.

If you are to insert items to some list and to do checks of existence on that list, HashSet is the best tool.



Edit : You may find the code here :


using System;
using System.Collections.Generic;
using System.Data;
using System.Data.Common;
using System.Data.SqlClient;
using System.Diagnostics;
using System.Linq;
using System.Runtime.InteropServices;
using System.Text.RegularExpressions;
using System.Threading;
using System.Collections;

namespace ConsoleApp
{



public static class Program2
{

private static void DebugWriteLine(string message, int testCount, VoidMethod method)
{
Stopwatch t2 = new Stopwatch();
t2.Start();
for (int j = 0; j < testCount; j++)
{
method();
}
t2.Stop();
Console.WriteLine(message + "\t" + ((t2.Elapsed.TotalSeconds * 1000000) / testCount).ToString("0.###############"));
}

private static void TestDictionaryInsert<T>(T dict, List<string> items) where T : IDictionary<string, string>
{
foreach (var item in items)
{
dict.Add(item, item);
}
}

private static void TestDictionarySearch<T>(T dict, List<string> items) where T : IDictionary<string, string>
{
foreach (var item in items)
{
dict.ContainsKey(item);
}
}

private static void TestListInsert<T>(T list, List<string> items) where T : ICollection<string>
{
foreach (var item in items)
{
list.Add(item);
}
}

private static void TestListSearch<T>(T list, List<string> items) where T : ICollection<string>
{
foreach (var item in items)
{
list.Contains(item);
}
}

static void Main(string[] args)
{
TestPerformanceOfDataHolders(100);
Console.ReadKey();
}

public static void TestPerformanceOfDataHolders(int itemCount)
{
var items = new List<string>(itemCount);

Random r = new Random((int)DateTime.Now.Ticks);
int random = 0;
for (int i = 0; i < itemCount; i++)
{
do
{
random = r.Next();
} while (items.Contains(random.ToString()));
items.Add(random.ToString());
}

List<IDictionary<string, string>> dictList = new List<IDictionary<string, string>>();
dictList.Add(new Dictionary<string, string>());
dictList.Add(new SortedDictionary<string, string>());
dictList.Add(new SortedList<string, string>());

List<ICollection<string>> colList = new List<ICollection<string>>();
colList.Add(new List<string>());
colList.Add(new HashSet<string>());

var sortedList = new List<string>();

foreach (var item in dictList)
{
TestDictionaryInsert(item, items);
}

foreach (var item in colList)
{
TestListInsert(item, items);
}

sortedList.AddRange(items);
sortedList.Sort();

const int testCount = 100;
foreach (var item in dictList)
{
DebugWriteLine(item.GetType().Name + " Insert", testCount, delegate
{
item.Clear();
TestDictionaryInsert(item, items);
});
}

foreach (var item in colList)
{
DebugWriteLine(item.GetType().Name + " Insert", testCount, delegate
{
item.Clear();
TestListInsert(item, items);
});
}

DebugWriteLine("List(Sorted) Insert", testCount, delegate
{
sortedList.Clear();
foreach (var item in items)
{
sortedList.Add(item);
}
sortedList.Sort();
});

foreach (var item in dictList)
{
DebugWriteLine(item.GetType().Name + " Search", testCount, delegate
{
TestDictionarySearch(item, items);
});
}

foreach (var item in colList)
{
DebugWriteLine(item.GetType().Name + " Search", testCount, delegate
{
TestListSearch(item, items);
});
}

DebugWriteLine("List(Sorted) Search", testCount, delegate
{
foreach (var item in items)
{
sortedList.BinarySearch(item);
}
});
}



}

}