0

简要总结

我想在 C# 中构建一组项目。项目的内部集合具有由它们的内容GetHashCode定义的andEquals方法。在数学符号中：

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']) )

/BriefSummary

我想在 C# 中有一个可散列的 HashSet。这将允许我这样做：

HashSet<ContentHashableHashSet<int>> setOfSets;

尽管有更复杂的方法来实现这一点，这可以通过添加覆盖ContentHashableHashSet.ToString()（输出包含在排序顺序中的元素的字符串）然后使用 then usingContentHashableHashSet.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!

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

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

最后，我可以像上面那样封装，然后通过返回 const（或只读？）HashSet 成员来实现所有类似集合的功能。

事后看来，这让人想起 python 的frozenset. 有谁知道在 C# 中实现这一点的精心设计的方法？

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

编辑：基类 HashSet 没有virtual和Add方法Remove，因此覆盖它们将在派生类中起作用，但如果执行HashSet<int> set = new ContentHashableHashSet<int>();. 转换为基类将允许编辑。

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

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

编辑 3：最近有人分享了有关ImmutableHashSet的信息，但是因为这个类是密封的，所以不可能从它派生并覆盖GetHashCode。

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

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

4

1 回答 1

1

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

// 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);
    }
}
于 2013-09-20T10:08:33.367 回答