列表 vs 字典（哈希表）

Question

这可能是一个愚蠢的问题，但我正在阅读关于Hashtables和Dictionaries比列表更快的原因，因为它们使用键索引项。

我知道List或Array是没有值的元素，而Dictionary是有值的元素。所以我想，也许明智的做法是使用具有所需值作为键且在所有情况下等值的Dictionary？

更新：

根据评论，我认为我需要一个HashSet。这个question谈论了它们的性能。

- Ricardo Polo Jaramillo

---

哈希表和字典比列表更快，这取决于你对它们的使用方式。 - Frédéric Hamidi

一个 HashSet 可以提供你想要使用 Dictionary 的键而不是值的功能。问题在于它们必须是唯一的，但是你可以使用 Dictionary 来达到同样的效果。 - JG in SD

如果您有重复的值，那么作为键所需的值将无法实现。请注意仅返回翻译后的文本内容。 - Kaf

Answer 1

与列表/数组相比，字典/哈希表也存在一些缺点：

• 您必须在每次查找时计算对象的哈希值。
• 对于小型集合，通过数组迭代可能比计算哈希更快，特别是因为哈希不能保证唯一¹。
• 它们不太适合在项目列表上进行迭代。
• 它们不太适合存储重复条目（有时您确实希望一个值在数组中显示多次）
• 有时类型没有很好的键可以关联。

使用适合情况的工具。 有时这将是列表或数组。 有时它将是字典。 您几乎永远不应再使用HashTable（如果真的不知道要存储哪种类型，请优先选择Dictionary <KeyType，Object>）。

_{¹它通常是唯一的，但由于发生冲突的潜力较小，因此在计算哈希值后集合必须检查桶。}

- Joel Coehoorn

Answer 2

"更快"取决于您使用它们的目的。.NET中的List只是一块连续的内存（这不是链表），因此在按顺序访问时非常高效（特别是考虑到现代CPU的缓存和预取效果），或者通过已知的整数索引进行“随机”访问。查找或插入元素（尤其是在中间）则效率不高。字典Dictionary是一种关联数据结构-键可以是任何可散列的东西（不仅仅是整数索引），但元素没有以“有意义”的方式排序，通过已知键进行访问的速度也不如List的整数索引快。因此，请根据工作选择正确的工具。

- Branko Dimitrijevic

Answer 3

您的说法“列表或数组是没有值的元素，而字典是有值的元素”不是严格正确的。更准确地说，列表是一组元素的集合，哈希表或字典是一组带有唯一键用于访问每个元素的元素集合。

当集合中只有很少的元素或者您只需要访问整个集合而非集合中的单个元素时，请使用列表；当集合很大并/或者您需要查找/访问集合中的单个成员时，请使用哈希表或字典。

- Charles Bretana