Qual è un modo corretto e valido per implementare __hash __()?

Question

Qual è un modo corretto e valido per implementare __hash__()?

Sto parlando della funzione che restituisce un hashcode che viene poi utilizzato per inserire oggetti in dizionari aka di hashtables.

Come __hash__() restituisce un numero intero e viene utilizzato per "binning" oggetti in hashtables. Suppongo che i valori del numero intero restituito debbano essere distribuiti uniformemente per dati comuni (per ridurre al minimo le collisioni). Qual è una buona pratica per ottenere tali valori? Le collisioni sono un problema? Nel mio caso ho una piccola classe che agisce come una classe contenitore che contiene alcuni ints, alcuni float e una stringa.

Answer 1

Un modo semplice e corretto per implementare __hash__() consiste nell'utilizzare una tupla di chiave. Non sarà veloce come un hash specializzato, ma se avete bisogno che allora probabilmente si dovrebbe implementare il tipo in C.

Ecco un esempio di utilizzo di una chiave per hash e l'uguaglianza:

class A(object): 
    def __key(self): 
     return (self.attr_a, self.attr_b, self.attr_c) 

    def __eq__(x, y): 
     return x.__key() == y.__key() 

    def __hash__(self): 
     return hash(self.__key()) 

Inoltre, lo documentation of __hash__ ha più informazioni, che possono essere utili in alcune circostanze particolari.

Answer 2

A seconda della dimensione del valore di hash restituito. È semplice logica che se hai bisogno di restituire un int di 32 bit basato sull'hash di quattro 32 bit, avrai delle collisioni.

Preferisco le operazioni bit. Come, il seguente codice C pseudo:

int a; 
int b; 
int c; 
int d; 
int hash = (a & 0xF000F000) | (b & 0x0F000F00) | (c & 0x00F000F0 | (d & 0x000F000F); 

Un tale sistema potrebbe funzionare per carri anche se semplicemente le hanno ispirate come il loro valore di bit piuttosto che in realtà rappresenta un valore a virgola mobile, forse meglio.

Per gli archi, ho poca o nessuna idea.

Answer 3

Posso provare a rispondere alla seconda parte della domanda.

Le collisioni probabilmente non deriveranno dal codice hash stesso, ma dalla mappatura del codice hash in un indice in una raccolta. Quindi, ad esempio, la tua funzione di hash potrebbe restituire valori casuali da 1 a 10000, ma se la tua tabella hash ha solo 32 voci riceverai collisioni al momento dell'inserimento.

Inoltre, penserei che le collisioni verrebbero risolte dalla collezione internamente e ci sono molti metodi per risolvere le collisioni. Il più semplice (e il peggiore) è dato da una voce da inserire all'indice i, da 1 a 1 finché non trovi uno spazio vuoto e inserisci lì. Il recupero quindi funziona allo stesso modo. Ciò si traduce in recuperi non efficienti per alcune voci, in quanto si potrebbe avere una voce che richiede di attraversare l'intera collezione per trovare!

Altri metodi di risoluzione collisione riducono il tempo di recupero spostando le voci nella tabella hash quando un elemento viene inserito per distribuire le cose. Ciò aumenta il tempo di inserimento ma si presuppone che leggi più di quello che inserisci. Esistono anche metodi che provano e diramano diverse voci in collisione in modo che le voci vengano raggruppate in un punto particolare.

Inoltre, se è necessario ridimensionare la raccolta, sarà necessario ripetere tutto o utilizzare un metodo di hashing dinamico.

In breve, a seconda di cosa si sta utilizzando il codice hash, potrebbe essere necessario implementare il proprio metodo di risoluzione delle collisioni.Se non li stai salvando in una raccolta, puoi probabilmente farla franca con una funzione hash che genera solo codici hash in una gamma molto ampia. Se è così, puoi assicurarti che il tuo contenitore sia più grande di quello che deve essere (più grande è, meglio è, ovviamente) a seconda dei tuoi problemi di memoria.

Ecco alcuni link se siete interessati più:

coalesced hashing on wikipedia

Wikipedia ha anche una summary dei vari metodi di risoluzione di collisione:

Inoltre, "File Organization And Processing" di Tharp copre un sacco di collisione metodi di risoluzione ampiamente. IMO è un ottimo riferimento per gli algoritmi di hashing.

Answer 4

Paul Larson di Microsoft Research ha studiato un'ampia gamma di funzioni di hash. Mi ha detto che

for c in some_string: 
    hash = 101 * hash + ord(c) 

ha funzionato sorprendentemente bene per un'ampia varietà di stringhe. Ho trovato che tecniche polinomiali simili funzionano bene per calcolare un hash di sottocampi diversi.

Answer 5

John Millikin ha proposto una soluzione simile a questo:

class A(object): 

    def __init__(self, a, b, c): 
     self._a = a 
     self._b = b 
     self._c = c 

    def __eq__(self, othr): 
     return ((self._a, self._b, self._c) == 
       (othr._a, othr._b, othr._c)) 

    def __hash__(self): 
     return hash((self._a, self._b, self._c)) 

Il problema di questa soluzione è che il hash(A(a, b, c)) == hash((a, b, c)). In altre parole, l'hash si scontra con quello della tupla dei suoi membri chiave. Forse questo non importa molto spesso nella pratica?

La Python documentation on __hash__ suggerisce di combinare gli hash dei sub-componenti utilizzando qualcosa come XOR, che ci dà questa:

class B(object): 

    def __init__(self, a, b, c): 
     self._a = a 
     self._b = b 
     self._c = c 

    def __eq__(self, othr): 
     return (isinstance(othr, type(self)) 
       and (self._a, self._b, self._c) == 
        (othr._a, othr._b, othr._c)) 

    def __hash__(self): 
     return (hash(self._a)^hash(self._b)^hash(self._c)^
       hash((self._a, self._b, self._c))) 

Bonus: più robusta __eq__ gettato lì dentro per buona misura.

Aggiornamento: come sottolinea Blckknght, la modifica dell'ordine di a, b, e c potrebbe causare problemi. Ho aggiunto un ulteriore ^ hash((self._a, self._b, self._c)) per acquisire l'ordine dei valori sottoposti a hash. Questa finale ^ hash(...) possono essere rimossi se i valori essendo associati non possono essere riorganizzati (per esempio, se hanno diversi tipi e quindi il valore di _a non verrà mai assegnato a _b o _c, ecc).