1. Technology

C# Online Tutorial - How to use Dictionary Collections

Using the List<T> class

By

List Image

In the previous tutorial, we looked at an Collection Classes in particular the List<T> classs and in this one we'll continue with the Dictionary.

Lists Are Ok But...

In fact they are very good for indexing operations and adding items at the end. But if you want to search through them or add items in the middle, well not so good. If you need fast searching on a List you use one of the three BinarySearch Methods provided, oh and the list must be sorted of course.

That Binary search is O(Log n) where n is the number of elements. Don't know this notation? Here's a link to Wikipedia on Big O Notation.

O(1) is best; that's constant time for example deciding if an int number is odd or even. A bubble sort is O (n2) which is particularly bad. To find the smallest item in an unsorted array is O(n) because you have a loop that compares each item. If you have more items it takes proportionately longer.

A Dictionary provides almost O(1)

That is for retrieving a value from it's key. Behind the scenes it uses a hashmap and most keys (which must be unique) map to a unique location. When two keys collide (i.e. the hashes are identical), then the second or subsequent keys are stored nearby and extra key comparisons must be done. This is why a Dictionary is almost but not quite O(1).

There are several Dictionary Classes in the .NET framework. Remember though that any that aren't descended from Systems.Collections.Generic tend to be older. For instance the System.Collections.Specialized Namespace has the following Dictionary classes:

  • HybridDictionary Class.
  • OrderedDictionary Class and IOrderedDictionary interface.
  • ListDictionary Class
  • StringDictionary Class.

And in the Systems.Collections.Generic namespace there are:

  • Dictionary Class.
  • SortedDictionary Class.

You need a shelf for all those dictionaries! We'll just deal with the Dictionary class.

The concept of a Dictionary (also known as a Map or associative array in other programming languages) is that you have a collection of keys/value pairs. Each key has an associated value and keys are unique.

What is a Key?

It can be any type though strings are more common. A numeric key is possible but unless you have wide gaps between numbers, you might as well use an array for that. In the example code, I've used a String.

The value can be any type, though value types will be copied.

I've created an example program that manages half a million directory entries. A function GetUniqueKey() returns a string of the specified length. I used a 25 char key and a 100 char len string. Ten of the keys are randomly copied into a List called randomkeys. After the half million random values are stored the ten keys are retrieved.

This is the declaration for the Dictionary.

private static Dictionary intDict = new Dictionary(MaxItems);

This specifies an initial capacity MaxItems - there are several constructor overloads, you don't have to specify the capacity. If you add more items then it grabs more memory and grows. This is true of most collection classes.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Security.Cryptography;
using System.Text;

namespace exdict1
{
    class Program
    {
        private const int MaxItems = 50000;
        private static Dictionary< String,String> intDict = new Dictionary<String,string>(MaxItems) ;
        private static Random r = new Random() ;

        // Note this is from http://stackoverflow.com/questions/1344221/how-can-i- generate-random-8-character-alphanumeric-strings-in-c

        public static string GetUniqueKey(int maxSize)
        {
            var chars ="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890".ToCharArray() ;
            var data = new byte[maxSize];
            var crypto = new RNGCryptoServiceProvider() ;
            crypto.GetNonZeroBytes(data) ;
            var result = new StringBuilder(maxSize) ;
            foreach (var b in data)
            {
                result.Append(chars [b % (chars.Length)]) ;
            }
            return result.ToString() ;
        }


        private static void Main(string[] args)
        {
            Console.WriteLine("Generating...") ;
            var watch = new Stopwatch() ;
            var randomkeys = new List<String>(10) ;

            watch.Start() ;
            for (var i = 0; i < MaxItems; i++)
            {
                var key = GetUniqueKey(25) ;
                var value = GetUniqueKey(100) ;
                intDict.Add(key, value) ;
                if (r.Next(100) == 1)
                {
                     if (randomkeys.Count() < 10)
                     {
                         randomkeys.Add(key) ;
                     }
                }
            }
            watch.Stop() ;
            Console.WriteLine("Generated... in {0}", watch.Elapsed.TotalSeconds) ;
            watch.Reset() ;
            watch.Start() ;
            for (var i = 0; i < 10; i++)
            {
                var akey = randomkeys[i];
                var value = intDict [akey];
                Console.WriteLine ("Key= {0} Value = {1}",akey,value) ;
            }
            Console.WriteLine("Fetched... in {0}", watch.Elapsed.TotalSeconds) ;
            watch.Stop() ;
            Console.ReadKey() ;
        }
     }
   }

In this example, I've just declared everything static rather than declaring the code in a class and creating an instance of it.

On my PC it takes 11.5 seconds to generate the half million strings and keys and 1.2 ms to retrieve the ten values. The ideone version only does it for 50,000 keys/values as 500,000 x 250 bytes is far too much for a webserver. In fact 50,000 was probably too much as well but it worked though this probably comes close to their definition of abuse!

The routine to generate the strings and keys came from a stackoverflow question and I've left the link in to the question as a comment in the source. It uses a cryptographically secure source to generate bytes which are indexed into a char array to generate the strings.

That's basically all there is to a Dictionary. Build it up by adding values wih a key then later retrieve them. There's no persistence, i.e. you can't save the Dictionary to disk but Paul Welter has created a SerialilizableDictionary class that saves it out in XML.

In the next C# tutorial I'll look at comparison and sorting in Collection classes.

  1. About.com
  2. Technology
  3. C / C++ / C#
  4. C# / C Sharp
  5. Learn C Sharp
  6. How to use Dictionary Collections

©2014 About.com. All rights reserved.