Il tipo di dato Tabella (Map)

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

Mario RossiVia Verdi, 1
Carlo BianchiVia Garibaldi, 3
Anastasia RossiVia Verdi, 1
Giuseppe Garibaldi Via Bianchi, 37


Le principali operazioni su tabelle sono le seguenti:

  • Inserzione di una nuova coppia (chiave, valore).
  • Aggiornamento del valore associato ad una chiave.
  • Eliminazione di una coppia (chiave, valore).
  • Ricerca del valore associato ad una chiave.


 

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 Map<K,V>

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.

  • Il metodo
       V put(K key, V value) 
    
    associa il valore value alla chiave key, sostituendo il valore precedente se già presente, viene reso il valore precedente se già presente, null altrimenti.

  • Il metodo
       V get(Object key) 
    
    restituisce il valore associato alla chiave key, oppure null se la chiave non è presente. Può essere lanciata l'eccezione ClassCastException se key non è di un tipo compatibile.

  • Il metodo
      V remove(Object key) 
    
    rimuove la chiave key, e il valore associato se già presenti, viene reso il valore precedente se già presente, null altrimenti. Può essere lanciata l'eccezione ClassCastException se key non è di un tipo compatibile.

  • Il metodo
     boolean containsKey(Object key) 
    restituisce true se la map contiene un'associazione per la chiave data.

  • Il metodo
     boolean containsValue(Object value) 
    restituisce true se la map contiene una o più chiavi associate al valore dato.

  • Il metodo
       Set<K> keySet() 
    
    Restituisce un insieme (ovvero una Collection senza ripetizioni) che rappresenta le chiavi presenti nella tabella (ovviamente, senza ripetizioni).

  • Il metodo
       Collection<V> values() 
    
    Restituisce una Collection che rappresenta i valori presenti nella tabella (ovviamente, ogni valore compare tante volte quante è presente in tabella).

  • Il metodo
       Set<Map.Entry<K,V>> entrySet() 
    
    Restituisce una insieme di Map.Entry che rappresenta le coppie chiave - valore presenti nella tabella.

    Map.Entry è un "contenitore" che permette di stampare la coppia (attraverso il metodo toString implicito, o di accedere alla chiave o al valore con i metodi getKey() e getValue().

  • Inoltre, tra gli altri, vi sono i metodi:   clear(),   isEmpty(),   size(),   equals(),   dall'ovvio significato.



Le tabelle hash

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à:

  • essere semplice, per non appesantire l'esecuzione del programma;
  • mappare oggetti uguali in numeri uguali.

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:

 
        hashValue = (int) (x % arraySize)        

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

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:

  1. non richiedono che gli oggetti memorizzati realizzino l'interfaccia Comparable.
  2. riescono ad avere un tempo medio di accesso costante che le rende veloci in pratica;
  3. i relativi metodi sono semplici da programmare;
  4. qualora il numero degli elementi presenti nella tabella cresca eccessivamente la struttura deve essere ricostruita su un array di dimensioni maggiori.


La classe TreeMap

La classe TreeMap implementa tabelle attraverso un tipo particolare di alberi binari di ricerca bilanciati detti red-black trees.

Questa tecnica di memorizzazione è caratterizzata dal fatto che:

  1. le chiavi devono essere ordinabili, o implementando l'interfaccia Comparable oppure mediante uno specifico Comparator fornito al momento della creazione. Le chiavi vengono visitate nell'ordine crescente corrispondente;
  2. il costo dell'inserzione della ricerca e della cancellazione è dell'ordine del Logaritmo del numero di chiavi presenti;
  3. La cancellazione è più efficiente rispetto alle tabelle hash.
  4. non ci si deve preoccupare del numero degli elementi presenti nell'albero; la struttura cresce in modo naturale ed efficiente.



Esempio: calcolo di frequenze

Un esempio interessante che permette di vedere un'applicazione sia delle HashMap che delle TreeMap è il calcolo delle frequenze delle parole in un testo letterario.

Si tratta di un problema molto comune della linguistica computazionale che consiste nel determinare la frequenza delle singole parole in un testo letterario.

Ai fini statistici è anche interessante calcolare il numero di parole che hanno una determinata frequenza.

Si vuole scrivere un programma che dato un directory contenente un numero arbitrario di file di tipo .txt li legge uno dopo l'altro e calcola la frequenza cumulativa delle parole.

Successivamente si calcolano le coppie (x, y) dove x parole compaiono esattamente y volte e viene scritto quest'ultimo elenco.

Le coppie (parola, numero di occorrenze) vengono memorizzate in una HashMap mentre le coppie (x, y) in una TreeMap.

Questo accorgimento permette di avere automaticamente ordinate le coppie in stampa.

Il programma fa uso delle classi EchoWriter e ScanDirectory presentate nei Complementi: Utilità.

import java.io.*;
import java.util.*;

public class Frequenze{ 

    final static String inpDirectory = "./testi"; // il directory dei file da scandire 
    final static String delim =" ,.;?!\"\'";      // i delimitatori delle parole 
		
    public Frequenze(){
// creazione e riempimento della prima tabella 
        Map<Object,Integer> h = new HashMap<Object,Integer>();
        ScanDirectory sd = new ScanDirectory(inpDirectory,".txt");
        for(String fileName : sd.list()) read(fileName, h);
	    
// creazione e riempimento della seconda tabella 
        Map<Object,Integer> t = new TreeMap<Object,Integer>();
        for(Integer v : h.values()) add(t,v);
	    	 
// stampa dei risultati 
        for (Map.Entry e : t.entrySet()) System.out.println(e);
    }
	
// add conta degli elementi 
    void add(Map<Object,Integer> m, Object v){
         Integer o = m.get(v);
         if(o==null) m.put(v,1); 
         else        m.put(v,o+1);	
    }
	
// read lettura di un file e inserzione delle parole
    void read(String inp, Map<Object,Integer> h){
         try {
             BufferedReader in = new BufferedReader(
                         new FileReader(inpDirectory+"/"+inp));
             String line = in.readLine();
             while(line!=null){
                  StringTokenizer st = new StringTokenizer(line, delim);
                  while(st.hasMoreTokens()){add(h, st.nextToken());}
                  line = in.readLine();
             }
             System.out.println("file "+inp+": inserite "+h.size()+" parole");
             in.close();
         } catch(IOException e) {e.printStackTrace();}
    }
}

 

Si noti la compattezza del programma ottenuta utilizzando le "classi giuste".

 




Esercizi

1) Si scriva una classe che utilizzi l'interfaccia java.util.Map per gestire un elenco di coppie (nome, indirizzo) come quello visto all'inizio.

Si scriva un programma di test che, senza modificare la classe, usi sia l'implementazione con HashMap che con TreeMap.


2) Si scriva un programma dove si generino un migliaio interi di numeri casuali nell intervallo [0,100], utilizzando la classe java.util.Random e si mostri la frequenza con cui appaiono, attraverso la stampa delle coppie (numero, frequenza).

Si scriva sia l'implementazione con HashMap che con TreeMap, che con una tabella ad accesso diretto.