@Nippolo, non passeresti l'esame di ‘algoritmi e strutture dati’ ;-)
la collisione avviene nel seguente caso:
siano date 2 chiavi (ad esempio 2 stringhe) DIVERSE ovviamente: k1 e k2.
Per ogni chiave applichi la funzione hash: hash(k1), hash(k2)
E' possibile che hash(k1) sia uguale ad hash(k2) ma questo avviene con bassissima probabilita' se il numero delle chiavi e mooooolto piu' piccolo nel numero di bit usato per rappresentare il valore hash, che e' un intero. Supponi di usare interi a 32 o 64 bit. Certo, se usi interi a 8 (256 possibili valori) o 16 bit (65536 possibili valori), la probabilita' di collisione e' decisamente piu' alta (maggiore con 8 bit ovviamente)
ora devi accedere al vettore delle liste di overflow di lunghezza N. Quello che fai e' accedere agli elementi
i1=hash(k1) modulo N
i2=hash(k2) modulo N
Qui puoi avere una collisione perche N e' molto piccolo. Ad esempio supponi che N sia 1, valore ragionevole per un dizionario vuoto. La collisione e' assicurata al 100%. Con N=2, la collisione e' assicurata al 50%. Quindi perche' non partire con N=1000'? si puo' anche fare, ma se metti nel dizionario un milione di elementi, e' ovvio che avrai delle collisioni: almeno 999000!
D'altra parte, fino a che ci sono pochi elementi nel dizionario, non serve avere N grande.
Quindi, poiche' hai una collisione MA le chiavi sono diverse, che fai? Ecco dove entra in gioco la lista di overflow: ti permette di gestire oggetti con chiavi DIVERSE ma che generano lo STESSO valore per
hash(k) modulo N
Dopo un po' le liste di overflow diventano molto lunghe e quindi fai una ricerca sequenziale (lenta). E' a questo punto che riorganizzi il dizionario con il vettore delle liste di overflow di lunghezza 2N. Questo ha come effetto quello di dimezzare, mediamente, la lunghezza delle liste.
Il caso di due oggetti con la STESSA chiave NON ESISTE: e' lo STESSO oggetto a cui e' stato cambiato il valore!
La chiave IDENTIFICA UNIVOCAMENTE l'oggetto: stessa chiave implica stesso oggetto!
Come noti, avevi scritto una cosa ‘quasi giusta' ;-)
Il concetto e': la funzione hash deve ritornare SEMPRE lo stesso valore se applicata alla STESSA chiave. Il problema delle collisioni lo si ha con
hash(k) modulo N
MA il valore di N puo' cambiare (e DEVE cambiare)
L'altro problema e' come calcolare la funzione hash di una stringa. Ci sono un'infinita' di modi che uno si puo' inventare
- usando shift e xor
- usando moltiplicazioni per un numero primo e somma
.
String.hashCode di Java usa il metodo 2.
Come dicevo, l'implementazione' abbastanza arzigogolata: ci sono un'infinita' di dettagli da tenere in considerazione
;-)