Versão curta: Qual é o melhor algoritmo de hash para um multiset implementado como um dicionário de itens não ordenados?

Eu estou tentando hash um multiset imutável (que é um saco ou multiset em outras línguas: como um conjunto matemático, exceto que ele pode conter mais de um de cada elemento) implementado como um dicionário. Eu criei uma subclasse da classe de biblioteca padrãocollections.Counter, semelhante ao conselho aqui:Ditos hashtable do pitão, que recomenda uma função hash da seguinte forma:

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

Criar a tupla completa de itens consome muita memória (em relação a, digamos, usar um gerador) e o hash ocorrerá em uma parte extremamente intensiva de memória do meu aplicativo. Mais importante, minhas chaves de dicionário (elementos multiconjunto) provavelmente não serão ordenadas.

Estou pensando em usar esse algoritmo:

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

Eu acho que usando meios XOR bitwiseordem não importa para o valor de hash ao contrário do hash de uma tupla? Eu suponho que eu poderia semi-implementar o algoritmo hashing-Python no fluxo desordenado de tuplas de meus dados. Vejohttps://github.com/jonashaag/cpython/blob/master/Include/tupleobject.h (pesquise na página a palavra "hash") - mas mal conheço C suficiente para lê-lo.

Pensamentos? Sugestões? Obrigado.

(Se você está se perguntando por que eu estou brincando com o hash multiset: Os dados de entrada para o meu problema são conjuntos de multisets e, dentro de cada conjunto de multisets, cada multiconjunto deve ser exclusivo. Estou trabalhando em um prazo e não sou um programador experiente, portanto, evitei inventar novos algoritmos sempre que possível. Parece que a maneira mais pitônica de ter certeza de que eu tenho um monte de coisas é colocá-las em umset(), mas as coisas devem ser laváveis.)

O que eu juntei dos comentários

Ambos @marcin e @senderle deram praticamente a mesma resposta: usehash(frozenset(self.items())). Isso faz sentido porqueitems() "visualizações" são definidas como. O @marcin foi o primeiro, mas dei a marca de seleção ao @senderle por causa da boa pesquisa sobre os tempos de execução do big-O para soluções diferentes. @marcin também me lembraincluir um__eq__ método - mas o herdado dedict vai funcionar muito bem. É assim que estou implementando tudo - comentários e sugestões adicionais baseados neste código são bem-vindos:

<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>