vuoi
o PayPal
tutte le volte che vuoi
Introduzione a una nuova struttura dati
Introduciamo una nuova struttura dati che ci permette di superare entrambe le limitazioni di una tabella realizzata tramite array.
Limitazioni della tabella:
- Le chiavi devono essere numeri interi in un intervallo prefissato
Introdurremo una funzione di hash che assegna dei valori numerici (interi in un intervallo prefissato) a delle chiavi generiche.
Seconda limitazione della tabella:
- La memoria non viene utilizzata in maniera efficiente
Useremo un array di bucket ("secchi"), cosicché ogni indice dell'array possa essere associato a più elementi del dizionario.
Il Codice hash:
È una funzione che ha come dominio l'insieme delle chiavi generiche in esame e come codominio un sottoinsieme dei numeri interi.
In Java la classe Object mette a disposizione il metodo hashCode che restituisce un int con buone proprietà di distribuzione uniforme. Se il metodo hashCode non viene ridefinito, esso associa ad un oggetto un valore numerico calcolato in
base all'indirizzo dell'oggetto in memoria. L'esistenza di questo metodo rende possibile l'utilizzo di qualsiasi oggetto come chiave.) Un codice hash per stringhe trasforma una stringa in un numero Intero. (Ricordiamo il significato della notazione posizionale nella rappresentazione di un numero intero. Ciascuna cifra rappresenta un numero che dipende dal suo valore intrinseco e dalla sua posizione. Usiamo la stessa convenzione per una stringa, dove ogni carattere rappresenta un numero che dipende dal suo valore come carattere nella codifica Unicode e dalla sua posizione nella stringa. Il valore numerico associato ad una stringa è quindi calcolato in questo modo: Per la base spesso si usa un numero primo come valore di base (ad esempio 31), perché questo "mescola" bene i valori, ovvero stringhe diverse hanno con buona probabilità codici hash diversi. In alternativa la base sarà (come per la notazione posizionale di interi) il numero di caratteri possibili nella codifica Unicode.)Il numero di simboli diversi per la codifica Unicode è 2^16 = 65536.
C'è ancora un problema: l'intervallo di variabilità delle chiavi deve essere noto a priori per dimensionare la tabella.
Affrontiamo il problema in questo modo:
- Prefissiamo la dimensione della tabella in modo arbitrario
- Quindi definiamo di conseguenza l'intervallo di variabilità delle chiavi utilizzabili: il valore massimo consentito è la lunghezza della tabella
MAPPA DI COMPRESSIONE: È una funzione di trasformazione delle chiavi che modifica la funzione h in modo che tutti i valori numerici associati alle chiavi ricadano all'interno dell'intervallo prefissato.
Il codominio di h è il sottoinsieme [0, N - 1] dei numeri interi, dove N coincide con la dimensione della tabella.
FUNZIONE DI HASH: È la composizione delle funzioni h (codice hash) e h (mappa di compressione)
Una funzione di hash ha:
- Dominio: l'insieme delle chiavi
che identificano univocamente i dati da inserire nel dizionario
Codominio: l'insieme degli indici validi per accedere ad elementi della tabella
Il risultato dell'applicazione della funzione di hash ad una chiave si chiama chiave ridotta.
Una tabella che usa chiavi ridotte si chiama tabella hash (hash table).
Bucket in una tabella hash
HASH: Quando due elementi hanno chiavi diverse ma uguali chiavi ridotte.
Per come è definita, una funzione di hash è generalmente non biunivoca perché il dominio ha dimensione maggiore del codominio.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
