Hashing un dizionario immutabile in Python

Question

Versione corta: Qual è l'algoritmo di hashing migliore per un multiset implementato come dizionario di elementi non ordinati?

Sto tentando di eseguire l'hash di un multiset immutabile (che è una borsa o un multiset in altre lingue: come un set matematico tranne che può contenere più di uno di ciascun elemento) implementato come dizionario. Ho creato una sottoclasse della classe libreria standard collections.Counter, simile al consiglio qui: Python hashable dicts, che raccomanda una funzione di hash in questo modo:

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

Creare la piena tupla di elementi prende un sacco di memoria (relativa per dire, usando un generatore) e l'hashing si verificherà in una parte estremamente intensiva della mia applicazione. Ancora più importante, le mie chiavi di dizionario (elementi multiset) probabilmente non saranno ordinabili.

Sto pensando di utilizzare questo algoritmo:

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

Immagino utilizzando XOR bit a bit significa ordine non conta per il valore hash a differenza del hash di una tupla? Suppongo che potrei semi-implementare il Python tuple-hashing alogrithm sul flusso ordinato di tuple dei miei dati. Vedere https://github.com/jonashaag/cpython/blob/master/Include/tupleobject.h (di ricerca nella pagina per la parola 'hash') - ma io a malapena so abbastanza C per leggerlo.

Pensieri? Suggerimenti? Grazie.

---

( Se vi state chiedendo perché sto nei guai con il tentativo di hash un multiset: I dati di input per il mio problema sono insiemi di multinsiemi, e all'interno di ogni serie di multinsiemi, ogni multinsieme deve essere univoco io. Sto lavorando a una scadenza e non sono un programmatore esperto, quindi volevo evitare di inventare nuovi algoritmi, laddove possibile. Sembra che il modo più Python per assicurarmi di avere un sacco di cose è metterli in una set(), ma le cose devono essere hashable.)

---

quello che ho raccolto dai commenti

Sia @marcin e @senderle ha dato più o meno la stessa risposta: utilizzare hash(frozenset(self.items())). Questo ha senso perché items() "views" are set-like. @marcin è stato il primo a dare il segno di spunta a @senderle a causa della buona ricerca sui tempi di esecuzione di big-O per soluzioni diverse. @marcin mi ricorda anche include an __eq__ method - ma quello ereditato dalla dict funzionano bene. Questo è come sto implementando tutto - ulteriori commenti e suggerimenti basati su questo codice sono benvenuti:

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

Dal momento che il dizionario è immutabile, è possibile creare l'hash quando viene creato il dizionario e restituirlo direttamente. Il mio suggerimento sarebbe quello di creare un frozenset da items (in 3+; iteritems in 2.7), hash, e memorizzare l'hash.

Per fornire un esempio esplicito:

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

di chiarire perché preferisco un frozenset ad una tupla di elementi ordinati: un frozenset non deve ordinare gli elementi (perché sono stabilmente in ordine di loro hash in memoria), e quindi l'hash iniziale dovrebbe essere completato in tempo O (n) anziché O (n log n).Questo può essere visto dalle implementazioni frozenset_hash e set_next.

Answer 2

Avete considerato hash(sorted(hash(x) for x in self.items()))? In questo modo, stai solo ordinando numeri interi e non devi creare un elenco.

Si potrebbe anche xorare l'elemento hash insieme, ma sinceramente non so quanto possa funzionare (si potrebbero avere molte collisioni?). A proposito di collisioni, non è necessario implementare il metodo __eq__?

In alternativa, simile alla mia risposta here, hash(frozenset(self.items())).