Is Dictionary<TKey, TValue> faster than LINQ on a List<T>?

Question

I generally use List<T> for collections. But if I need a fast lookup on a collection, then e.g. in the following example I would use a Dictionary so I could look it up quickly by id:

Dictionary<int, Customer>

But since I can use LINQ to query the List<T> anyway, as below, is there any reason to go through the trouble of using a Dictionary instead of a List? Is Dictionary faster or is LINQ doing something behind the scenes that makes it just as fast?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            List<Customer> customers = new List<Customer>()
            {
             new Customer { Id = 234, FirstName = "Jim", LastName = "Smith" },
             new Customer { Id = 345, FirstName = "John", LastName = "Thomas" },
             new Customer { Id = 654, FirstName = "Rick", LastName = "Ashton" },
             new Customer { Id = 948, FirstName = "Rod", LastName = "Anders" }
            };

            var customer = (from c in customers
                           where c.Id == 654 select c).SingleOrDefault();
            Console.WriteLine(customer.Display());

            Console.ReadLine();

        }
    }


    public class Customer
    {
        public int Id { get; set; }
        public string FirstName { get; set; }
        public string LastName { get; set; }

        internal string Display()
        {
            return String.Format("{0}, {1} ({2})", LastName, FirstName, Id);
        }

    }
}

Solution 1

If you logically want to create a collection where you can easily look up a customer by their ID, I would use some form of IDictionary<int, Customer>. That expresses what you're trying to achieve.

Now you could use a list to do the same thing, and as leppie says for small datasets it will be about as fast or even faster - but for small datasets it'll be very fast anyway, so why do you care? I think it's more important to tell the reader of your code what you're trying to do with the collection - and a dictionary achieves that aim far more effectively than a list, IMO.

Solution 2

According to MSDN getting an item from a dictionary based on key "approaches an O(1) operation." On the other hand executing Where on a list loops through the elements to find matches. So generally dictionary will be definitely faster.

If you want to speed up Linq operations you can use Indexed LINQ which allows to put indexes on your collections.

Solution 3

LINQ isn't magic. It will still have to iterate through a list to find the element you want. Dictionary will still be faster (for collections of suitable size, as leppie points out)

Solution 4

For lists smaller than 20 items, the overhead of a Dictionary/Hashtable will causes it to be slower than a list.

Solution 5

LINQ will generally be slower in this sort of operation. However, on a small enough set (such as your example), it'll likely be faster, due to the differences in overhead. However again, on a small enough set (such as your example) the difference between either solution is going to be so small that it won't matter as much as the question of whether dictionary look up or Where() reads more naturally.

View more solutions

Comments

[Kris van der Mast]

Interesting. Where did you find those numbers? I'm interested in reading more about it.

[Rup]

Is that the cutoff from the old HybridDictionary class?

[leppie]

@XIII: Thumb-sucked guesstimate :)

[DevOhrion]

This post really "demagics" linq. I just found it super helpful. :) stackoverflow.com/questions/3448194/…