שולחנות האש

21 ביוני 2002

ש: כשאני משתמש באובייקט כמפתח ב- Hashtable, מה בכיתה Object עלי לעקוף ולמה?

ת: כאשר אתה יוצר אובייקט מפתח משלך לשימוש Hashtable, אתה חייב לעקוף את Object.equals()ואת Object.hashCode()שיטות מאז Hashtableמשתמש בשילוב של המפתח של hashCode()ו equals()שיטות לאחסן ולאחזר הערכי שלה במהירות. זה גם כלל כללי שכשאתה עוקף equals(), אתה תמיד עוקף hashCode().

עוד על הסיבה

הסבר מעט יותר מעמיק יעזור לך להבין Hashtableאת מנגנון האחסון והשליפה. Hashtableפנימי מכיל דליים שבו הוא מאחסן את זוגות מפתח / ערך. Hashtableשימושים של hashcode המפתח כדי לקבוע שאליו דלי זוג מפתח / ערך צריך למפות.

איור 1 מציג את a Hashtableואת דליה. כאשר אתה מעביר מפתח / ערך אל ה- Hashtable, הוא מבצע שאילתת קוד hash של המפתח. Hashtableהשימושים כי קוד כדי לקבוע את הדלי שבו למקם את / ערך המפתח. כך, לדוגמא, אם ה- hashcode שווה לאפס, Hashtableהמקומות מכניסים את הערך לדלי 0. כמו כן, אם ה- hashcode הוא שניים, Hashtableהמקומות מכניסים את הערך לדלי 2. (זו דוגמה פשטנית; Hashtableהרצון יעסה את ה- hashcode קודם כך Hashtableלא מנסה להכניס את הערך מחוץ לדלי.)

על ידי שימוש ב- hashcode בדרך זו, הוא Hashtableיכול גם לקבוע במהירות באיזו דלי הוא הציב את הערך כשאתה מנסה לאחזר אותו.

Hashcodes, לעומת זאת, מייצגים רק חצי מהתמונה. ה- hashcode רק אומר Hashtableלאיזו דלי יש להפיל את המפתח / הערך. לפעמים, עם זאת, אובייקטים מרובים עשויים למפות לאותו דלי, אירוע המכונה התנגשות. בג'אווה Hashtableהתגובות להתנגשות על ידי הצבת ערכים מרובים לאותו דלי (יישומים אחרים עשויים להתמודד עם התנגשויות באופן שונה). איור 2 מראה כיצד Hashtableיכול להיראות לאחר מספר התנגשויות.

עכשיו דמיין שאתה מתקשר get()עם מפתח שממפה ל- Bucket 0. Hashtableכעת יהיה עליך לבצע חיפוש מחדש ברצף דרך צמדי המפתח / הערך ב- Bucket 0 כדי למצוא את הערך המבוקש. כדי לבצע בדיקה זו, Hashtableמבצע את השלבים הבאים:

  1. שאיל את קוד ה- hashcode של המפתח
  2. אחזר את רשימת המפתחות / הערכים השוכנים בדלי שניתן על ידי ה- hashcode
  3. סרוק באמצעות כל ערך ברצף עד מפתח שווה המפתח עבר get()נמצא

תשובה ארוכה לשאלה קצרה אני מכיר, אבל היא מחמירה. עוקף כהלכה equals()והוא hashCode()תרגיל לא מקוון. עליכם לנקוט משנה זהירות בכדי להבטיח את חוזי שתי השיטות.

ביישום שווה ()

לפי equals()הג'אדוק, על השיטה להתאים לכללים הבאים:

" equals()השיטה מיישמת יחס שקילות:
  • זה רפלקסיבי: לכל ערך התייחסות x, x.equals(x)צריך להחזיר נכון
  • זה סימטרי: לכל ערכי התייחסות x ו- y, x.equals(y)צריך להחזיר true אם ורק אם y.equals(x)מחזיר true
  • זה חולף: עבור כל ערכי התייחסות x, y ו- z, אם x.equals(y)מחזיר true y.equals(z)ומחזיר true, אז x.equals(z)צריך להחזיר true
  • זה עקבי: לכל ערכי התייחסות x ו- y, קריאות מרובות של x.equals(y)החזרת אמת באופן עקבי או החזרת שקר באופן עקבי, בתנאי שלא נעשה שינוי במידע המשמש בהשוואה שווה על האובייקט
  • לכל ערך ייחוס שאינו אפס x, x.equals(null)צריך להחזיר שקר "

ב- Java Effective, ג'ושוע בלוך מציע מתכון בן חמישה שלבים לכתיבת equals()שיטה יעילה . הנה המתכון בצורה קוד:

