Προγραμματισμός

Hashtables

21 Ιουνίου 2002

Ε: Όταν χρησιμοποιώ ένα αντικείμενο ως κλειδί σε πίνακα κατακερματισμού, τι στην κλάση αντικειμένων πρέπει να παρακάμψω και γιατί;

ΕΝΑ: Όταν δημιουργείτε το δικό σας βασικό αντικείμενο για χρήση στο a Hashtable, πρέπει να παρακάμψετε το Object.equals () και Object.hashCode () μεθόδους από τότε Hashtable χρησιμοποιεί έναν συνδυασμό των κλειδιών hashCode () και ισούται με () μεθόδους αποθήκευσης και ανάκτησης των καταχωρίσεών της γρήγορα. Είναι επίσης ένας γενικός κανόνας ότι όταν παρακάμπτετε ισούται με (), πάντα παρακάμπτετε hashCode ().

Περισσότερα για το γιατί

Μια ελαφρώς πιο εμπεριστατωμένη εξήγηση θα σας βοηθήσει να καταλάβετε Hashtableμηχανισμός αποθήκευσης και ανάκτησης. ΕΝΑ Hashtable περιέχει εσωτερικά κουβάδες στους οποίους αποθηκεύει τα ζεύγη κλειδιών / τιμών. ο Hashtable χρησιμοποιεί τον κωδικό hash του κλειδιού για να προσδιορίσει σε ποιον κάδο πρέπει να αντιστοιχίσει το ζεύγος κλειδιών / τιμών.

Το σχήμα 1 δείχνει a Hashtable και οι κάδοι του. Όταν μεταβιβάζετε ένα κλειδί / τιμή στο Hashtable, ερωτά τον κωδικό hash του κλειδιού. ο Hashtable χρησιμοποιεί αυτόν τον κωδικό για να προσδιορίσει τον κάδο στον οποίο θα τοποθετήσει το κλειδί / τιμή. Έτσι, για παράδειγμα, εάν ο κωδικός hash ισούται με μηδέν, το Hashtable τοποθετεί την τιμή στο Bucket 0. Ομοίως, εάν ο κωδικός hash είναι δύο, το Hashtable τοποθετεί την τιμή στον Κάδο 2. (Αυτό είναι ένα απλοϊκό παράδειγμα, το Hashtable θα κάνει μασάζ πρώτα στον κωδικό κατακερματισμού, έτσι ώστε το Hashtable δεν προσπαθεί να εισαγάγει την τιμή έξω από τον κάδο.)

Με τη χρήση του κωδικού κατακερματισμού με αυτόν τον τρόπο, το Hashtable μπορεί επίσης να προσδιορίσει γρήγορα σε ποιον κάδο έχει τοποθετήσει την τιμή όταν προσπαθείτε να το ανακτήσετε.

Ωστόσο, οι κωδικοί Hash αντιπροσωπεύουν μόνο τη μισή εικόνα. Ο κωδικός κατακερματισμού λέει μόνο το Hashtable σε ποιον κάδο για να ρίξετε το κλειδί / τιμή. Μερικές φορές, ωστόσο, πολλά αντικείμενα ενδέχεται να αντιστοιχούν στον ίδιο κάδο, ένα συμβάν γνωστό ως σύγκρουση. Στην Java, το Hashtable αποκρίνεται σε μια σύγκρουση τοποθετώντας πολλαπλές τιμές στον ίδιο κάδο (άλλες εφαρμογές μπορεί να χειριστούν συγκρούσεις διαφορετικά). Το σχήμα 2 δείχνει τι α Hashtable μπορεί να μοιάζει με μερικές συγκρούσεις.

Τώρα φανταστείτε ότι τηλεφωνείτε παίρνω() με ένα κλειδί που αντιστοιχεί στο Bucket 0. Το Hashtable θα χρειαστεί τώρα να πραγματοποιήσετε μια διαδοχική αναζήτηση μέσω των ζευγών κλειδιών / τιμών στο Bucket 0 για να βρείτε την ζητούμενη τιμή. Για να εκτελέσετε αυτήν την αναζήτηση, το Hashtable εκτελεί τα ακόλουθα βήματα:

  1. Ερώτηση του κωδικού κατακερματισμού του κλειδιού
  2. Ανακτήστε τη λίστα κλειδιών / τιμών που βρίσκονται στον κάδο που δίνεται από τον κωδικό κατακερματισμού
  3. Σαρώστε διαδοχικά κάθε καταχώριση έως ότου ένα κλειδί που ισούται με το κλειδί που μεταβιβάστηκε παίρνω() βρίσκεται

