title: Hashing an immutable dictionary in Python
body: <p><strong>Short version:</strong> What's the best hashing  algorithm for a multiset implemented as a dictionary of unordered items?</p>
  
  <p>I'm trying to hash an immutable multiset (which is a bag or multiset in other languages: like a mathematical set except that it can hold more than one of each element) implemented as a dictionary. I've created a subclass of the standard library class <code>collections.Counter</code>, similar to the advice here: <a href="https://stackoverflow.com/questions/1151658/python-hashable-dicts">Python hashable dicts</a>, which recommends a hash function like so:</p>
  
  <pre class="lang-python prettyprint-override"><code>class FrozenCounter(collections.Counter):
      # ...
      def __hash__(self):
          return hash(tuple(sorted(self.items())))
  </code></pre>
  
  <p>Creating the full tuple of items takes up a lot of memory (relative to, say, using a generator) and hashing will occur in an extremely memory intensive part of my application. More importantly, my dictionary keys (multiset elements) probably won't be order-able.</p>
  
  <p>I'm thinking of using this algorithm:</p>
  
  <pre class="lang-python prettyprint-override"><code>def __hash__(self):
      return functools.reduce(lambda a, b: a ^ b, self.items(), 0)
  </code></pre>
  
  <p>I figure using bitwise XOR means <strong>order doesn't matter for the hash value unlike in the hashing of a tuple?</strong> I suppose I could semi-implement the Python tuple-hashing alogrithm on the unordered stream of tuples of my data. See <a href="https://github.com/jonashaag/cpython/blob/master/Include/tupleobject.h" rel="noreferrer">https://github.com/jonashaag/cpython/blob/master/Include/tupleobject.h</a> (search in the page for the word 'hash') -- but I barely know enough C to read it.</p>
  
  <p><strong>Thoughts? Suggestions? Thanks.</strong>
  <hr />
  (<em>If you're wondering why I'm messing around with trying to hash a multiset:</em> The input data for my problem are sets of multisets, and within each set of multisets, each multiset must be unique. I'm working on a deadline and I'm not an experienced coder, so I wanted to avoid inventing new algorithms where possible. It seems like the most Pythonic way to make sure I have unique of a bunch of things is to put them in a <code>set()</code>, but the things must be hashable.)
  <hr /></p>
  
  <h1>What I've gathered from the comments</h1>
  
  <p>Both @marcin and @senderle gave pretty much the same answer: use <code>hash(frozenset(self.items()))</code>. This makes sense because <a href="http://docs.python.org/py3k/library/stdtypes.html#dictionary-view-objects" rel="noreferrer"><code>items()</code> "views" are set-like</a>. @marcin was first but I gave the check mark to @senderle because of the good research on the big-O running times for different solutions. @marcin also reminds me to <a href="http://docs.python.org/py3k/reference/datamodel.html#object.__hash__" rel="noreferrer">include an <code>__eq__</code> method</a> -- but the one inherited from <code>dict</code> will work just fine. This is how I'm implementing everything -- further comments and suggestions based on this code are welcome:</p>
  
  <pre class="lang-python prettyprint-override"><code>class FrozenCounter(collections.Counter):
      # Edit: A previous version of this code included a __slots__ definition.
      # But, from the Python documentation: "When inheriting from a class without
      # __slots__, the __dict__ attribute of that class will always be accessible,
      # so a __slots__ definition in the subclass is meaningless."
      # http://docs.python.org/py3k/reference/datamodel.html#notes-on-using-slots
      # ...
      def __hash__(self):
          "Implements hash(self) -&gt; int"
          if not hasattr(self, '_hash'):
              self._hash = hash(frozenset(self.items()))
          return self._hash
  </code></pre>