title: Implementing a content-hashable HashSet in C# (like python's `frozenset`)
body: <p><strong>Brief summary</strong></p>
  
  <p>I want to build a set of sets of items in C#. The inner sets of items have a <code>GetHashCode</code> and <code>Equals</code> method defined by their <em>contents</em>. In mathematical notation:</p>
  
  <pre><code>x = { }
  x.Add( { A, B, C } )
  x.Add( { A, D } )
  x.Add( { B, C, A } )
  
  now x should be{ { A, B, C }, { A, D } }
  </code></pre>
  
  <p>In python, this could be accomplished with <code>frozenset</code>:</p>
  
  <pre><code>x = set()
  x.add( frozenset(['A','B','C']) )
  x.add( frozenset(['A','D']) )
  x.add( frozenset(['B','C','A']) )
  </code></pre>
  
  <p><strong>/BriefSummary</strong>
  <br><br></p>
  
  <p>I would like to have a hashable HashSet in C#. This would allow me to do:</p>
  
  <pre><code>HashSet&lt;ContentHashableHashSet&lt;int&gt;&gt; setOfSets;
  </code></pre>
  
  <p>Although there are more sophisticated ways to accomplish this, This can be trivially achieved in practice (although not in the most efficient manner) by adding overriding <code>ContentHashableHashSet.ToString()</code> (outputing the strings of the elements contained in sorted order) and then using then using <code>ContentHashableHashSet.ToString().GetHashCode()</code> as the hash code.</p>
  
  <p>However, if an object is modified after placement in <code>setOfSets</code>, it could result in multiple copies:</p>
  
  <pre><code>var setA = new ContentHashableHashSet&lt;int&gt;();
  setA.Add(1);
  setA.Add(2);
  var setB = new ContentHashableHashSet&lt;int&gt;();
  setB.Add(1);
  
  setOfSets.Add(setA);
  setOfSets.Add(setB);
  
  setB.Add(2); // now there are duplicate members!
  </code></pre>
  
  <p>As far as I can see, I have two options: I can derive <code>ContentHashableHashSet</code> from <code>HashSet</code>, but then I will need to make it so that all modifiers throw an exception. Missing one modifier could cause an insidious bug.</p>
  
  <p>Alternatively, I can use encapsulation and class <code>ContentHashableHashSet</code> can contain a <code>readonly HashSet</code>. But then I would need to reimplement all set methods (except modifiers) so that the <code>ContentHashableHashSet</code> can behave like a <code>HashSet</code>. As far as I know, extensions would not apply.</p>
  
  <p>Lastly, I could encapsulate as above and then all set-like functionality will occur by returning the const (or readonly?) HashSet member.</p>
  
  <p>In hindsight, this is reminiscent of python's <code>frozenset</code>. Does anyone know of a well-designed way to implement this in C#?</p>
  
  <p>If I was able to lose <code>ISet</code> functionality, then I would simply create a sorted <code>ImmutableList</code>, but then I would lose functionality like fast union, fast intersection, and sub-linear ( roughly O(log(n)) )  set membership with <code>Contains</code>.</p>
  
  <p><strong>EDIT:</strong> The base class HashSet does <em>not</em> have virtual <code>Add</code> and <code>Remove</code> methods, so overriding them will work within the derived class, but will <em>not</em> work if you perform <code>HashSet&lt;int&gt; set = new ContentHashableHashSet&lt;int&gt;();</code>. Casting to the base class will allow editing.</p>
  
  <p><strong>EDIT 2:</strong> Thanks to @xanatos for recommending a simple <code>GetHashCode</code> implementation: </p>
  
  <blockquote>
    <p>The easiest way to calculate the GetHashCode is to simply xor (^) all the gethashcodes of the elements. The xor operator is commutative, so the ordering is irrelevant. For the comparison you can use the SetEquals</p>
  </blockquote>
  
  <p><strong>EDIT 3:</strong> Someone recently shared information about <a href="http://blogs.msdn.com/b/bclteam/archive/2012/12/18/preview-of-immutable-collections-released-on-nuget.aspx" rel="nofollow">ImmutableHashSet</a>, but because this class is sealed, it is not possible to derive from it and override <code>GetHashCode</code>.</p>
  
  <p>I was also told that <code>HashSet</code> takes an <code>IEqualityComparer</code> as an argument, and so this can be used to provide an immutable, content-hashable set without deriving from ImmutableHashSet; however, this is not a very object oriented solution: every time I want to use a <code>ContentHashableHashSet</code>, I will need to pass the same (non-trivial) argument. As I'm sure you know, this can really wreak havoc with your coding zen, and where I would be flying along in python with <code>myDictionary[ frozenset(mySet) ] = myValue</code>, I will be stuck doing the same thing <a href="http://en.wikipedia.org/wiki/Sisyphus" rel="nofollow">again and again and again</a>. </p>
  
  <p>Thanks for any help you can provide. I have a temporary workaround (whose problems are mentioned in <strong>EDIT 1</strong> above), but I'd mostly like to learn about the best way to design something like this.</p>