C＃：为什么字典比列表快得多？
我正在testing从Dictionary VS列表中获取数据的速度。
我用这个代码来testing：
internal class Program { private static void Main(string[] args) { var stopwatch = new Stopwatch(); List<Grade> grades = Grade.GetData().ToList(); List<Student> students = Student.GetStudents().ToList(); stopwatch.Start(); foreach (Student student in students) { student.Grade = grades.Single(x => x.StudentId == student.Id).Value; } stopwatch.Stop(); Console.WriteLine("Using list {0}", stopwatch.Elapsed); stopwatch.Reset(); students = Student.GetStudents().ToList(); stopwatch.Start(); Dictionary<Guid, string> dic = Grade.GetData().ToDictionary(x => x.StudentId, x => x.Value); foreach (Student student in students) { student.Grade = dic[student.Id]; } stopwatch.Stop(); Console.WriteLine("Using dictionary {0}", stopwatch.Elapsed); Console.ReadKey(); } } public class GuidHelper { public static List<Guid> ListOfIds=new List<Guid>(); static GuidHelper() { for (int i = 0; i < 10000; i++) { ListOfIds.Add(Guid.NewGuid()); } } } public class Grade { public Guid StudentId { get; set; } public string Value { get; set; } public static IEnumerable<Grade> GetData() { for (int i = 0; i < 10000; i++) { yield return new Grade { StudentId = GuidHelper.ListOfIds[i], Value = "Value " + i }; } } } public class Student { public Guid Id { get; set; } public string Name { get; set; } public string Grade { get; set; } public static IEnumerable<Student> GetStudents() { for (int i = 0; i < 10000; i++) { yield return new Student { Id = GuidHelper.ListOfIds[i], Name = "Name " + i }; } } } 记忆中有学生和成绩的列表，他们有StudentId的共同点。
在第一种方法中，我尝试使用LINQ在我的机器上花费接近7秒的列表来查找学生的成绩，而在另一种方式中，我首先将List转换为字典，然后使用不到一秒的密钥从字典中find学生的成绩。 
当你这样做：
student.Grade = grades.Single(x => x.StudentId == student.Id).Value;
正如所写的，它必须枚举整个List直到它find列表中具有正确的studentId的条目（条目0是否与lambda匹配？否…条目1匹配lambda？No …等等）。 这是O（n）。 既然你为每个学生做了一次，那就是O（n ^ 2）。
但是，当你这样做：
student.Grade = dic[student.Id];
如果你想通过字典中的键find某个元素，它可以立即跳转到字典中的位置 – 这是O（1）。 O（n）为每个学生做。 （如果你想知道这是怎么完成的 – Dictionary对键进行math运算，将其转换为字典中的一个值，这与插入时的位置相同）
所以，字典更快，因为你使用了一个更好的algorithm。
使用字典时，您正在使用密钥来检索您的信息，这使得它可以更有效地find它，使用Single Linqexpression式，因为它是一个列表，除了查看整个列表想要的项目。
原因是因为字典是一个查询，而列表是一个迭代。
Dictionary使用散列查找，而列表则需要遍历列表，直到每次从结果中find结果。
换一种方式。 该列表将比第一个项目的字典更快，因为没有什么可查的。 这是第一个项目，繁荣..完成了。 但第二次清单必须查看第一个项目，然后是第二个项目。 第三次通过它必须通过第一个项目，然后第二个项目，然后第三个项目..等。
所以每次迭代查找需要越来越多的时间。 列表越大，需要的时间越长。 虽然字典总是一个或多或less固定的查找时间（随着字典变大，字典也会增加，但速度要慢得多，所以比较几乎是固定的）。
Dictionary使用散列来search数据。 字典中的每个项目都存储在包含相同散列的项目的桶中。 速度要快得多
尝试整理你的清单，然后会更快一点。
一个字典使用一个哈希表 ，它是一个很好的数据结构，因为它将input映射到相应的输出几乎是瞬间的，它已经指出O（1）的复杂性，这意味着或多或less的立即检索。
它的缺点是，为了performance，你需要提前大量的空间（取决于实现方式，可能需要单独的链接或线性/二次探测，至less可以像计划存储的一样多，可能是双倍的后一种情况），而且您需要一个很好的散列algorithm，将您的input（ "John Smith" ）唯一地映射到相应的输出，如数组中的位置（ hash_array[34521] ）。
同样以sorting的顺序列出条目是一个问题。 如果我可以引用维基百科：
按特定顺序列出所有n个条目通常需要单独的sorting步骤，其成本与每个条目的log（n）成比例。
有一个线性探测和单独的链接读一些更高的细节:)
字典是基于一个哈希表，这是一个相当有效的algorithm来查找的东西。 在一个列表中，你必须去逐个元素，以find一些东西。
这都是数据组织的问题
在查找数据时，键控集合总是比非键控集合更快。 这是因为一个非键控的集合将不得不列举它的元素来find你正在寻找的东西。 在键控collections中，您可以直接通过键访问元素。
这些是比较列表与字典的一些不错的文章。
这里 而这一个 。
