C# HashSet<T>搜索性能（与ObservableCollection<T>相比）？

Question

C#泛型HashSet<T>的搜索性能应该是O(1)，ObservableCollection<T>的搜索性能应该是O(n)。

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

每个元素通过简单地返回其DateTime.GetHashCode()来计算其HashCode。

现在我想获取我的数据的子集，例如所有日期在2012年3月到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查询，它需要大约25毫秒来返回80个在给定范围内的元素 - 使用HashSet<T>或ObservableCollection<T>都没有影响。

如果我手动循环遍历所有元素并检查它们，需要相同的时间，大约25毫秒。

但是我知道所有在给定范围内的日期的HashCode。是否可以从我的HashSet<T>中获取具有给定HashCode的所有元素？我认为这样会快得多...

有可能加速LINQ查询吗？我假设它没有利用我的HashSet<T>的特殊能力？

- Ehssan

---

每个元素的哈希码是它的日期吗？ - Jodrell

哦，另外需要注意的是，this.elements 是你所说的哈希集合吗？从问题中不太清楚... - Chris

如果你有300,000个元素，你是从数据库中提取它们吗？如果是这样，你可以仅获取正确日期范围内的项目，这应该会更快。 - jb.

不，这些元素并不来自数据库。我只是问一下，因为在通用的 HashSet 中搜索性能应该是 O(1)，但是 LINQ 查询（以及我的查询）执行的时间复杂度为 O(n)。哦，还有要提一下的是：有很少的元素具有相同的哈希码... - Ehssan

正如已经指出的那样，@EhssanDoust，当您执行linq查询时，并没有通过哈希值进行搜索，而是仅在IEnumerable上进行搜索，并比较“Date”属性（在您的情况下，这只是用于生成哈希的元素）。 您知道HashSet 无法根据哈希检索元素，对吗？请参见此处。 您确实需要使用不同的数据结构。 - Sam Holder

Answer 1

你没有使用正确的数据结构。你应该使用类似于排序列表（按Date属性排序）的东西，然后可以进行二分搜索来查找范围的开始和结束。

- jason

---

是的，我肯定会使用SortedList或SortedDicionary，但我不能 - 元素的“日期”不是唯一的键... - Ehssan

@EhssanDoust，为什么日期不唯一会阻止您使用字典？只要Equals方法能正确地确定两个实例是否相等，并且如果这些对象之间的equals也为true，gethashcode始终为2个不同的对象返回相同的值，则它就可以正常工作。 - Sam Holder

@SamHolder 我不确定我是否正确理解了你的意思，但如果我想要通过日期在字典中高效地搜索元素，那么字典的键应该是该日期，对吗？但是我的集合中很少有不唯一的日期... 所以我不能将它们用作键？ - Ehssan

@EhssanDoust 对不起，我理解能力有误。我忘记你只有一个日期而不是完整的对象。像Jason建议的那样，排序后的列表应该是可以的，因为列表可以有多个具有相同键的元素。所以找到第一个具有所需日期的元素的索引，然后找到最后一个日期的元素的索引，最后获取这些索引之间的所有元素。 - Sam Holder

Answer 2

正如所指出的，哈希集非常高效地确定给定哈希是否在集合中。您的查询只是利用了哈希集实现IEnumerable以遍历整个集合并进行日期比较。它根本不会使用哈希。这就是为什么手动方式与查询需要相同时间的原因。

您无法根据哈希从哈希集获取元素，您只能测试元素是否存在于集合中。如果您需要按哈希获取它（似乎您不需要），则需要字典。

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

另一件要考虑的事情是您是否过早地进行了优化。如果手动搜索25毫秒足够快，则任何实现IEnumerable的结构都可能足够好。在这种情况下，您可以根据其他需要选择其中之一。

- Sam Holder

---

谢谢您的回答。我认为当前的搜索性能已经足够了，只是想知道是否可能通过其哈希码直接检索元素，但正如您所指出的那样并不可行。HashSet<T> 的 Remove 方法比任何“普通”集合提供的方法都要更高效，所以我肯定会使用 HashSet。 - Ehssan