HashSet和List：哪一种是存储对象列表的高效方法？

当我们需要存储对象列表时，选择合适的数据结构是非常重要的。在这个问题中，我们关注的是HashSet和List之间的性能差异。但是在讨论性能差异之前，我们需要明确一个事实：对于小型数据集来说，性能差异通常并不重要。我们通常关注的是大型数据集，这就是我们需要考虑算法复杂度的时候了。

然而，如果我们在HashSet的性能上确实遇到了瓶颈，那么我们可以尝试创建一个混合的List/HashSet。但是这需要通过大量的实验性能测试来进行验证，而不是在论坛上提问。

什么时候应该担心HashSet和List之间的性能差异呢？我们可以将这个问题重新定义为：当小集合变得足够大以至于需要担心HashSet和List之间的性能差异时，这个临界点是几十个元素、几万个元素、还是数十亿个元素？

实际上，在几百个元素以上，我们会看到明显的性能差异。关键是，如果你的访问模式是HashSet擅长的类型（例如判断元素X是否在集合中），那么总是使用HashSet。如果你的集合太小，以至于List更快，那么这些查找很少会成为应用程序的瓶颈。如果你确实可以测量出这个瓶颈，那么可以尝试进行优化，但否则你将浪费时间。

那么，如果我们有一个小集合，在循环中被多次访问，该怎么办呢？这并不是一个罕见的情况。

答案是，无论临界点在哪里，都应该使用HashSet。因为“如果性能是一个问题，就使用HashSet。在少数情况下，List可能更快，但差异微不足道。”

总之，选择HashSet还是List取决于你的具体需求和性能要求。对于大型数据集和需要频繁进行查找操作的情况，HashSet通常是更好的选择。而对于小型数据集和不需要频繁查找的情况，List可能更加高效。但是无论如何，我们应该始终根据实际需求进行测试和评估，以确保选择最合适的数据结构。

从上述内容中可以看出，这段对比HashSet和List的性能的讨论主要是关于它们在不同方面的表现。作者指出，HashSet和List的行为不同，因此比较它们的性能是没有意义的。作者建议使用能够传达意图的数据结构。即使你说你的List不会有重复项，并且迭代顺序也不重要，这使得它与HashSet类似，但使用List仍然是一个较差的选择，因为它的容错性相对较低。

作者还对性能的一些其他方面进行了分析，包括随机访问、包含、插入、添加、删除和内存消耗。作者提到，虽然HashSet和List在添加元素方面的性能都是O(1)，但HashSet相对较慢，因为它需要在存储之前计算哈希码的成本。此外，HashSet在可扩展性方面更优秀，但也有内存消耗的代价，因为每个条目都作为一个新对象与其哈希码一起存储。

作者的问题是关于HashSet和List的性能问题，但并不是关于理论性能的讨论。HashSet确实允许使用ElementAt()进行随机访问，但这可能需要O(n)的时间。作者还提到，表格中应该包含每个集合是否允许重复项的信息。

最后，作者感谢这个表格，因为它对他在使用情况下进行了正确的选择（选择了HashSet）。

HashSet和List：哪种方式更有效地存储对象列表？

很多人都说，当你的数据量增长到速度成为一个问题时，HashSet<T>总是会比List<T>更快，但这取决于你要做什么。

假设你有一个只有平均5个项的List<T>，在大量循环中，如果每个循环只添加或删除一个项，可能使用List<T>会更好。

我在我的机器上做了一个测试，嗯，必须非常非常小才能从List<T>中获得优势。对于短字符串的列表，在大小为5之后，优势就消失了；对于对象，在大小为20之后，优势也消失了。

以下是测试的结果：

1 item LIST strs time: 617ms

1 item HASHSET strs time: 1332ms

2 item LIST strs time: 781ms

2 item HASHSET strs time: 1354ms

3 item LIST strs time: 950ms

3 item HASHSET strs time: 1405ms

4 item LIST strs time: 1126ms

4 item HASHSET strs time: 1441ms

5 item LIST strs time: 1370ms

5 item HASHSET strs time: 1452ms

6 item LIST strs time: 1481ms

6 item HASHSET strs time: 1418ms

下面是以图形方式显示的数据：

[image]

以下是代码：

[code]

非常感谢！这是一个很好的解释，我正在寻找一种比List<T>更快地添加和删除项的方法，由于我通常会有大量的对象，这种集合非常适合我。

实际上，在.NET框架中有一种集合，根据它包含的项的数量在列表和哈希表之间切换：HybridDictionary。不过，微软似乎已经放弃了它，因为只有非泛型版本可用。

我在这个测试中看到的一个问题是，你正在逐步构建两个列表并在它们之间交替。这几乎肯定会导致分配更加分散，这会损害对List<>的简单线性搜索的性能。如果你可以将数组/列表和字符串放在连续的内存块中，CPU的预取器会将列表（或其中的大块）拉入其缓存中，操作将非常快速（直到某个点，但这应该远远高于5或20！）。

尽管这个答案已经很详细了，但它未能回答关于列表与哈希集搜索性能的原始问题。你正在测试它们的插入和删除速度，这需要更多的时间和不同的性能特征。再试一次，使用.Contains，你的图形将发生显著变化。

为什么你添加和删除的是"string0"而不是"string" + i.ToString())？

-paddock，你能解释为什么分散分配内存会减慢对List<>的搜索吗？我认为无论内存的地址如何，RAM中的任何内存位置的查找速度都是相同的。

CPU无法直接处理系统内存中的数据，它会将数据从内存中拉入缓存中进行处理。请求内存移动和内存实际到达之间有很大的延迟，因此CPU通常会请求一次移动更大的连续内存块。其背后的想法是下一条指令所需的内存很可能非常接近上一条指令使用的内存，因此很可能已经在缓存中。当你的数据分散在整个内存中时，获取幸运的机会就减少了。

请参考下面这个回答，我认为它更清晰、更正确。

运行这段代码并使用Contains，在列表中搜索每个项，包括HashSet的创建（在什么时候值得为现有的List创建一个HashSet进行搜索），我得到的结果是，大约在13个字符串和17个对象时达到平衡。

非常好的答案。但是已经过去了7年，对于.NET Core来说，是否感兴趣进行相同的测量呢？

我也有同样的问题，因为我一直在阅读关于Core性能如何提高的内容。我刚刚比较了4.8框架和.net 5，发现在.net 5中，列表的运行时间约为4.8的50%-60%。旧的HashSet经过了更多优化，而新的HashSet的运行时间约为旧的85%。