C# Array and Dictionary Test, Integer Lookups

You are wondering how a Dictionary or hashtable with integer keys compares against an array. With the Dictionary, you will have hashcode computations and lookups, and with the array you will have computed indices. Here we look at an experiment in the C# language that compares lookups in an array by integer values, and lookups in a Dictionary by integers, both of which provide constant-time lookups.

=== Array and Dictionary performance (C#) ===

Array lookup:       367 ms
Dictionary lookup: 2419 ms

Using array instead of Dictionary

First, we see a program written in the C# language that generates and array of strings with 1000 values, and also a Dictionary with 1000 int keys and string values, using the default IEqualityComparer<int>. There are two properties called ArrayTest and DictionaryTest that return the data structures. In this specific case, the two collections have basically the same purpose and usage.

=== Program that uses array and Dictionary (C#) ===

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

class Program
{
    static string[] ArrayTest
    {
        get
        {
            string[] array = new string[1000];
            for (int i = 0; i < 1000; i++)
            {
                array[i] = i.ToString();
            }
            return array;
        }
    }

    static Dictionary<int, string> DictionaryTest
    {
        get
        {
            var dictionary = new Dictionary<int, string>();
            for (int i = 0; i < 1000; i++)
            {
                dictionary.Add(i, i.ToString());
            }
            return dictionary;
        }
    }

    static void Main()
    {
        //
        // Get the array and Dictionary.
        //
        var array = ArrayTest;
        var dictionary = DictionaryTest;

        //
        // Lookup a value at this index and compare.
        //
        string value1 = array[100];
        string value2 = dictionary[100];
        Console.WriteLine(value1);
        Console.WriteLine(value2);
        Console.WriteLine(value1 == value2);
    }
}

=== Output of the program ===

100
100
True

Description of the code. This code, written in the C# language, creates an array and a Dictionary that both contain strings corresponding to the keys or offsets 0-999. Because the strings are computed at runtime, they will not be interned. The program finds that the values of the strings at the 100 key or offset are equal.

Benchmarking array and Dictionary

First, as a developer you will consider it very likely that the array lookup will be much faster than the Dictionary key computation, and this is entirely correct. However, this test can give you an idea of the difference between the two lookups. Additionally, this article can point you in the direction of how you can exchange a Dictionary for an array.

=== Code that uses array and Dictionary (C#) ===
    (Each block is tested in a loop.)

// Array block
string value = array[i % 1000];
if (string.IsNullOrEmpty(value))
{
    throw new Exception();
}

// Dictionary block
string value = dictionary[i % 1000];
if (string.IsNullOrEmpty(value))
{
    throw new Exception();
}

=== Benchmark description ===
    See top for figures.

Platform:          .NET Framework 3.5 SP1
Iterations tested: 100000000
Loop type:         for loop

What collections to choose

The most important part of this article is just to remind people that sometimes, arrays and Dictionaries are interchangeable, and there are advantages to using simpler data structures such as arrays. Often, you can assign static resources such as images or files to a certain numeric value, and then store them in an array instead of a Dictionary with int keys.

(See Dictionary Int Examples.)

Summary

Here we saw how you can exchange a Dictionary or Hashtable data structure for an array reference type. This has performance and memory usage benefits that are significant. These factors can add up in a complex or performance-critical application. Additionally, arrays can sometimes lead to simpler and less-error prone code that Dictionaries, because you don't need to use methods such as ContainsKey and TryGetValue.

(Do not copy this page.)