Gal Ratner
Gal Ratner is a Techie who lives and works in Los Angeles CA and Austin TX. Follow galratner on Twitter Google
HashSet vs. List search performance. Surprising results.

I was trying to see how fast HashSet search is compared to a List. Microsoft defines the HashSet as: “provides high performance set operations. A set is a collection that contains no duplicate elements, and whose elements are in no particular order. ”

So I wrote the following code:

    class MyObject

    {

        public string MyProperty { get; set; }

    }

 

    class Program

    {

        static void Main(string[] args)

        {

            HashSet<MyObject> myHashSet = new HashSet<MyObject>();

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

                myHashSet.Add(new MyObject() { MyProperty = i.ToString() });

 

            List<MyObject> myList = new List<MyObject>();

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

                myList.Add(new MyObject() { MyProperty = i.ToString() });

 

            while (true)

            {

                DateTime start = DateTime.Now;

                var myHashSetResult = myHashSet.Where(o => o.MyProperty == "9999996").FirstOrDefault();

                Console.WriteLine(DateTime.Now.Subtract(start).ToString());

 

                start = DateTime.Now;

                var myListResult = myList.Where(o => o.MyProperty == "9999996").FirstOrDefault();

                Console.WriteLine(DateTime.Now.Subtract(start).ToString());

                Console.ReadLine();

            }

        }

 

The results were surprising.

 

00:00:00.6809792
00:00:00.5407776

 

The list search was consistently up to 12% faster then the HashSet. If anybody has a better test please let me know.

 

Update 9/2/2011: Based on the comments I received I decided to refactor the code.
I added a randomizer, used a stopwatch and overrided GetHashCode in my object.
The results were still the same. List<T> was faster then HashSet<T>.
Here is the code:

static void Main(string[] args)
        {
            Random r = new Random();
            HashSet<MyObject> myHashSet = new HashSet<MyObject>();
            List<MyObject> myList = new List<MyObject>();
 
            // Populate the hash set
            for (int i = 0; i < 9999999; i++)
            {
                if (i == 9999998)
                    myHashSet.Add(new MyObject() { MyProperty = "365" });
                myHashSet.Add(new MyObject() { MyProperty = r.Next().ToString() });
            }
 
            // Populate the list
            for (int i = 0; i < 9999999; i++)
            {
                if (i == 9999998)
                    myList.Add(new MyObject() { MyProperty = "365" });
                myList.Add(new MyObject() { MyProperty = r.Next().ToString() });
            }
 
            Stopwatch stopWatch = new Stopwatch();
            TimeSpan ts;
            string elapsedTime;
 
            while (true)
            {
                stopWatch.Stop();
                stopWatch.Reset();
                stopWatch.Start();
 
                var myHashSetResult = myHashSet.Where(o => o.MyProperty == "365").FirstOrDefault();
                
                stopWatch.Stop();
                ts = stopWatch.Elapsed;
                elapsedTime = String.Format("HashSet: {0:00}:{1:00}:{2:00}.{3:00}",
                    ts.Hours, ts.Minutes, ts.Seconds,
                    ts.Milliseconds / 10);
                Console.WriteLine("RunTime " + elapsedTime);
 
                stopWatch.Stop();
                stopWatch.Reset();
                stopWatch.Start();
 
                var myListResult = myList.Where(o => o.MyProperty == "365").FirstOrDefault();
 
                stopWatch.Stop();
                ts = stopWatch.Elapsed;
                elapsedTime = String.Format("List: {0:00}:{1:00}:{2:00}.{3:00}",
                    ts.Hours, ts.Minutes, ts.Seconds,
                    ts.Milliseconds / 10);
                Console.WriteLine("RunTime " + elapsedTime);
 
                Console.ReadLine();
            }
        }
 
        class MyObject
        {
            public string MyProperty { getset; }
 
            public override int GetHashCode()
            {
                return Convert.ToInt32(MyProperty);
            }
        }

It yielded the following results:

RunTime HashSet: 00:00:00.48
RunTime List: 00:00:00.39

 


Posted 29 Jul 2009 8:14 AM by Gal Ratner
Filed under: , ,

Powered by Community Server (Non-Commercial Edition), by Telligent Systems