C#HashSet <T>搜索性能(与ObservableCollection <T>相比)？

Question

C#的通用HashSet <T>搜索性能应该是O(1),并且ObservableCollection <T>的搜索性能应该是O(n).

我有大量的唯一元素,每个元素都有一个不唯一的DateTime属性.

每个元素只需返回其DateTime.GetHashCode()即可计算其HashCode.

现在我想得到我的数据的一个子集,例如,所有元素的日期都在2012年3月到2012年6月之间.

    var result = from p in this.Elements
                 where p.Date >= new DateTime(2012, 03, 01) &&
                       p.Date <= new DateTime(2012, 30, 06
                 select p;

如果我在300.000个元素的集合上运行此LINQ查询,则返回给定范围内的80个元素需要大约25毫秒 - 如果我使用HashSet <T>或ObservableCollection <T>则无关紧要.

如果我手动遍历所有元素并检查它们,则需要相同的时间,约25毫秒.

但我确实知道在给定范围内的所有日期的HashCode.是否可以从我的HashSet <T>获取具有给定HashCodes的所有元素？我觉得那会快得多......

是否可以加快LINQ查询？我假设它没有利用我的HashSet <T>的特殊能力？

Answer 1

您没有使用正确的数据结构。您应该使用排序列表（按Date属性排序）之类的东西，然后您可以在其中对范围的开头和结尾进行二分搜索。

Answer 2

正如已经指出的那样，哈希集在确定给定哈希是否在该集合中非常有效。您的查询仅使用哈希集实现 IEnumerable 的事实来迭代整个集合并进行日期比较。它根本不会使用哈希值。这就是为什么手动方式与查询花费相同时间的原因。

您无法从哈希集中获取基于哈希的元素，只能测试该元素在集合中是否存在。 如果你需要通过 has 来获取它，那么字典就是你想要的（看来你不需要）

确定您需要如何处理数据，并使用为此优化的结构。这可能是您自己的类，它维护多个内部结构，每个内部结构在一件事情上都很有效（例如一个用于搜索范围，另一个用于通过多个字段的存在性进行检查），或者可能有一个适合您需求的现有结构。但如果不知道您想用数据做什么，就很难给出建议。

另一件需要考虑的事情是你是否过早地进行优化。如果 25ms 手动搜索足够快，那么也许任何实现 IEnumerable 的结构都足够好。在这种情况下，您可以根据您需要的其他标准来选择一个。