克隆哈希集的有效方法?

如果你真的想要最有效的克隆方法 HashSet<T> ,您可以执行以下操作(但可能以维护性为代价)

1. 使用Reflector或Debugger精确计算 哈希集<t> 需要复制。您可能需要为每个字段递归地执行此操作。
2. 使用 Reflection.Emit 或者使用表达式树生成对所有字段进行必要复制的方法。可能需要调用复制每个字段值的其他生成方法。我们使用运行时代码生成,因为它是直接访问私有字段的唯一方法。
3. 使用 FormatterServices.GetUninitializedObject(...) 实例化一个空对象。使用步骤2中生成的方法将原始对象复制到新的空白对象。

编辑: 经过更仔细的检查,这似乎不是一个好主意,因为原始哈希集中少于60个元素,下面的方法看起来比创建新的哈希集慢。

免责声明: 这似乎有效,但如果要对克隆的哈希集进行序列化,您可能需要复制SerializationInfo m_siinfo,则风险由您自己承担。

我还遇到了这个问题并尝试了一下,下面您将发现一个扩展方法,它使用fieldinfo.getvalue和setvalue来复制所需的字段。它比使用散列集(IEnumerable)快,这在多大程度上取决于原始散列集中元素的数量。对于1000个元素,差异约为因子7。有100000个元素,大约是因子3。

还有其他的方法,可能会更快,但这已经摆脱了我目前的瓶颈。我试着使用ExpressionTrees和Emission,但遇到了障碍,如果我让他们工作,我会更新这篇文章。

using System;
using System.Collections.Generic;
using System.Reflection;
using System.Runtime.Serialization;

public static class HashSetExtensions
{
    public static HashSet<T> Clone<T>(this HashSet<T> original)
    {
        var clone = (HashSet<T>)FormatterServices.GetUninitializedObject(typeof(HashSet<T>));
        Copy(Fields<T>.comparer, original, clone);

        if (original.Count == 0)
        {
            Fields<T>.freeList.SetValue(clone, -1);
        }
        else
        {
            Fields<T>.count.SetValue(clone, original.Count);
            Clone(Fields<T>.buckets, original, clone);
            Clone(Fields<T>.slots, original, clone);
            Copy(Fields<T>.freeList, original, clone);
            Copy(Fields<T>.lastIndex, original, clone);
            Copy(Fields<T>.version, original, clone);
        }

        return clone;
    }

    static void Copy<T>(FieldInfo field, HashSet<T> source, HashSet<T> target)
    {
        field.SetValue(target, field.GetValue(source));
    }

    static void Clone<T>(FieldInfo field, HashSet<T> source, HashSet<T> target)
    {
        field.SetValue(target, ((Array)field.GetValue(source)).Clone());
    }

    static class Fields<T>
    {
        public static readonly FieldInfo freeList = GetFieldInfo("m_freeList");
        public static readonly FieldInfo buckets = GetFieldInfo("m_buckets");
        public static readonly FieldInfo slots = GetFieldInfo("m_slots");
        public static readonly FieldInfo count = GetFieldInfo("m_count");
        public static readonly FieldInfo lastIndex = GetFieldInfo("m_lastIndex");
        public static readonly FieldInfo version = GetFieldInfo("m_version");
        public static readonly FieldInfo comparer = GetFieldInfo("m_comparer");

        static FieldInfo GetFieldInfo(string name)
        {
            return typeof(HashSet<T>).GetField(name, BindingFlags.Instance | BindingFlags.NonPublic);
        }
    }
}

简单的模式 应该 不会 为许多收藏工作:

Class cloneableDictionary(Of T, U)
    Inherits Dictionary(Of T, U)
    Function clone() As Dictionary(Of T, U)
        Return CType(Me.MemberwiseClone, cloneableDict(Of T, U))
    End Function
End Class

不幸的是,我不知道微软做了什么来阻止在不应该调用它的地方调用MemberWiseClone(例如,用MemberWiseClone的名称声明一个方法以外的东西,比如一个类),所以我不知道如何判断这种方法是否可行。

我认为标准集合不支持公共克隆方法,而只支持受保护的方法是有正当理由的:如果克隆,从集合派生的类可能会严重中断;如果基类的克隆方法是公共的,则无法阻止派生类的对象被赋予预期的代码。克隆它。

尽管如此,如果.NET包含可克隆的医学类和标准类型之类的类,那就太好了。( 虽然显然不是 基本上如上文所述实施)。

我检查了两个版本的.NET框架源代码 4.5.2 版本 4.7.2 . 4.7.2版在构造函数中确实有优化功能,当传入的集合是散列集类型时,可以使用一些内部克隆逻辑进行处理。您还需要将比较器传递到构造函数中,这样逻辑才能工作。版本4.5.2似乎没有这种优化。

例子:

var clonedSet = new HashSet(set, set.Comparer);

从理论上讲,O(N)克隆尽可能好地克隆两个不会共享相同基础数据结构的集。

检查元素是否在哈希集中应该是一个常量时间(即o(1))操作。

因此,您可以创建一个包装器,它只包装一个现有的哈希集,并保留任何新的添加内容,但这似乎非常反常。

当你说“高效”时,你的意思是“比现有的O(N)方法更高效”——我假设,如果你不玩关于“克隆”含义的相当严肃的语义游戏,你就不能真正比O(N)更高效。

只是一个偶然的想法。这可能是愚蠢的。

因为它们没有实现ICloneable,并且构造函数也没有使用源是同一类型的知识,所以我想我们只剩下一个选项了。实现优化版本并将其作为扩展方法添加到类型中。

类似:

namespace ExtensionMethods
{
    public static class MyExtensions
    {
        public static HashSet<int> Clone(this HashSet<int> original)
        {
            HashSet<int> clone = new HashSet<int>();
            //your optimized code here 
            return clone;
        }
    }   
}

然后,问题中的代码如下所示:

HashSet<int> original = ...
HashSet<int> clone = HashSet<int>.Clone(original);