מחלקה ציבורית EffectiveEquals {private int valueA; ערך int פרטי B; . . . שווה ציבורי בוליאנית (אובייקט o) {if (this == o) {// שלב 1: בצע == test return true; } אם (! (o מופע של EffectiveEquals)) {// שלב 2: מופע המחאה מחזיר שקר; } EffectiveEquals ee = (EffectiveEquals) o; // שלב 3: טיעון העברה // שלב 4: עבור כל שדה חשוב, בדוק אם הם שווים // עבור פרימיטיבים השתמש == // עבור אובייקטים השתמש בשווה () אך הקפד גם // לטפל במקרה null החזרה ראשונה ee.valueA == valueA && ee.valueB == valueB; }. . . }

הערה: אינך צריך לבצע בדיקת null מאחר שהיא null instanceof EffectiveEqualsתערך לשקר.

לבסוף, לשלב 5, חזור equals()לחוזה ושאל את עצמך אם equals()השיטה רפלקסיבית, סימטרית וחולפת. אם לא, תקן את זה!

בהטמעת hashCode ()

בגין hashCode()החוזה הכללי, הג'אדוק אומר:

  • "בכל פעם שהוא מופעל על אותו אובייקט לא פעם במהלך ביצוע יישום Java, hashCode()השיטה חייבת להחזיר באופן עקבי את אותו מספר שלם, בתנאי שלא נעשה שינוי במידע המשמש בהשוואה שווה באובייקט. מספר שלם זה לא צריך להישאר עקבי מאחד ביצוע בקשה לביצוע אחר של אותה בקשה.
  • אם שני אובייקטים שווים על פי equals(Object)השיטה, אז קריאת hashCode()השיטה על כל אחד משני האובייקטים חייבת לייצר את אותה תוצאה שלמה.
  • לא נדרש שאם שני אובייקטים אינם שווים על פי equals(java.lang.Objectהשיטה, אז קריאת hashCode()השיטה על כל אחד משני האובייקטים חייבת לייצר תוצאות שלמות ברורות. עם זאת, על המתכנת להיות מודע לכך שהפקת תוצאות שלמות שלמות לאובייקטים לא שווים עשויה לשפר את ביצועי הטבלאות. "

יצירת hashCode()שיטת עבודה נכונה מתגלה כקשה; זה הופך להיות קשה עוד יותר אם האובייקט המדובר אינו משתנה. אתה יכול לחשב קוד hash עבור אובייקט נתון בדרכים רבות. השיטה היעילה ביותר מבססת את המספר על שדות האובייקט. יתר על כן, ניתן לשלב ערכים אלה בדרכים שונות. להלן שתי גישות פופולריות:

  • באפשרותך להפוך את שדות האובייקט למחרוזת, לשרשר את המיתרים ולהחזיר את ה- hashcode שנוצר
  • אתה יכול להוסיף את hashcode של כל שדה ולהחזיר את התוצאה

בעוד שקיימות גישות אחרות ויסודיות יותר, שתי הגישות האמורות מוכיחות את הקלה ביותר להבנה וליישום.

טוני סינטס הוא יועץ עצמאי ומייסד ייעוץ מחלקה ראשונה, חברת ייעוץ המתמחה בגישור מערכות הכשרה שונות. מחוץ לייעוץ ממדרגה ראשונה, טוני הוא סופר עצמאי פעיל, וכן מחבר הספר Sams Teach Yourself-Oriented Object Programming in 21 Days (Sams, 2001; ISBN: 0672321092).

למידע נוסף על נושא זה

  • עבור Javadoc Hashtable, עבור אל

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

  • "יישום שווה () ו- hashCode ()" של Vipan Singla מספק דיון מעמיק על עקיפת השיטות שווה () ו- hashCode ()

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

  • 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 ()

  • לקבלת מדריך יעיל לתכנות Java של ג'ושוע בלוך (אדיסון ווסלי פרופשיונל, 2001; ISBN0201310058), עבור אל

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

  • לקבלת מאמרים נוספים על שיעורי ושיטות Java, עיין במקטע ה- APIs במדד המקומי JavaWorld

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

  • רוצה יותר? עיין בדף אינדקס התשובות והתשובות של Java לקבלת קטלוג השאלות והתשובות המלאות

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

  • במשך יותר מ 100 טיפים Java תובנה מכמה המוחות הטובים ביותר בעסק, ביקור JavaWorld" s טיפים Java דף האינדקס

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

  • למד את יסודות Java בדיון שלנו למתחילים ב- Java

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

  • הרשמה JavaWorld שבועי חינם של" Java Core דיוור אלקטרוני

    //www.javaworld.com/subscribe

  • תוכלו למצוא שפע של מאמרים הקשורים ל- IT מפרסומי אחותנו באתר .net

סיפור זה, "Hashtables" פורסם במקור על ידי JavaWorld.