Version corta: ¿Cuál es el mejor algoritmo de hash para un conjunto múltiple implementado como un diccionario de elementos desordenados?

Estoy intentando hacer un hash de un multiset inmutable (que es una bolsa o multiset en otros idiomas: como un conjunto matemático, excepto que puede contener más de uno de cada elemento) implementado como un diccionario. He creado una subclase de la clase de biblioteca estándarcollections.Counter, similar al consejo aquí:Python hashable dicts, que recomienda una función hash como tal:

<code>class FrozenCounter(collections.Counter):
    # ...
    def __hash__(self):
        return hash(tuple(sorted(self.items())))
</code>

La creación de la tupla completa de elementos requiere una gran cantidad de memoria (relativa a, por ejemplo, el uso de un generador) y el hashing se producirá en una parte de mi aplicación que requiere mucha memoria. Más importante aún, es probable que mis claves de diccionario (elementos de conjuntos múltiples) no sean ordenables.

Estoy pensando en usar este algoritmo:

<code>def __hash__(self):
    return functools.reduce(lambda a, b: a ^ b, self.items(), 0)
</code>

Me imagino usando medios XOR en modo bit¿El orden no importa para el valor de hash a diferencia del hashing de una tupla? Supongo que podría semi-implementar el algoritmo Python tuple-hashing en el flujo desordenado de tuplas de mis datos. Verhttps://github.com/jonashaag/cpython/blob/master/Include/tupleobject.h (busque en la página la palabra 'hash'), pero apenas conozco suficiente C para leerla.

¿Pensamientos? Sugerencias? Gracias.

(Si te estás preguntando por qué estoy perdiendo el tiempo intentando hacer un hash de un multiset: Los datos de entrada para mi problema son conjuntos de conjuntos múltiples, y dentro de cada conjunto de conjuntos múltiples, cada conjunto múltiple debe ser único. Estoy trabajando en una fecha límite y no soy un programador experimentado, así que quise evitar inventar nuevos algoritmos siempre que sea posible. Parece que la forma más pitónica de asegurarse de que tengo un montón de cosas únicas es ponerlas en unaset(), pero las cosas deben ser hashable.

Lo que he recogido de los comentarios.

Tanto @marcin como @senderle dieron prácticamente la misma respuesta: usehash(frozenset(self.items())). Esto tiene sentido porqueitems() Las "vistas" son como un conjunto. @marcin fue el primero, pero le di la marca de verificación a @senderle debido a la buena investigación sobre los grandes tiempos de ejecución para diferentes soluciones. @marcin también me recuerda queincluir una__eq__ método - pero el heredado dedict funcionará bien Así es como lo estoy implementando todo: son bienvenidos los comentarios y sugerencias adicionales basados ​​en este código:

<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) -> int"
        if not hasattr(self, '_hash'):
            self._hash = hash(frozenset(self.items()))
        return self._hash
</code>