[Python] Dubbi su hash e set

enrico franchi enrico.franchi a gmail.com
Dom 4 Maggio 2008 19:08:31 CEST


2008/5/4 Pietro Battiston <toobaz a email.it>:
> -----BEGIN PGP SIGNED MESSAGE-----
>  Hash: SHA1
>
>  enrico franchi ha scritto:
>
> > On Fri, May 2, 2008 at 8:46 PM, Pietro Battiston <toobaz a email.it> wrote:
>  >
>  >>  Ora, la mia coscienza sporca mi suggerisce che forse quando ho
>  >>  sovrascritto __hash__ ho fatto più di quanto dovrebbe fare uno che di
>  >>  internal Python non ne sa abbastanza, e che le hash di tutti gli
>  >>  oggetti che conosco sono (solitamente) univoche. Ma...
>  >
>  > Non è questione di internals. E' questione di algoritmi. Devi definire
>  > una funzione (quasi) univoca sugli oggetti che a te interessano.
>  > La proprietà è che se hash(x) == hash(y) per te x e y devono essere
>  > uguali e che possibilmente se devono essere diversi non abbiano lo
>  > stesso hash (che vuole dire "è estremamente poco probabile che...").
>
>  OK, allora i miei scrupoli erano ingiustificati e stavo effettivamente
>  agendo "legalmente". Quindi?!
>
>
>  >>  "not necessarily true" non significa che dovrebbe alla fine fregarsene
>  >>  se in un insieme due elementi distinti (e peraltro identici in tutto
>  >>  tranne l'allocazione di memoria) hanno la stessa hash?!
>  >
>  > Dice chiaramente: due valori con lo stesso valore hanno anche lo stesso
>  hash,
>  > due valori con diverso hash potrebbero avere lo stesso valore (o anche
>  > no). E' frequente: per esempio se crei una classe "vuota" tutte le sue
>  > istanze avranno lo stesso hash (se la prova non mi inganna).
>
>  In realtà qualche osservazione empirica mi fa pensare che in caso di
>  __hash__ non definita, hash(x) = id(x). Comunque ho afferrato il concetto.

Si, hai ragione tu, presente quando uno pensa una cosa e ne scrive
un'altra (e ho pure fatto l'esperimento). Vabbè.

Comunque non è che __hash__ non è definita, poichè viene ereditata da object.
Ed in effetti id è un buon candidato per essere un valore di hash di
default, visto e considerato che:
1. non cambia durante la vita dell'oggetto
2. è sempre univoco.

Peccato che sia 'troppo' univoco. Due oggetti sensatamente uguali
risultano con hash diverso, che non è quello che vuoi per usarli come
chiavi di un dizionario.

Comunque confermo quello che ha scritto altrove Daniele: devi definire
anche __eq__ oppure __cmp__.
Quello risolverà i tuoi problemi.

Stilisticamente aggiungo: trovo spesso e volentieri poco saggio
ereditare da classi built-in che non necessariamente sono state
pensate per questo scopo. Hai spesso sorprese di vario genere e devi
stare venti volte più attento che usando semplice contenimento.

class my_list(list):
    pass


s1 = my_list()
s2 = my_list()
s3 = s1 + s2

print "s3:", type(s3)
-> list

Per dire. Questa è una cosa difficile da prevedere e può romperti di
brutto il codice. Con set pare essere più robusto ma "è culo". Io
fossi in te penserei il tutto in termini di contenimento, scrivi
pochissimo codice in più, ma hai molto più controllo e meno sorprese.


-- 
-enrico


Maggiori informazioni sulla lista Python