HashSet<T> 的性能如何（与 ObservableCollection<T> 相比）？

Question

我目前正在处理一个项目，需要管理大量唯一元素。每个元素有约20个属性，并且每个元素都有一个公共属性DateTime。

由于DateTime属性不是唯一的，所以我无法使用通用字典来存储我的数据。

目前我将这些元素放入ObservableCollection中，但是从集合中删除元素的性能非常慢，我等待了大约20秒才能从大约25,000个元素的集合中删除7,000个元素。

（搜索操作似乎非常高效，从300,000个未排序的元素中随机选择80个元素只需大约30毫秒）。

每个元素通过简单地返回DateTime.GetHashCode()来实现GetHashCode()方法。

我认为使用HashSet而不是ObservableCollection会显著提高我的性能，但似乎根本没有影响……

而使用通用字典则更糟糕……

如果元素具有“良好”的哈希函数（很少有相同哈希码的元素），那么HashSet不比ObservableCollection更强大吗？

- Ehssan

---

但是，如果根据帖子DateTime属性不唯一，为什么要使用该非唯一属性的GetHashCode()？ - Tigran

ObservableCollection和HashSet的用途不同。你开始使用ObservableCollection的原因是什么？你将它绑定到WPF或Silverlight控件了吗？HashSet提供基本操作（添加、删除、包含和大小）的常数时间性能。 - Martin

@Tigran，因为HashSet不是字典？HashSet中的所有项都是唯一的，但哈希码不是，所以.NET使用哈希码作为起始值来放置和搜索项。GetHashCode（）不能保证唯一性，它作为哈希键来均匀分布哈希集中的项。 - Val Bakhtin

你是否在“观察”ObservableCollection？你的“观察者”代码是否可能是性能问题的原因？当你删除时，我会被调用。 - n8wrl

如果删除项目较慢，你可以将项目标记为已删除，并仅向可观察集合添加。您可以尝试在集合中使用Tuple<Element,bool>，而不是Element；只要Tuple使用两个元素的哈希值，并且您始终通过Tuple<Element,false>进行搜索，那么您就不会匹配已删除的元素，因为其哈希值将已更改，即使它仍旧在同一桶中。当然，这意味着您的集合将不断增长，最终性能将降低... - Sam Holder

Answer 1

你需要重写对象的Equals方法。

因为HashSet使用一个内部IEqualityComparer实例，通常首先检查是否为（null），然后使用重写的Equals方法比较“非空”项和另一个项：

class MyObject
{
    public Guid Id { get; set; }

    public override bool Equals(object other)
    {
        if (other is MyObject)
        {
            // use the 'Id' property as identifier

            MyObject myObj = (MyObject)obj;
            return myObj.Id == this.Id;
        }

        // is not a 'MyObject' based object
        return base.Equals(other);
    }
}

你也可以使用字符串或其他可与你的对象进行比较的对象。

编辑：

所以你可以使用HashSet来代替OberservableCollection。最后一个集合类型通常较慢，因为在每个集合更改（添加、删除、清除、插入等）时会触发PropertyChanged和CollectionChanged事件。

- user432219

Answer 2

您可以通过减少变更通知来优化ObservableCollection的性能。我编写了一个自定义集合类——ItemCollection，具有更新机制（BeginUpdate/EndUpdate）：

  ItemCollection<Customer> customers = new ItemCollection<Customer>
  customers.BeginUpdate();
  customers.Add( new Customer( "Joe", "Smith" ) );
  customers.Add( new Customer( "Mary", "Jones" ) );
  customers.Add( new Customer( "Lisa", "Black" ) );
  customers.Add( new Customer( "Peter", "Brown" ) );
  customers.EndUpdate();

带有源代码的文章： 基于XAML的应用程序的演示模式.

- user687474

Answer 3

马塞尔的答案是正确的，但如果性能真的很重要，您可以稍微改进他的equals方法：

class MyObject
{
    public Guid Id { get; set; }

    public override bool Equals(object other)
    {
        MyObject myObj = obj as MyObject;

        if (myObj != null)
        {
            // use the 'Id' property as identifier
            return myObj.Id == this.Id;
        }

        // is not a 'MyObject' based object
        return base.Equals(other);
    }
}

通过这种方法，您可以避免检查对象是否为特定类型的昂贵函数两次，并仅调用一次并进行快速的空值检查。如果想了解更多信息，请查看Eric的这篇文章。

- Oliver