C#：HashSet：为什么 valueType.Equals(Object) 这么慢

Question

有了这个方法：

public void RunFD(object fileObj, ISet<object> visited)
{
    if (!visited.Add(fileObj)) return;

    if (fileObj is IEnumerable enumerablFileObj )
    {
        foreach (var aFileObj in enumerablFileObj.OfType<object>())
        {
            RunFD(aFileObj , visited);
        }
    }
    else
    {
        AddToFolder(fileObj);
    }
}

fileObj 是一个简单的对象，可以包含字符串或自定义对象。可能会出现Parent1 -> child -> Parent1的场景，因此使用名为visited的HashSet。这里，Parent1 指的是与另一个 Parent1 完全相同的实例。

尽管此方法按预期运行，但我注意到执行时间相当长。令人惊讶的是，大部分执行时间都花在了visited.Add(fileObj)上。

在执行过程中，观察到最耗时的操作是HashSet.AddIfNotPresent -> ObjectEqualityComparer.Equals -> ValueType.Equals(Object)，它占了我的方法总执行时间的95%。

我很困惑，因为我预计 HashSet 的时间复杂度一般为 O(1)，仅检查引用对象是否与另一个相同（这符合我的要求）。

考虑到我有多种类型的 fileObj 类，我是否应该为所有这些类重写 Equals 方法？有没有更有效的方法来检查对象是否相同？

我尝试寻找另一种解决方案，但唯一出现的解决方案是重载对象的 Equals 和 GetHashCode 方法。然而，这是非常痛苦的，因为我有很多可能的对象用于此方法..

Answer 1

如果您只需要检查引用相等性，请使用使用 ReferenceEquals 的自定义相等比较器：

public class ReferenceEqualityComparer<T> : IEqualityComparer<T> where T : class
{
    public static IEqualityComparer<T> Default { get {return new ReferenceEqualityComparer<T>();}}

    public bool Equals(T x, T y){ return ReferenceEquals(x, y); }
    public int GetHashCode(T obj) { return RuntimeHelpers.GetHashCode(obj); }
}

var visited = new HashSet<object>(ReferenceEqualityComparer<object>.Default);