Hashtables

21 giugno 2002

D: Quando utilizzo un oggetto come chiave in un Hashtable, cosa devo sovrascrivere nella classe Object e perché?

R: Quando crei il tuo oggetto chiave da usare in a Hashtable, devi sovrascrivere i metodi Object.equals()e Object.hashCode()poiché Hashtableutilizza una combinazione dei metodi hashCode()e della chiave equals()per memorizzare e recuperare rapidamente le sue voci. È anche una regola generale che quando esegui l'override equals(), esegui sempre l'override hashCode().

Maggiori informazioni sul perché

Una spiegazione leggermente più approfondita ti aiuterà a capire Hashtableil meccanismo di archiviazione e recupero. A Hashtablecontiene internamente dei bucket in cui memorizza le coppie chiave / valore. Gli Hashtableusi codice hash della chiave per determinare a quale bucket la coppia chiave / valore dovrebbe mappa.

La figura 1 mostra a Hashtablee i relativi bucket. Quando si passa una chiave / valore a Hashtable, viene eseguita una query sul codice hash della chiave. Gli Hashtableusi che codice per determinare il secchio in cui inserire la chiave / valore. Quindi, ad esempio, se il codice hash è uguale a zero, Hashtableinserisce il valore nel Bucket 0. Allo stesso modo, se il codice hash è due, Hashtableinserisce il valore nel Bucket 2. (Questo è un esempio semplicistico; Hashtablemassaggerà prima il codice hash quindi il Hashtablenon cerca di inserire il valore fuori dal bucket.)

Utilizzando l'hashcode in questo modo, Hashtableè anche possibile determinare rapidamente in quale bucket ha posizionato il valore quando si tenta di recuperarlo.

Gli hashcode, tuttavia, rappresentano solo metà dell'immagine. Il codice hash dice solo al Hashtablebucket in cui inserire la chiave / valore. A volte, tuttavia, più oggetti possono essere mappati allo stesso bucket, un evento noto come collisione. In Java, Hashtablerisponde a una collisione inserendo più valori nello stesso bucket (altre implementazioni possono gestire le collisioni in modo diverso). La figura 2 mostra come Hashtablepotrebbe apparire dopo alcune collisioni.

Ora immagina di chiamare get()con una chiave che mappa al Bucket 0. HashtableOra sarà necessario eseguire una ricerca sequenziale attraverso le coppie chiave / valore nel Bucket 0 per trovare il valore richiesto. Per eseguire questa ricerca, Hashtableesegue i seguenti passaggi:

  1. Interroga il codice hash della chiave
  2. Recupera l'elenco di chiavi / valori che risiedono nel bucket fornito dal codice hash
  3. Scansione sequenziale di ciascuna voce finché non get()viene trovata una chiave uguale alla chiave in cui è stata trasferita

Una lunga risposta a una breve domanda lo so, ma peggiora. Correttamente prioritario equals()ed hashCode()è un esercizio non banale. È necessario prestare la massima attenzione per garantire i contratti di entrambi i metodi.

Sull'implementazione di equals ()

Secondo equals()Javadoc, il metodo deve essere conforme alle seguenti regole:

"Il equals()metodo implementa una relazione di equivalenza:
  • È riflessivo: per qualsiasi valore di riferimento x, x.equals(x)dovrebbe restituire vero
  • È simmetrico: per qualsiasi valore di riferimento x e y, x.equals(y)dovrebbe restituire vero se e solo se y.equals(x)restituisce vero
  • È transitivo: per qualsiasi valore di riferimento x, yez, se x.equals(y)restituisce true e y.equals(z)restituisce true, x.equals(z)deve restituire true
  • È coerente: per qualsiasi valore di riferimento x e y, più invocazioni di x.equals(y)restituiscono costantemente true o costantemente restituiscono false, a condizione che non venga modificata alcuna informazione utilizzata nei confronti uguali sull'oggetto
  • Per qualsiasi valore di riferimento non nullo x, x.equals(null)dovrebbe restituire false "

In Effective Java, Joshua Bloch offre una ricetta in cinque passaggi per scrivere un equals()metodo efficace . Ecco la ricetta sotto forma di codice:

