c# - 列表与字典（哈希表）

Question

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

我知道 a ListorArray用于没有值的元素，而 aDictionary用于具有值的元素。所以我认为拥有一个Dictionary你需要的值作为键并且所有这些值都相等可能是明智的？

更新：

根据评论，我认为我需要的是HashSet. 这个问题谈论他们的表现。

Answer 1

“更快”取决于您需要它们做什么。

.NETList只是一块连续内存（这不是链表），这使得顺序访问（尤其是考虑现代 CPU 的缓存和预取的影响）或通过已知整数“随机”访问非常有效指数。搜索或插入元素（尤其是在中间） - 不是那么多。

Dictionary是一种关联数据结构 - 键可以是任何可散列的（不仅仅是整数索引），但元素没有以“有意义”的方式排序，并且通过已知键的访问速度不如List整数索引。

因此，为工作选择合适的工具。

Answer 2

字典/哈希表与列表/数组也有一些弱点：

• 您必须在每次查找时计算对象的哈希值。
• 对于小型集合，遍历数组可能比计算哈希更快，特别是因为不能保证哈希是唯一的¹。
• 他们不擅长迭代项目列表。
• 它们不太擅长存储重复条目（有时您合法地希望一个值在数组中显示不止一次）
• 有时一个类型没有一个好的键来关联它

使用适合情况的东西。有时这将是一个列表或数组。有时它会是一个字典。您几乎不应该再使用 HashTable （如果您真的不知道要存储的类型，请选择 Dictionary<KeyType, Object>）。

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

Answer 3

您的陈述“列表或数组适用于没有值的元素，而字典适用于有值的元素”，严格来说并不正确。

更准确地说，List 是元素的集合，而 Hashtable 或 Dictionary 是元素的集合以及用于访问每个元素的唯一键。

为极少数元素的集合使用列表，或者当您只需要访问整个集合而不是集合的单个元素时。

当集合很大和/或当您需要查找/访问集合的各个成员时，请使用哈希表或字典。