Μια μεγάλη απάντηση σε μια σύντομη ερώτηση που ξέρω, αλλά χειροτερεύει. Σωστά παράκαμψη ισούται με () και hashCode () είναι μια ασήμαντη άσκηση. Πρέπει να προσέχετε ιδιαίτερα για να εγγυηθείτε τις συμβάσεις και των δύο μεθόδων.

Κατά την εφαρμογή ισούται με ()

Σύμφωνα με την ισούται με () Javadoc, η μέθοδος πρέπει να συμμορφώνεται με τους ακόλουθους κανόνες:

ισούται με () η μέθοδος εφαρμόζει μια σχέση ισοδυναμίας:
  • Είναι αντανακλαστικό: Για οποιαδήποτε τιμή αναφοράς x, x. ίσο (x) πρέπει να επιστρέψει αληθινό
  • Είναι συμμετρικό: Για οποιεσδήποτε τιμές αναφοράς x και y, x. ίσο (y) θα πρέπει να επιστρέψει αληθές εάν και μόνο εάν ε. ίσα (x) επιστρέφει αλήθεια
  • Είναι μεταβατικό: Για οποιεσδήποτε τιμές αναφοράς x, y και z, εάν x. ίσο (y) επιστρέφει true και y. ίσο (z) επιστρέφει αλήθεια, τότε x. ίσο (z) πρέπει να επιστρέψει αληθινό
  • Είναι συνεπές: Για οποιεσδήποτε τιμές αναφοράς x και y, πολλαπλές επικλήσεις του x. ίσο (y) επιστρέφει αληθινά ή σταθερά επιστρέφει ψευδώς, υπό την προϋπόθεση ότι δεν τροποποιούνται πληροφορίες που χρησιμοποιούνται σε ίσες συγκρίσεις στο αντικείμενο
  • Για οποιαδήποτε μη μηδενική τιμή αναφοράς x, x. ίσο (μηδέν) πρέπει να επιστρέψει ψευδές "

Σε Αποτελεσματική Java, Ο Joshua Bloch προσφέρει μια συνταγή πέντε βημάτων για τη σύνταξη μιας αποτελεσματικής ισούται με () μέθοδος. Εδώ είναι η συνταγή σε μορφή κώδικα:

