Implementing a hashable by content HashSet in C # (e.g. python `frozenset`)

Question

Brief Summary

I want to create a set of element sets in C #. Internal element sets have the GetHashCode and Equals methods defined by their contents. In mathematical notation:

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

In python, this can be done using frozenset :

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

/ BriefSummary

I would like to have a hashable HashSet in C #. This would allow me to:

 HashSet<ContentHashableHashSet<int>> setOfSets; 

Although there are more complex ways to achieve this, this can be trivially achieved in practice (albeit not in the most efficient way) by adding an override to ContentHashableHashSet.ToString() (outputting strings from elements contained in sorted order) and then using then using ContentHashableHashSet.ToString().GetHashCode() as a hash code.

However, if the object was modified after being placed in setOfSets , this may result in several copies:

 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! 

As far as I can tell, I have two options: I can get the ContentHashableHashSet from the HashSet , but then I will need to make sure that all modifiers throw an exception. The absence of a single modifier can cause an insidious error.

Alternatively, I can use encapsulation, and the ContentHashableHashSet class may contain readonly HashSet . But then I will need to override all installed methods (except modifiers) so that the ContentHashableHashSet can behave like a HashSet . As far as I know, extensions will not apply.

Finally, I could encapsulate as above, and then an entire similar function would occur, returning a member of the HashSet const (or read-only?).

In retrospect, it resembles python frozenset . Does anyone know of a well-designed way to implement this in C #?

If I could lose ISet functionality, I would simply create a sorted ImmutableList , but then I would lose functionality such as quick union, fast intersection, and sublinear (roughly O (log (n))) establishes membership with Contains .

EDIT: The HashSet base class does not have virtual Add and Remove methods, so overriding them will work in the derived class, but will not work if you execute HashSet<int> set = new ContentHashableHashSet<int>(); . Casting to the base class will allow editing.

EDIT 2: Thanks to @xanatos for recommending a simple implementation of GetHashCode :

The easiest way to compute GetHashCode is to simply xor (^) all the gethashcodes of the elements. The xor operator is commutative; therefore, the ordering does not matter. For comparison you can use SetEquals

EDIT 3: Someone recently shared information about ImmutableHashSet , but since this class is sealed, it is impossible to deduce from it and override GetHashCode .

I was also told that the HashSet takes IEqualityComparer as an argument, and therefore it can be used to provide an immutable set of content that does not contain an ImmutableHashSet; however, this is not a very object-oriented solution: every time I want to use a ContentHashableHashSet , I will need to pass the same (non-trivial) argument. As I am sure, you know, this can really harm your Zen encoding, and where I will fly in python using myDictionary[ frozenset(mySet) ] = myValue , I will stick to the same thing over and over again .

Thanks for any help you can provide. I have a workaround (the problems of which are mentioned in EDIT 1 above), but I would like to know how best to create something like this.

Answer 1

Hide the elements of your collection set so that they cannot be changed. This means that you copy when you add / remove sets, but maybe this is acceptable?

 // 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); } }