Chris Newman - Dictionary VS Hash Table

Tuesday, January 08, 2008

Dictionary VS Hash Table

Posted in ASP.NET | Generics

We all know how useful a hash table can be, but if you are using the .NET Framework 2.0 you should be using a Dictionary instead. A dictionary and a hash table in .NET 2.0 are very similar but with 1 main difference, a dictionary is faster because it does not need to box and unbox the data as a hash table would.

I made a simple program to see just how much faster a dictionary is than a hash table. I ran the test 20 times for each data set and the results were close each time. A GUID as the key and a boolean as the data.

This is the results of the last test for each dataset.

Time in Milliseconds for 100,000 keys	Dictionary	Hash Table
Inserting	34.41264	76.0970
Reading	18.9005	31.1648
Deleting	21.2474	30.4655

Time in Seconds for 10,000,000 keys	Dictionary	Hash Table
Inserting	6.5704143	26.9096540
Reading	3.1362891	5.6670613
Deleting	3.4623316	4.8830676

My comp specs

Vista Business 32bit, AMD 64 x2 5000+, 2GB ram

and now for the code I used. You can also download the project.

hashVsDictionary.zip

using System;

using System.Collections;

using System.Collections.Generic;

using System.Diagnostics;

namespace hashVsDictionary

    internal class Program

        private static void Main(string[] args)

            #region init

            int num = 10000000;

            Guid[] guids = new Guid[num];

            Stopwatch s = new Stopwatch();

            s.Start();

            for (int i = 0; i < num; i++)

                guids[i] = Guid.NewGuid();

            s.Stop();

            Console.WriteLine("Data Creation = " + s.Elapsed);

            s.Reset();

            #endregion

            #region hash

            Hashtable hash = new Hashtable();

            s.Start();

            for (int i = 0; i < num; i++)

                hash.Add(guids[i], true);

            s.Stop();

            Console.WriteLine("Insert Hash = " + s.Elapsed);

            s.Reset();

            s.Start();

            for (int i = 0; i < num; i++)

                bool b = Convert.ToBoolean(hash[guids[i]]);

            Console.WriteLine("Extracting Hash = " + s.Elapsed);

            s.Reset();

            s.Start();

            for (int i = 0; i < num; i++)

                hash.Remove(guids[i]);

            Console.WriteLine("Removing Hash = " + s.Elapsed);

            s.Reset();

            #endregion

            #region dict

            Dictionary<Guid, bool> dict = new Dictionary<Guid, bool>();

            s.Start();

            for (int i = 0; i < num; i++)

                dict.Add(guids[i], true);

            s.Stop();

            Console.WriteLine("Insert Dictionary = " + s.Elapsed);

            s.Reset();

            s.Start();

            for (int i = 0; i < num; i++)

                bool b = dict[guids[i]];

            Console.WriteLine("Extracting Dict = " + s.Elapsed);

            s.Reset();

            s.Start();

            for (int i = 0; i < num; i++)

                dict.Remove(guids[i]);

            Console.WriteLine("Removing Dict = " + s.Elapsed);

            s.Reset();

            #endregion

            Console.ReadLine();

Tuesday, January 08, 2008 2:18:33 AM (Eastern Standard Time, UTC-05:00)

Comments [2] -

Tuesday, February 26, 2008 1:02:09 PM (Eastern Standard Time, UTC-05:00)

Great, Thank you for sharing this. I've assumed dictionaries would be more efficient but have been looking for proof. Thanks again!

Jeremy

Monday, May 19, 2008 4:33:36 AM (Eastern Daylight Time, UTC-04:00)

It's faster because Dictionary knows what to store.
But if you use to store Object, hashtable is way more faster.
From microsoft:
"The Dictionary class has the same functionality as the Hashtable class. A Dictionary of a specific type (other than Object) has better performance than a Hashtable for value types because the elements of Hashtable are of type Object and, therefore, boxing and unboxing typically occur if storing or retrieving a value type."

Hmmm

OpenID
Please login with either your OpenID above, or your details below.

Name
E-mail	(will show your gravatar icon)
Home page

	Remember Me
Comment (Some html is allowed: `a@href@title, b, i, strike, strong, u`) where the @ means "attribute." For example, you can use <a href="" title=""> or <blockquote cite="Scott">.
Enter the code shown (prevents robots):
Live Comment Preview

Navigation

Home

Web Solutions

Bradford Sherrill

Advertisments