streamalism.org

1. סקירה כללית

Hashing הוא מושג בסיסי של מדעי המחשב.

בג'אווה אלגוריתמי כביסה יעילים עומדים מאחורי כמה מהאוספים הפופולאריים ביותר שיש לנו - כגון מפת גיבוב (למבט מעמיק על מפת גיבוב, אל תהסס לבדוק מאמר זה) ואת HashSet.

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

2. שימוש ב hashCode () במבני נתונים

הפעולות הפשוטות ביותר באוספים יכולות להיות לא יעילות במצבים מסוימים.

לדוגמה, זה מפעיל חיפוש לינארי שאינו יעיל מאוד עבור רשימות בגדלים עצומים:

מילים ברשימה = Arrays.asList ("ברוך הבא", "אל", "באלדונג"); אם (words.contains ("Baeldung")) {System.out.println ("Baeldung נמצא ברשימה"); }

ג'אווה מספקת מספר מבני נתונים להתמודדות ספציפית עם נושא זה - לדוגמא, כמה מַפָּה יישומי ממשק הם טבלאות חשיש.

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

3. הבנת איך hashCode () עובד

פשוט שים, hashCode () מחזיר ערך שלם שנוצר על ידי אלגוריתם hashing.

אובייקטים שווים (על פי שלהם שווים()) חייב להחזיר את אותו קוד hash. אין חובה שאובייקטים שונים יחזירו קודי hash שונים.

החוזה הכללי של hashCode () מדינות:

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

• אם שני אובייקטים שווים בהתאם ל- שווה (אובייקט) ואז לקרוא ל hashCode () שיטה על כל אחד משני האובייקטים חייבת לייצר את אותו הערך

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

"ככל שהדבר מעשי באופן סביר, hashCode () שיטה המוגדרת לפי מחלקה לְהִתְנַגֵד האם מחזירה מספרים שלמים מובחנים לאובייקטים מובחנים. (זה מיושם בדרך כלל על ידי המרת הכתובת הפנימית של האובייקט למספר שלם, אך טכניקת הטמעה זו אינה נדרשת על ידי שפת התכנות JavaTM.) "

4. נאיבי hashCode () יישום

זה למעשה די פשוט שיש נאיבי hashCode () יישום העומד במלואו בחוזה הנ"ל.

כדי להדגים זאת, נגדיר דוגמא מִשׁתַמֵשׁ מחלקה העוקפת את יישום ברירת המחדל של השיטה:

