La classe HashSet di Set – Lezione 33 di Java Avanzato

HashSet, memorizzare gli elementi con il metodo hashCode

La classe HashSet rappresenta un’implementazione dell’interfaccia Set, questo tipo di implementazione conserva gli oggetti in tabelle simili alle HashTable.
Una tabella hash rappresenta un array associativo suddiviso in bucket. Un bucket è una casella dell’array di HashSet, in cui oni qualvolta si vuole aggiungere un oggetto viene calcolato un numero intero univoco (con il metodo hashCode) per selezionare il bucket in cui posizionare l’elemento. Ogni casella (bucket) dell’HashSet avrà un certo numero di oggetti collegati tra una lista puntata.

Graficamente la classe HashSet di Set sarà così definita:

La classe HashSet di Set

La funzione hashCode in Java è contenuta in Object:

  public int hashCode() {...}

La classe HashSet per decidere in quale bucket mettere un nuovo elemento (inserito con il metodo add) utilizza hashCode, che come per equals, si basa su gli indirizzi di memoria dell’oggetto e restituisce un intero calcolato sulla base dell’indirizzo.

Coerenza tra equals e hashCode

Cosa accadrebbe se venissero inseriti nell’HashSet due oggetti uguali per equals ma che hanno ottenuto due hashCode differenti? Avremo un duplicato in HashSet, abbiamo violato le condizioni del contratto!

Per ogni coppia di elementi x e y:

x.equals(y) == true allora x.hashCode() == y.hashCode()

Se due oggetti risultano uguali per equals allora devono avere lo stesso hashCode. Il verso opposto della relazione non viene richiesto perché risulta essere una richiesta eccessiva. Se fosse vero, ogni oggetto con hashCode diverso dovrebbe essere inserito in un bucket dell’array. Ciò è improponibile, dato che in Set non sono ammessi duplicati avremmo un unico oggetto in ogni bucket dell’array. Spesso si decide di inserire più oggetti con hashCode differenti in uno stesso bucket per ottimizzare l’utilizzo della struttura dati.

Facciamo un esempio, una classe Employee ridefinisce il metodo equals in modo che il confronto tra due Employee avvenga confrontato in base al nome degli impiegati, ma non ridefinisce il metodo hashCode. Di conseguenza, due oggetti differenti con lo stesso nome potrebbero non essere inseriti perché uguali!

Un possibile overriding del metodo hashCode è il seguente:

  public int hasCode() {
    return 0;
  }

Questa versione è coerente ma in questo caso oggetti diversi avranno lo stesso bucket, vengono inseriti tutti nella prima casella. Nella teoria delle funzioni hash, il metodo hashCode deve restituire un intero che sia il più possibile uniformemente distribuito. Nel caso precedente tutti gli oggetti ricevono zero. Dato che la classe Employee ha due campi, il suo hashCode dovrebbe restituisce un intero derivato da entrambi i suoi. Spesso per calcolare l’hashCode i campi di un oggetto vengono convertiti in tipi numerici in modo da ottenere un unico intero che verrà utilizzato come posizione nell’array. Un modo comune di combinare due interi senza correre il rischio di andare in overflow è di utilizzare un OR esclusivo, detto XOR (simbolo ^).

  public int hashCode() {
    return name.hashCode() ^ salary.
  }

Lo XOR mantiene la funzione uniforme distribuendo in modo uniforme sugli interi. Ciò ci garantisce che gli oggetti inseriti nell’array veranno equamente distribuiti in tutti i bucket.

Il contenuto degli elementi di HashSet non dovrebbe essere modificati perché se il bucket di quell’oggetto è stato scelto in base allo stato interno degli oggetti, modificandolo avremmo un problema di coerenza con la struttura dati. Utilizzando il metodo contains andremmo a cercare un oggetto solo nel bucket in cui si dovrebbe trovare quell’oggetto. Non avendo aggiornato il bucket dell’elemento modificato non lo troveremmo anche se presente.

Nota: in un HashSet per modificare un elemento è consigliato: estrarre l’elemento dall’insieme, modificarlo e reinserirlo in modo da fargli ottenere un nuovo hashCode basato sul nuovo stato interno dell’oggetto.

In un HashSet è possibile fissare il numero di bucket anche se è buona norma che oscilli tra il 75% ed il 150% degli
elementi da conservare. E’ anche possibile specificare il leadFactor, ovvero il rapporto tra il numero di elementi ed il numero di bucket: quando questo valore viene superato, l’hash table viene ricreata e vengono aumentati il numero di bucket in moda da soddisfare il load factory fissato.

In un HashSet abbiamo a disposizione i seguenti metodi:

  •   HashSet()

    Costruttore di un HashSet vuoto;

  •   HashSet(Collection elements)

    Costruisce un HashSet e vi inserisce gli oggetti contenuti in una collezione E;

  •   HashSet(int initialCapacity)

    Consente di costruire un HashSet con una capacità inziale;

  •   HashSet(int initialCapacity, float loadFactor)

    Costruisce un HashSet specificando una capacità e un load factory iniziale.

Indice Lezione PrecedenteLezione Successiva

Pubblicato in Collezioni, Guide, Java, Programmazione Taggato con: , , , , ,

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *

*