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

为什么 valueType.Equals(Object) 这么慢

需要注意的潜在问题之一是

ValueType.Equals

可以使用反射。如果值类型不覆盖相等成员，并且例如包含引用类型字段/属性（请参阅此 github 问题中的列表），它将使用反射来执行操作：

// if there are no GC references in this object we can avoid reflection
// and do a fast memcmp
if (CanCompareBitsOrUseFastGetHashCode(RuntimeHelpers.GetMethodTable(obj))) // MethodTable kept alive by access to object below
{
    return //...
}
 
FieldInfo[] thisFields = GetType().GetFields(BindingFlags.Instance | BindingFlags.Public | BindingFlags.NonPublic);

for (int i = 0; i < thisFields.Length; i++)
{
    object? thisResult = thisFields[i].GetValue(this);
    object? thatResult = thisFields[i].GetValue(obj);
    // ...
}

这显然是成本相对较高的操作。

缓解措施 - 在结构体上定义自定义

GetHashcode

和

Equals

或为集合提供自定义

IEqualityComparer

比较器。

另一个值得研究的点是调用

Equals

的时间。但这需要一个完整的再现器。

O(1)

是通过“良好”的哈希函数实现的，这会导致很少发生冲突，这可能不是您的数据的情况（或者只是您的数据有很多重复项）。

Answer 2

如果您只需要检查引用相等性，请使用使用 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);