c# - 通过索引/键引用时列表与字典

Question

因此，我主要使用列表从数据库中检索少量数据，并将其输入到 Web 应用程序中，但最近遇到了一些字典，它可以使用键生成更具可读性的代码，但是仅通过索引/引用时的性能差异是什么？关键？

我知道字典会使用更多内存，但在这种情况下最佳实践是什么？考虑到我不会执行搜索或对数据进行排序，是否值得进行性能/维护权衡？

Answer 1

当您确实想通过列表查找某个项目时，您应该看到所有项目，直到找到它的键。 让我们看一些基本的例子。你有

Person
{
   public int ID {get;set;}
   public string Name {get;set;}
}

你有收藏List<Person> persons你想通过 ID 找到某个人:

var person = persons.FirstOrDefault(x => x.ID == 5);

正如所写，它必须枚举整个列表，直到找到列表中具有正确 ID 的条目。 (条目 0 与 lambda 匹配吗？不...条目 1 与 lambda 匹配吗？不...等等)。 This is O(n) 。

但是，如果你想通过字典来查找 dictPersons :

var person = dictPersons[person.ID];

如果你想在字典中通过键查找某个元素，它可以立即跳转到它在字典中的位置 - 这是 O(1)。 O(n) 为每个人做这件事。 (如果您想知道这是如何完成的 - Dictionary 对键运行数学运算，这会将其转换为字典内某个位置的值，该值与插入时放置它的位置相同。它被称为哈希函数)

所以，Dictionary比 List 快因为Dictionary不会迭代所有集合，而是Dictionary从确切的位置获取项目(哈希函数计算这个位置)。这是一个更好的算法。

Dictionary依赖链接(维护每个哈希表存储桶的项目列表)来解决冲突，而 Hashtable使用重新哈希来解决冲突(当发生冲突时，尝试另一个哈希函数将 key 映射到存储桶)。 You can read how hash function works and difference between chaining and rehashing.