Strutture hash in java

Hash Table - Hash Map - Hash Set

Sorgente di questi appunti la documentazione java 1.6 java.util.Hash*

Hashtable<K,V>

Questa classe implementa una hashtable che mappa chiavi a valori. Qualsiasi valore non null può essere usato come chiave o come valore. Per memorizzare e ritrovare oggetti da una hashtable, gli oggetti usati come chiavi devono implementare il metodo hashCode e il metodo equals.
Una istanza di Hashtable ha due parametri che influenzano le sue performance: capacità iniziale e fattore di carico. La capacità è il numero di buckets nella hash table, la capacità iniziale è il numero di buckets al momento della creazione della hash table.
Da notare che la hash table è open: nel caso di hash collision, un buckets singolo memorizza più entità, le quali devono essere cercate sequenzialmente.
Il fattore di carico è la misura che indica la percentuale di come la tabella di hash deve essere piene prima che la sua capacità sia automaticamente incrementata.
Questi due valori sono solamente suggeriti nell'implementazione, i dettagli esatti di come e se il metodo di reash venga chiamato sono dipendenti dall'implementazione.
Il valore di default per il fattore di carico è .75 offre un buon tradeoff tra il tempo e il costo. Alti valori decrementano lo spazio in più ma incrementano il tempo per cercare una entry (che si riflette su molte operazioni della tabella incluse get e put).
La capacità iniziale controlla il tradeoff tra spazio sprecato e la necessità per operazioni di reash che consumano molto tempo. Nessuna operazione di reash verrà mai eseguita se la capacità iniziale è più grande del massimo numero di entry che la hastable può contenere divisa il suo fattore di carico. Certamente settare il numero di entry troppo alto porterà a uno spreco esagerato di spazio.

// It uses the names of the numbers as keys:
   Hashtable<String, Integer> numbers = new Hashtable<String, Integer>();
   numbers.put("one", 1);
   numbers.put("two", 2);
   numbers.put("three", 3);
 
//To retrieve a number, use the following code:
   Integer n = numbers.get("two");
   if (n != null) {
     System.out.println("two = " + n);
   }

Un iteratore restituito dal metodo iterator di una collezione restituita da tutte le classi "collection view methods" sono fail-fast : se la hashtable viene modificata strutturalmente dopo che l'iteratore viene creato, o in ogni altro modo che non sia il metodo remove dell'iteratore , l'iteratore lancia una ConcurrentModificationException . Questo per evitare comportamenti non deterministici. L'enumeratore restituito da una chiave di hashtable e i metodi degli elementi non sono fail-fast.
Continuare da "Note that the fail-fast" dice che non funzionano in caso di accesso concorrente così come gli altri, ma bisogna fare il syncronized.

HashMap<K,V>

La tabella Hash basa la sua implementazione sull'interfaccia Map. Questa interfaccia fornisce tutte le operazioni opzionali sulla map, e permette valori null per la key e per values. La classe HashMap è approssimativamente equivalente alla HashTable eccetto che è non sincronizzato e permette i null. Questa classe non garantisce l'ordine della map in particolare nel tempo.
Questa implementazione fornisce tempo costante per operazioni base get e put, assumento che la funziona di hash disperda gli elementi appropriatamente tra i bucket. Le iterazioni sulla collezione richiedono tempo proporzionalmente alla capacità dell'istanza HashMap (numero di bucket) sommata alla sua dimensione (il numero di valori e chiavi mappati). Per questo è molto importante settare la capacità iniziale troppo alta (o il fattore di carico troppo basso) se le performance di iterazione sono importanti.
Una istanza di HashMa ha due parametri che influenzano la sua performance: capacità iniziale e fattore di carico.

  • La capacità è il numero di buckets nella hash table e la capacità iniziale è quella con cui la hash table viene creata.
  • Il fattore di carico è la misura di come "il riempimento della hash table è permesso, prima che la sua capacità è automaticamente incrementata" "of how full the hash table is allowed to get before its capacity is automatically increased" . Quando il numero di entries eccede il prodotto del fattore di carico e la capacità corrente la hash table viene rehash = rigenerata (le strutture interne vengono ricostruite), così che la hash table approssimativamente raddoppia il numero dei buckets.
  • Come regola generale il fattore di carico di default (.75) offre un buon compromesso tra costi di tempo e spazio. Alti valori decrementano lo spazio di overhead ma diminuiscono il costo di lookup , questo si riflette sulla maggior parte delle operazioni incluse put e get. Il numero aspettato di entries nella map e il suo fattore di carico dovrebbero essere prese in considerazione quando viene settata il suo valore iniziale, in modo da minimizzare il numero di operazioni di rehash. Se la capacità iniziale è più grande del massimo numero di entries diviso per il fattore di carico , nessuna operazione di rehash viene eseguita.

Se molti mappings sono memorizzati in una istanza di HashMap, creandola con una capacità sufficente permetterà al mapping di essere memorizzato più efficientemente rispetto al rehashing necessario per far crescere le tabelle.

Continuare da "Note that this implementation is not synchronized."

HashSet<E>

Questa classe implementa l'interfaccia di Set, backend da una hash table (attualmente una istanza di HashMap). Questa non garantisce l'ordine di iterazione del set, cioè non garantisce che l'ordine rimanga costante nel tempo. Questa classe permette gli elementi null.
Questa classe offre tempo costante per le operazioni base (add, remove, contains e size), assumendo che la funzione di hash disperda gli elementi appropriatamente tra i bucket. L'iterazione tra questi set richiede tempo proporzionale alla somma degli "instance size" (il numero degli elementi) dell' HashSet più la capacità del istanza di HashMap (il numero dei bucket). Per questo è molto importante non settare la capacità iniziale troppo alta (o il fattore di carico troppo basso) se la performance di iterazione è importante.
Continuare da "Note that this implementation is not synchronized"

Salvo diversa indicazione, il contenuto di questa pagina è sotto licenza Creative Commons Attribution-ShareAlike 3.0 License