obtener - lista de diccionarios python

Hashing un diccionario inmutable en Python

Question

Versión 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 las collections.Counter clases de la biblioteca estándar. Encuentro , similar al consejo aquí: Python hashable dicts , que recomienda una función hash así:

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

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:

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

Me imagino que usar XOR a nivel de bit significa que el orden no importa para el valor de hash a diferencia del hash de una tupla. Supongo que podría semi-implementar el algoritmo Python tuple-hashing en el flujo desordenado de tuplas de mis datos. Consulte https://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 se está preguntando por qué estoy tratando de hacer un hash de un conjunto múltiple: 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 Pythonic de asegurarme de que tengo algo único es ponerlos en un set() , pero las cosas deben ser hashable.

Lo que he recogido de los comentarios.

Tanto @marcin como @senderle dieron prácticamente la misma respuesta: usar hash(frozenset(self.items())) . Esto tiene sentido porque los items() "vistas" son como conjuntos . @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 que incluya un método __eq__ , pero el heredado de dict funcionará bien. Así es como lo estoy implementando todo: son bienvenidos los comentarios y sugerencias adicionales basados ​​en este código:

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

Answer 1

¿Has considerado el hash(sorted(hash(x) for x in self.items())) ? De esa manera, solo está ordenando enteros, y no tiene que construir una lista.

También podrías juntar los elementos de hashes, pero francamente no sé qué tan bien funcionaría (¿tendrías muchas colisiones?). Hablando de colisiones, ¿no tienes que implementar el método __eq__ ?

Alternativamente, de forma similar a mi respuesta here , hash(frozenset(self.items())) .

Answer 2

Dado que el diccionario es inmutable, puede crear el hash cuando se crea el diccionario y devolverlo directamente. Mi sugerencia sería crear un frozenset partir de items (en 3+; iteritems en 2.7), hacer hash y almacenar el hash.

Para proporcionar un ejemplo explícito:

>>>> frozenset(Counter([1, 1, 1, 2, 3, 3, 4]).iteritems())
frozenset([(3, 2), (1, 3), (4, 1), (2, 1)])
>>>> hash(frozenset(Counter([1, 1, 1, 2, 3, 3, 4]).iteritems()))
-3071743570178645657
>>>> hash(frozenset(Counter([1, 1, 1, 2, 3, 4]).iteritems()))
-6559486438209652990

Para aclarar por qué prefiero un frozenset a una tupla de elementos ordenados: un frozenset no tiene que ordenar los elementos (porque están ordenados de forma estable por su hash en la memoria), por lo que el hash inicial debe completarse en O (n) en lugar de O (n log n) tiempo. Esto se puede ver en las implementaciones frozenset_hash y set_next .