public class EffectiveEquals {private int valueA; private int valueB; . . . public boolean equals (Object o) {if (this == o) {// Step 1: Esegui un == test return true; } if (! (o instanceof EffectiveEquals)) {// Passaggio 2: istanza di check return false; } EffectiveEquals ee = (EffectiveEquals) o; // Passaggio 3: Trasmetti argomento // Passaggio 4: per ogni campo importante, controlla se sono uguali // Per le primitive usa == // Per gli oggetti usa equals () ma assicurati di // gestire anche il caso nullo primo ritorno ee.valueA == valueA && ee.valueB == valueB; }. . . }

Nota: non è necessario eseguire un controllo nullo poiché null instanceof EffectiveEqualsrestituirà false.

Infine, per il passaggio 5, torna al equals()contratto di e chiediti se il equals()metodo è riflessivo, simmetrico e transitivo. In caso contrario, aggiustalo!

Sull'implementazione di hashCode ()

Per hashCode()il contratto generale di, il Javadoc dice:

  • "Ogni volta che viene invocato sullo stesso oggetto più di una volta durante l'esecuzione di un'applicazione Java, il hashCode()metodo deve restituire costantemente lo stesso numero intero, a condizione che non venga modificata alcuna informazione utilizzata nei confronti uguali sull'oggetto. Questo numero intero non deve rimanere coerente da uno esecuzione di un'applicazione su un'altra esecuzione della stessa applicazione.
  • Se due oggetti sono uguali in base al equals(Object)metodo, la chiamata del hashCode()metodo su ciascuno dei due oggetti deve produrre lo stesso risultato intero.
  • Non è necessario che se due oggetti sono diversi in base al equals(java.lang.Objectmetodo, la chiamata del hashCode()metodo su ciascuno dei due oggetti deve produrre risultati interi distinti. Tuttavia, il programmatore deve essere consapevole che la produzione di risultati interi distinti per oggetti disuguali può migliorare le prestazioni degli hashtable. "

Creare un hashCode()metodo che funzioni correttamente si rivela difficile; diventa ancora più difficile se l'oggetto in questione non è immutabile. Puoi calcolare un codice hash per un dato oggetto in molti modi. Il metodo più efficace basa il numero sui campi dell'oggetto. Inoltre, puoi combinare questi valori in vari modi. Ecco due approcci popolari:

  • È possibile trasformare i campi dell'oggetto in una stringa, concatenare le stringhe e restituire il codice hash risultante
  • Puoi aggiungere il codice hash di ogni campo e restituire il risultato

Sebbene esistano altri approcci più approfonditi, i due approcci sopra menzionati si dimostrano i più facili da comprendere e implementare.

Tony Sintes è un consulente indipendente e fondatore di First Class Consulting, una società di consulenza specializzata nel collegare sistemi e formazione aziendali disparati. Al di fuori di First Class Consulting, Tony è uno scrittore freelance attivo, nonché autore di Sams Teach Yourself Object-Oriented Programming in 21 Days (Sams, 2001; ISBN: 0672321092).

Ulteriori informazioni su questo argomento

  • Per Hashtable Javadoc, vai a

    //java.sun.com/j2se/1.4/docs/api/java/util/Hashtable.html

  • "Implementing equals () e hashCode ()" di Vipan Singla fornisce una discussione approfondita sull'override dei metodi equals () e hashCode ()

    //www.vipan.com/htdocs/hashcode_help.html

  • The Object.equals() Javadoc

    //java.sun.com/j2se/1.4/docs/api/java/lang/Object.html#equals(java.lang.Object)

  • The Object.hashCode() Javadoc

    //java.sun.com/j2se/1.4/docs/api/java/lang/Object.html#hashCode()

  • For Joshua Bloch's Effective Java Programming Language Guide (Addison Wesley Professional, 2001; ISBN0201310058), go to

    //www.amazon.com/exec/obidos/ASIN/0201310058/javaworld

  • For more articles on Java classes and methods, browse the APIs section of JavaWorld's Topical Index

    //www.javaworld.com/channel_content/jw-apis-index.shtml

  • Want more? See the Java Q&A index page for the full Q&A catalog

    //www.javaworld.com/columns/jw-qna-index.shtml

  • Per più di 100 consigli penetranti Java da alcune delle migliori menti del settore, visita 'JavaWorld s Tips Java pagina indice

    //www.javaworld.com/columns/jw-tips-index.shtml

  • Impara le basi di Java nella nostra discussione per principianti su Java

    //forums.idg.net/[email protected]@.ee6b804

  • Iscriviti alla newsletter settimanale gratuita di JavaWorld Core Java

    //www.javaworld.com/subscribe

  • Troverai una vasta gamma di articoli relativi all'IT tratti dalle nostre pubblicazioni gemelle su .net

Questa storia, "Hashtables" è stata originariamente pubblicata da JavaWorld.