在 C# 中实现内容可哈希的 HashSet(如 python 的“冻结集”)

本文关键字：python 冻结 冻结集 HashSet 实现 哈希 | 更新日期: 2023-09-27 18:32:11

>简要总结

我想用 C# 构建一组项目。内部项集具有由其内容定义的GetHashCode和Equals方法。在数学符号中：

x = { }
x.Add( { A, B, C } )
x.Add( { A, D } )
x.Add( { B, C, A } )
now x should be{ { A, B, C }, { A, D } }

在python中，这可以通过frozenset来实现：

x = set()
x.add( frozenset(['A','B','C']) )
x.add( frozenset(['A','D']) )
x.add( frozenset(['B','C','A']) )

/简要摘要

我想在 C# 中有一个可哈希的哈希集。这将允许我执行以下操作：

HashSet<ContentHashableHashSet<int>> setOfSets;

尽管有更复杂的方法可以实现这一点，但这在实践中可以通过添加覆盖ContentHashableHashSet.ToString()（输出按排序顺序包含的元素的字符串）然后使用 then 使用 ContentHashableHashSet.ToString().GetHashCode() 作为哈希代码来实现（尽管不是最有效的方式）。

但是，如果在放置在 setOfSets 中后修改对象，则可能会导致多个副本：

var setA = new ContentHashableHashSet<int>();
setA.Add(1);
setA.Add(2);
var setB = new ContentHashableHashSet<int>();
setB.Add(1);
setOfSets.Add(setA);
setOfSets.Add(setB);
setB.Add(2); // now there are duplicate members!

据我所知，我有两个选择：我可以从HashSet派生ContentHashableHashSet，但随后我需要这样做，以便所有修饰符都抛出异常。缺少一个修饰符可能会导致一个阴险的错误。

或者，我可以使用封装和类ContentHashableHashSet可以包含一个readonly HashSet。但是接下来我需要重新实现所有设置方法（修饰符除外），以便ContentHashableHashSet可以像HashSet一样运行。据我所知，延期将不适用。

最后，我可以如上所述进行封装，然后所有类似集合的功能都将通过返回 const（或只读？哈希集成员。

事后看来，这让人想起蟒蛇的frozenset。有谁知道在 C# 中实现这一点的设计良好的方法？

如果我能够丢失ISet功能，那么我将简单地创建一个排序ImmutableList，但随后我将失去快速联合、快速交集和亚线性（大致 O（log（n）） 集成员资格等功能Contains。

编辑：基类HashSet没有虚拟Add和Remove方法，因此重写它们将在派生类中工作，但如果执行HashSet<int> set = new ContentHashableHashSet<int>();则不起作用。强制转换为基类将允许编辑。

编辑2：感谢@xanatos推荐一个简单的GetHashCode实现：

计算 GetHashCode 的最简单方法是简单地对元素的所有 gethashcode 进行 xor （^）。异或运算符是可交换的，因此排序无关紧要。为了进行比较，您可以使用 SetEquals

编辑3：最近有人分享了有关ImmutableHashSet的信息，但由于此类是密封的，因此无法从中派生并覆盖GetHashCode。

我还被告知HashSet将IEqualityComparer作为参数，因此这可以用来提供一个不可变的、内容可哈希集，而无需从 ImmutableHashSet 派生;然而，这不是一个非常面向对象的解决方案：每次我想使用 ContentHashableHashSet 时，我都需要传递相同的（非平凡）参数。我相信你知道，这真的会对你的编码禅宗造成严重破坏，而且我会和myDictionary[ frozenset(mySet) ] = myValue一起在python中飞翔，我会一次又一次地做同样的事情。

感谢您提供的任何帮助。我有一个临时解决方法（其问题在上面的 EDIT 1 中提到），但我主要想了解设计这样的东西的最佳方式。

在 C# 中实现内容可哈希的 HashSet(如 python 的“冻结集”)

隐藏集合的元素，以便无法更改它们。这意味着在添加/检索集时进行复制，但也许这是可以接受的？

// Better make sure T is immutable too, else set hashes could change
public class SetofSets<T>
{
    private class HashSetComparer : IEqualityComparer<HashSet<T>>
    {
        public int GetHashCode(HashSet<T> x)
        {
            return x.Aggregate(1, (code,elt) => code ^ elt.GetHashCode());
        }
        public bool Equals(HashSet<T> x, HashSet<T> y)
        {
            if (x==null)
                return y==null;
            return x.SetEquals(y);
        }
    }
    private HashSet<HashSet<T>> setOfSets;
    public SetofSets()
    {
        setOfSets = new HashSet<HashSet<T>>(new HashSetComparer());
    }
    public void Add(HashSet<T> set)
    {
        setOfSets.Add(new HashSet<T>(set));
    }
    public bool Contains(HashSet<T> set)
    {
        return setOfSets.Contains(set);
    }
}
相关文章：