Informatica I - la struttura dati Tabella hash con bucket

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. Una seconda limitazione della tabella è che 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

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
• 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 simboli diversi che per la codifica Unicode è 2¹⁶ = 65536.

Problema dell'intervallo di variabilità delle chiavi

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.