δημόσια τάξη EffectiveEquals {private int valueA; ιδιωτική τιμή int; . . . public boolean ισούται με (Object o) {if (this == o) {// Βήμα 1: Εκτέλεση == test return true; } εάν (! (o instanceof EffectiveEquals)) {// Βήμα 2: Παρουσία ψευδούς επιστροφής ελέγχου; } EffectiveEquals ee = (EffectiveEquals) o; // Βήμα 3: Όρισμα μετάδοσης // Βήμα 4: Για κάθε σημαντικό πεδίο, ελέγξτε αν είναι ίσο // Για πρωτόγονα χρήση == // Για αντικείμενα η χρήση ισούται με (), αλλά φροντίστε επίσης να // χειριστείτε την μηδενική θήκη πρώτη επιστροφή ee.valueA == valueA && ee.valueB == valueB; } . . } 

Σημείωση: Δεν χρειάζεται να εκτελέσετε μηδενικό έλεγχο από τότε null instanceof EffectiveEquals θα αξιολογήσει σε ψευδές.

Τέλος, για το Βήμα 5, επιστρέψτε στο ισούται με ()συμβόλαιο και αναρωτηθείτε αν το ισούται με () μέθοδος είναι αντανακλαστική, συμμετρική και μεταβατική. Εάν όχι, διορθώστε το!

Κατά την εφαρμογή του hashCode ()

Για hashCode ()γενική σύμβαση, ο Javadoc λέει:

  • "Όποτε γίνεται επίκληση στο ίδιο αντικείμενο περισσότερες από μία φορές κατά την εκτέλεση μιας εφαρμογής Java, το hashCode () Η μέθοδος πρέπει να επιστρέφει με συνέπεια τον ίδιο ακέραιο, υπό την προϋπόθεση ότι δεν τροποποιούνται πληροφορίες που χρησιμοποιούνται σε ίσες συγκρίσεις στο αντικείμενο. Αυτός ο ακέραιος αριθμός δεν χρειάζεται να παραμείνει συνεπής από τη μία εκτέλεση μιας εφαρμογής σε μια άλλη εκτέλεση της ίδιας εφαρμογής.
  • Εάν δύο αντικείμενα είναι ίδια σύμφωνα με το ισούται με (αντικείμενο) μέθοδο, και στη συνέχεια καλεί το hashCode () μέθοδος σε καθένα από τα δύο αντικείμενα πρέπει να παράγει το ίδιο ακέραιο αποτέλεσμα.
  • Δεν απαιτείται εάν δύο αντικείμενα είναι άνισα σύμφωνα με το ισούται με (java.lang.Object μέθοδο, και στη συνέχεια καλεί το hashCode () μέθοδος σε καθένα από τα δύο αντικείμενα πρέπει να παράγει ξεχωριστά ακέραια αποτελέσματα. Ωστόσο, ο προγραμματιστής πρέπει να γνωρίζει ότι η παραγωγή διακριτών ακέραιων αποτελεσμάτων για άνισα αντικείμενα μπορεί να βελτιώσει την απόδοση των hashtables. "

Δημιουργώντας μια σωστή λειτουργία hashCode () Η μέθοδος αποδεικνύεται δύσκολη. γίνεται ακόμη πιο δύσκολο εάν το εν λόγω αντικείμενο δεν είναι αμετάβλητο. Μπορείτε να υπολογίσετε έναν κωδικό κατακερματισμού για ένα δεδομένο αντικείμενο με πολλούς τρόπους. Η πιο αποτελεσματική μέθοδος βασίζει τον αριθμό στα πεδία του αντικειμένου. Επιπλέον, μπορείτε να συνδυάσετε αυτές τις τιμές με διάφορους τρόπους. Ακολουθούν δύο δημοφιλείς προσεγγίσεις:

  • Μπορείτε να μετατρέψετε τα πεδία του αντικειμένου σε συμβολοσειρά, να συνενώσετε τις συμβολοσειρές και να επιστρέψετε τον κωδικό κατακερματισμού που προκύπτει
  • Μπορείτε να προσθέσετε τον κωδικό hash κάθε πεδίου και να επιστρέψετε το αποτέλεσμα

Ενώ υπάρχουν άλλες, πιο εμπεριστατωμένες, προσεγγίσεις, οι δύο προαναφερθείσες προσεγγίσεις αποδεικνύουν την ευκολότερη κατανόηση και εφαρμογή.

Ο Tony Sintes είναι ανεξάρτητος σύμβουλος και ιδρυτής της First Class Consulting, μιας συμβουλευτικής εταιρείας που ειδικεύεται στη γεφύρωση διαφορετικών εταιρικών συστημάτων και κατάρτισης. Εκτός από την First Class Consulting, ο Tony είναι ενεργός ανεξάρτητος συγγραφέας, καθώς και συγγραφέας του Sams Teach Yourself Object-Oriented Programming in 21 Days (Sams, 2001; ISBN: 0672321092).

Μάθετε περισσότερα σχετικά με αυτό το θέμα

  • Για το Hashtable Javadoc, μεταβείτε στο

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

  • Το "Implementing Equals () και hashCode ()" του Vipan Singla παρέχει μια σε βάθος συζήτηση για την παράκαμψη των μεθόδων ίσο () και 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)

  • Το Object.hashCode () Javadoc

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

  • Για τον Joshua Bloch's Αποτελεσματικός οδηγός γλώσσας προγραμματισμού Java (Addison Wesley Professional, 2001; ISBN0201310058), μεταβείτε στη διεύθυνση

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

  • Για περισσότερα άρθρα σχετικά με τάξεις και μεθόδους Java, ανατρέξτε στο API τμήμα του JavaWorld 'Τοπ Ευρετήριο

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

  • Θέλουν περισσότερα? Δείτε το Ε & Α Java σελίδα ευρετηρίου για τον πλήρη κατάλογο ερωτήσεων και απαντήσεων

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

  • Για περισσότερες από 100 διορατικές συμβουλές Java από μερικά από τα καλύτερα μυαλά στην επιχείρηση, επισκεφτείτε JavaWorld 'μικρό Συμβουλές Java σελίδα ευρετηρίου

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

  • Μάθετε τα βασικά Java σε μας Αρχάριος Java συζήτηση

    //forums.idg.net/webx?50@@.ee6b804

  • Εγγραφείτε JavaWorldΔωρεάν εβδομαδιαία Πυρήνας Java ενημερωτικό δελτίο ηλεκτρονικού ταχυδρομείου

    //www.javaworld.com/subscribe

  • Θα βρείτε πληθώρα άρθρων που σχετίζονται με την πληροφορική από τις αδελφές εκδόσεις μας στο .net

Αυτή η ιστορία, "Hashtables" δημοσιεύθηκε αρχικά από την JavaWorld.

$config[zx-auto] not found$config[zx-overlay] not found