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.
 

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.

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.

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

Esempio: calcolo di frequenze

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();}
    }
}

Esercizi