字典<TKey,TValue>比List <T>上的LINQ更快吗？

Question

我通常List<T>用于收藏.但是,如果我需要对集​​合进行快速查找,那么例如在下面的示例中,我将使用一个字典,以便我可以通过id以下方式快速查找:

Dictionary<int, Customer>

但是既然我可以使用LINQ来查询List<T>,如下所示,是否有任何理由经历使用Dictionary而不是List的麻烦？字典更快还是LINQ在幕后做一些让它同样快的东西？

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);
        }

    }
}

Answer 1

如果您在逻辑上想要创建一个集合,您可以通过其ID轻松查找客户,我会使用某种形式IDictionary<int, Customer>.这表达了你想要实现的目标.

现在你可以使用一个列表来做同样的事情,正如leppie所说的那样,对于小型数据集来说它会快得多,甚至更快 - 但是对于小型数据集来说它无论如何都会非常快,所以你为什么要关心？我认为告诉读者你的代码你正在尝试用这个集合做什么更重要 - 而字典实现这个目标远比列表IMO更有效.

Answer 2

对于小于 20 个项目的列表， a 的开销Dictionary/Hashtable将导致它比列表慢。

Answer 3

LINQ 并不神奇。它仍然需要遍历列表来查找所需的元素。字典仍然会更快（对于合适大小的集合，正如 leppie 指出的那样）

Answer 4

根据MSDN从基于键的字典中获取项目“接近 O(1) 操作”。另一方面，在列表上执行Where 会循环遍历元素以查找匹配项。所以一般字典肯定会更快。

如果你想加速 Linq 操作，你可以使用Indexed LINQ，它允许在你的集合上放置索引。