משתמש בכיתה ציבורית {מזהה פרטי ארוך; שם מחרוזת פרטי; דוא"ל מחרוזת פרטי; // סטנדרטים / סטרים / קונסטרוקטורים סטנדרטיים @ Override public int hashCode () {return 1; } @ עקוף בוליאני ציבורי שווה (אובייקט o) {אם (זה == o) להחזיר נכון; אם (o == null) להחזיר שקר; אם (this.getClass ()! = o.getClass ()) להחזיר שקר; משתמש משתמש = (משתמש) o; החזרת id == user.id && (name.equals (user.name) && email.equals (user.email)); } // גטרים וקובעים כאן}

ה מִשׁתַמֵשׁ class מספק יישומים מותאמים אישית עבור שניהם שווים() ו hashCode () אשר עומדים באופן מלא בחוזים המתאימים. יתר על כן, אין שום דבר לא לגיטימי עם קיום hashCode () החזרת כל ערך קבוע.

עם זאת, יישום זה מדרדר את הפונקציונליות של טבלאות hash לאפס בעצם, שכן כל אובייקט יאוחסן באותה דלי יחיד.

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

5. שיפור ה hashCode () יישום

בואו נשפר מעט את הזרם hashCode () יישום על ידי הכללת כל תחומי המשרד מִשׁתַמֵשׁ בכיתה כך שהיא יכולה לייצר תוצאות שונות עבור אובייקטים לא שווים:

@Override ציבורי int hashCode () {return (int) id * name.hashCode () * email.hashCode (); }

אלגוריתם הגיבוב הבסיסי הזה הוא בהחלט טוב בהרבה מהקודם, מכיוון שהוא מחשב את קוד החשיש של האובייקט רק על ידי הכפלת קודי החשיש של שֵׁם ו אימייל שדות ו תְעוּדַת זֶהוּת.

באופן כללי, אנו יכולים לומר שזה סביר hashCode () יישום, כל עוד אנו שומרים על שווים() היישום עולה בקנה אחד עם זה.

6. סטנדרטי hashCode () יישומים

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

בואו נסתכל על הטמעה "סטנדרטית" המשתמשת בשני מספרים ראשוניים כדי להוסיף עוד יותר ייחודיות לקודי hash מחושבים:

@Override int hashCode ציבורי () {int hash = 7; hash = 31 * hash + (int) id; hash = 31 * hash + (name == null? 0: name.hashCode ()); hash = 31 * hash + (email == null? 0: email.hashCode ()); החזרת חשיש; }

אמנם חשוב להבין את התפקידים hashCode () ו שווים() בשיטות משחק, אנחנו לא צריכים ליישם אותם מאפס בכל פעם, מכיוון שרוב ה- IDE יכולים ליצור התאמה אישית hashCode () ו שווים() יישומים ומאז Java 7, קיבלנו Objects.hash () שיטת שירות לחשיכה נוחה:

Objects.hash (שם, דוא"ל)

IntelliJ IDEA מייצרת את היישום הבא:

@Override ציבורי int hashCode () {int תוצאה = (int) (id ^ (id >>> 32)); תוצאה = 31 * תוצאה + name.hashCode (); תוצאה = 31 * תוצאה + email.hashCode (); תוצאת החזרה; }

ואקליפס מייצר את זה:

@Override ציבורי int hashCode () {final int prime = 31; תוצאה int = 1; תוצאה = ראשית * תוצאה + ((דוא"ל == null)? 0: email.hashCode ()); תוצאה = ראשית * תוצאה + (int) (id ^ (id >>> 32)); תוצאה = ראשית * תוצאה + ((שם == null)? 0: name.hashCode ()); תוצאת החזרה; }

בנוסף ל- IDE מבוסס הנ"ל hashCode () יישומים, ניתן גם ליצור יישום יעיל באופן אוטומטי, למשל באמצעות Lombok. במקרה זה, יש להוסיף את התלות בלומבוק-מאבן pom.xml:

 org.projectlombok lombok-maven 1.16.18.0 pom 

עכשיו זה מספיק כדי להעלות הערות על מִשׁתַמֵשׁ כיתה עם @EqualsAndHashCode:

משתמש בכיתה ציבורית @EqualsAndHashCode {// שדות ושיטות כאן}

באופן דומה, אם אנו רוצים את אפאצ'י קומונס לאנג HashCodeBuilder בכיתה לייצר a hashCode () יישום עבורנו, יש לכלול את התלות commons-lang Maven בקובץ pom:

 commons-lang commons-lang 2.6 

וגם hashCode () ניתן ליישם כך:

מחלקה ציבורית משתמש {public int hashCode () {להחזיר HashCodeBuilder חדש (17, 37). לצרף (id). להוסיף (שם). להוסיף (דוא"ל). toHashCode (); }}

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

מה שניתן להבחין כאן הוא שכל אותם יישומים משתמשים במספר 31 בצורה כלשהי - זאת מכיוון של- 31 יש מאפיין נחמד - ניתן להחליף את הכפל שלו בשינוי סיבית המהיר מהכפל הסטנדרטי:

31 * i == (i << 5) - אני

7. טיפול בהתנגשויות חשיש

ההתנהגות הפנימית של טבלאות חשיש מעלה היבט רלוונטי במבני הנתונים הללו: אפילו עם אלגוריתם גיבוב יעיל, שני אובייקטים או יותר עשויים להיות בעלי אותו קוד חשיש, גם אם הם לא שווים. לכן, קודי החשיש שלהם יצביעו על אותו דלי, למרות שיהיו להם מפתחות טבלת חשיש שונים.

מצב זה ידוע בדרך כלל כהתנגשות חשיש, ומתודולוגיות שונות קיימות לטיפול בו, כאשר לכל אחת היתרונות והחסרונות שלהם. Java מפת גיבוב משתמש בשיטת השרשור הנפרדת לטיפול בהתנגשויות:

"כששני אובייקטים או יותר מצביעים על אותה דלי, הם פשוט נשמרים ברשימה מקושרת. במקרה כזה, טבלת ה- hash היא מערך של רשימות מקושרות, וכל אובייקט עם אותו hash צורף לרשימה המקושרת באינדקס ה- bucket במערך.

במקרה הגרוע, בכמה דליים תהיה קשורה רשימה מקושרת, ואחזור של אובייקט ברשימה יבוצע באופן ליניארי..”

מתודולוגיות של התנגשות חשיש מראות בקצרה מדוע כל כך חשוב ליישם hashCode () ביעילות.

Java 8 הביא שיפור מעניין ל- מפת גיבוב יישום - אם גודל דלי חורג מהסף המסוים, הרשימה המקושרת מוחלפת במפת עץ. זה מאפשר להשיג O (logn) להסתכל למעלה במקום לפסימי עַל).

8. יצירת יישום טריוויאלי

לבדיקת הפונקציונליות של תקן hashCode () יישום, בואו ליצור יישום Java פשוט שמוסיף קצת מִשׁתַמֵשׁ חפצים ל מפת גיבוב ומשתמש ב- SLF4J לרישום הודעה למסוף בכל פעם שהשיטה נקראת.

הנה נקודת הכניסה של היישום לדוגמא:

מחלקה ציבורית יישום {public static void main (String [] args) {Map users = HashMap new (); משתמש משתמש 1 = משתמש חדש (1 ליטר, "ג'ון", "[דוא"ל מוגן]"); משתמש משתמש 2 = משתמש חדש (2L, "ג'ניפר", "[דוא"ל מוגן]"); משתמש משתמש 3 = משתמש חדש (3 ליטר, "מרי", "[מוגן בדוא"ל]"); users.put (user1, user1); users.put (user2, user2); users.put (user3, user3); אם (users.containsKey (user1)) {System.out.print ("המשתמש נמצא באוסף"); }}} 

וזה ה hashCode () יישום:

משתמש בכיתה ציבורית {// ... public int hashCode () {int hash = 7; hash = 31 * hash + (int) id; hash = 31 * hash + (name == null? 0: name.hashCode ()); hash = 31 * hash + (email == null? 0: email.hashCode ()); logger.info ("hashCode () נקרא - Hash מחושב:" + hash); החזרת חשיש; }}

הפרט היחיד שכדאי להדגיש כאן הוא שבכל פעם שאובייקט מאוחסן במפת החשיש ונבדק באמצעות ה- containKey () שיטה, hashCode () מופעל וקוד החשיש המחושב מודפס למסוף:

[ראשי] INFO com.baeldung.entities.User - hashCode () נקרא - hash מחושב: 1255477819 [main] INFO com.baeldung.entities.User - hashCode () נקרא - hash ממוחשב: -282948472 [main] INFO com.baeldung .entities.User - hashCode () נקרא - Hash ממוחשב: -1540702691 [main] INFO com.baeldung.entities.User - hashCode () נקרא - hash מחושב: 1255477819 משתמש שנמצא באוסף

9. מסקנה

ברור שייצור יעיל hashCode () יישומים דורשים לעיתים קרובות תערובת של כמה מושגים מתמטיים, (כלומר מספרים ראשוניים ושרירותיים), פעולות לוגיות בסיסיות ובסיסיות.

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

כמו תמיד, כל דוגמאות הקוד המוצגות במאמר זה זמינות ב- GitHub.