![]() ![]() |
Gli elenchi di dati sono tra le strutture informative più utilizzate. Il tipo di dati corrispondente è la Tabella
(Map) .
Una tabella rappresenta una successione di elementi (chiave, valore), dove la chiave (o chiave di ricerca) ha lo scopo di individuare univocamente il valore associato.
Matematicamente si tratta infatti di una funzione (mappa) surgettiva dall'insieme delle chiavi all'insieme dei valori.
Esempio un rubrica nomi indirizzi
Le principali operazioni su tabelle sono le seguenti:
Le tabelle sono una struttura dati estremamente importante e la ricerca di tecniche efficienti di memorizzazione e di gestione
costituisce uno dei problemi fondamentali dell'algoritmica concreta.
|
![]() ![]() |
L'interfaccia java.util.Map<K,V> specifica il tipo Map con chiavi di tipo
K e valori associati di tipo V
Per una descrizione esauriente si rimanda alla documentazione ufficiale, qui ci limitiamo a segnalare i metodi principali.
|
![]() ![]() |
Una implementazione banale delle tabelle potrebbe basarsi su un array di coppie (chiave, valore) che viene scandito
sequenzialmente con una complessità lineare nel numero di elementi, tale costo è tuttavia assolutamente inaccettabile per le tabelle di grandi dimensioni usate in pratica.
Un caso particolarmente fortunato è invece quando le chiavi sono numeri interi più piccoli della dimensione dell'array. In questo caso la complessità di inserzione, ricerca e cancellazione è sempre costante (pari a 1). Nella pratica si riesce ad approssimare il buon comportamento del secondo caso per insiemi qualsiasi di chiavi con una metodologia detta delle tabelle hash. Per memorizzare degli oggetti in una tabella di dimensione n (cioè con n posizioni, comprese tra 0 e n-1), si assegna ad ogni oggetto un numero intero i, detto codice hash, tra 0 e n-1 e lo si posiziona nell'i-esima posizione della tabella. La ricerca di un oggetto avviene calcolando il suo codice hash e quindi accedendo alla corrispondente posizione della tabella. La funzione che calcola il codice hash di un oggetto, detta funzione hash, deve soddisfare le seguenti proprietà:
La realizzazione più comune delle tabelle hash si basa sull'uso di array e un esempio semplice di funzione hash (da interi ''grandi'' a
interi ''piccoli'') è dato dall'operatore modulo con argomento la
dimensione dell'array:
L'uso delle funzioni hash introduce però il problema delle collisioni: due oggetti diversi possono infatti fornire lo stesso valore di funzione hash. Nel momento in cui vogliamo mappare insiemi possibilmente grandi di oggetti in interi di piccole dimensioni, le collisioni sono inevitabili e, in questo caso, è necessario scorrere tutti gli elementi con lo stesso codice hash alla ricerca di quello che interessa. La teoria delle tabelle hash fornisce tecniche di generazione della funzione hash e algoritmi di memorizzazione e ricerca che garantiscono operazioni efficienti con complessità costante, purché la dimensione della tabella sia sufficientemente grande rispetto al numero di oggetti da memorizzare. In pratica una occupazione minore del 75% è più che accettabile.
|
![]() ![]() |
La classe HashMap implementa tabelle con le tabelle hash.
Rispetto ad altre strutture dati con le stesse funzionalità (quali ad esempio gli alberi binari di ricerca) le tabelle hash non devono mantenere un ordine degli elementi memorizzati. Sono caratterizzate dal fatto che:
|