streamalism.org

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

טבלת גיבוב הוא היישום הוותיק ביותר של מבנה נתוני טבלת hash בג'אווה. ה מפת גיבוב הוא היישום השני, שהוצג ב- JDK 1.2.

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

2. מתי להשתמש טבלת גיבוב

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

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

3. דוגמא לשימוש

נמשיך בדוגמה המילונית. נדגם מִלָה כמפתח:

מעמד ציבורי Word {שם פרטי מחרוזת; מילה ציבורית (שם מחרוזת) {this.name = שם; } // ...}

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

שולחן Hashtable = Hashtable חדש ();

ראשית, בואו נוסיף ערך:

מילה מילה = מילה חדשה ("חתול"); table.put (מילה, "חיה");

כמו כן, כדי לקבל ערך:

הגדרת מחרוזת = table.get (word);

לבסוף, נסיר ערך:

הגדרה = טבלה. הסר (מילה);

ישנן עוד הרבה שיטות בכיתה, ואנחנו נתאר כמה מהן בהמשך.

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

4. החשיבות של hashCode ()

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

טבלת גיבוב משתמש במערך. כל מיקום במערך הוא "דלי" שיכול להיות ריק או להכיל אחד או יותר זוגות ערך מפתח. המדד של כל זוג מחושב.

אך מדוע לא לאחסן אלמנטים ברצף, ולהוסיף אלמנטים חדשים בסוף המערך?

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

4.1. טבלת כתובות ישירות

הדוגמה הפשוטה ביותר למיפוי כזה היא טבלת הכתובות הישירות. כאן המקשים משמשים כאינדקסים:

אינדקס (k) = k, כאשר k הוא מפתח

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

אבל יש לנו שתי בעיות כאן:

• ראשית, המפתחות שלנו אינם מספרים שלמים, אלא מִלָה חפצים
• שנית, אם הם היו מספרים שלמים, איש לא היה מבטיח שהם קטנים. תאר לעצמך שהמפתחות הם 1, 2 ו- 1000000. יהיה לנו מערך גדול בגודל 1000000 עם שלושה אלמנטים בלבד, והשאר יהיה שטח מבוזבז

hashCode () השיטה פותרת את הבעיה הראשונה.

ההיגיון במניפולציה בנתונים טבלת גיבוב פותר את הבעיה השנייה.

בואו נדון בזה לעומק.

4.2. hashCode () שיטה

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

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

4.3. צמצום הטווח

לקבל(), לָשִׂים() ו לְהַסִיר() השיטות מכילות את הקוד הפותר את הבעיה השנייה - צמצום טווח המספרים השלמים האפשריים.

הנוסחה מחשבת אינדקס עבור המפתח:

אינדקס int = (hash & 0x7FFFFFFF)% tab.length;

איפה tab.length הוא גודל המערך, ו בְּלִיל הוא מספר שהוחזר על ידי המפתחות hashCode () שיטה.

כמו שאנו יכולים לראות אינדקס הוא תזכורת לחלוקה בְּלִיל לפי גודל המערך. שים לב שקודי hash שווים מייצרים את אותו אינדקס.

4.4. התנגשויות

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

מבנה נתונים כזה נקרא טבלת hash עם שרשור.

4.5. פקטור עומס

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

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

אבל בוא נחזור למפתחות.

4.6. עקיפה שווה ל- () ו- hashCode ()

כשאנחנו מכניסים ערך ל- a טבלת גיבוב ולהוציא אותו ממנו, אנו מצפים כי ניתן להשיג את הערך לא רק באותו מופע של המפתח אלא גם עם מפתח שווה:

מילה מילה = מילה חדשה ("חתול"); table.put (מילה, "חיה"); מחרוזת שחולצה = table.get (מילה חדשה ("חתול"));

כדי לקבוע את כללי השוויון, אנו עוקפים את המפתח שווים() שיטה:

ציבורי בוליאני שווה (אובייקט o) {אם (o == זה) יחזיר נכון; אם (! (o למשל של Word)) להחזיר שקר; מילה מילה = (Word) o; החזר word.getName (). שווה (name.name); }

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

בואו נסתכל מקרוב על הדוגמה לעיל. מה קורה אם לא נעקוף hashCode ()?

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

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

public int hashCode () {return name.hashCode (); }

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

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

5. התבוססות שולחנות האש

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

5.1. כישלון מהיר: איטרציה

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

ראשית, ניצור טבלת גיבוב והוסף ערכים אליו:

שולחן Hashtable = Hashtable חדש (); table.put (Word חדש ("חתול"), "חיה"); table.put (מילה חדשה ("כלב"), "חיה אחרת");

שנית, ניצור איטרטור:

Iterator it = table.keySet (). Iterator ();

ושלישית, נשנה את הטבלה:

table.remove (מילה חדשה ("כלב"));

עכשיו אם ננסה לחזור על הטבלה, נקבל ConcurrentModificationException:

בעוד (it.hasNext ()) {מפתח המילה = it.next (); }

java.util.ConcurrentModificationException ב java.util.Hashtable $ Enumerator.next (Hashtable.java:1378)

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

5.2. לא נכשל מהר: ספירה

ספירה ב טבלת גיבוב אינו מהיר כישלון. בואו נסתכל על דוגמא.

ראשית, בואו ניצור a טבלת גיבוב והוסף ערכים אליו:

שולחן Hashtable = Hashtable חדש (); table.put (Word חדש ("1"), "one"); table.put (Word חדש ("2"), "two");

שנית, בואו ניצור ספירה:

ספירה enumKey = table.keys ();

שלישית, בואו ונשנה את הטבלה:

table.remove (מילה חדשה ("1"));

עכשיו אם נעבור דרך הטבלה זה לא ישליך חריג:

בעוד (enumKey.hasMoreElements ()) {מפתח מילים = enumKey.nextElement (); }

5.3. צו איטרציה בלתי צפוי

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

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

לפיכך, בואו נוסיף כמה ערכים ונבדוק את הפלט:

שולחן Hashtable = Hashtable חדש (); table.put (Word חדש ("1"), "one"); table.put (Word חדש ("2"), "two"); // ... table.put (מילה חדשה ("8"), "שמונה"); איטרטור it = table.entrySet (). iterator (); בעוד (it.hasNext ()) {Map.Entry entry = it.next (); // ...}}

חמש ארבע שלוש שתיים שמונה שבע

6. טבלת גיבוב לעומת. מפת גיבוב

טבלת גיבוב ו מפת גיבוב מספקים פונקציונליות דומה מאוד.

שניהם מספקים:

• איטרציה מהירה
• צו איטרציה בלתי צפוי

אבל יש גם כמה הבדלים:

• מפת גיבוב אינו מספק ספירה, בעוד טבלת גיבוב מספק לא נכשל במהירות ספירה
• טבלת גיבוב לא מאפשר ריק מפתחות ו ריק ערכים, בעוד מפת גיבוב האם מאפשרים אחד כזה ריק מקש וכל מספר של ריק ערכים
• טבלת גיבובהשיטות מסונכרנות בזמן HashMapsהשיטות אינן

7. טבלת גיבוב ממשק API ב- Java 8

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

7.1. getOrDefault ()

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

לפני Java 8:

מפתח מילים = מילה חדשה ("כלב"); הגדרת מחרוזת; אם (table.containsKey (key)) {definition = table.get (key); } אחר {definition = "לא נמצא"; }

אחרי Java 8:

definition = table.getOrDefault (מפתח, "לא נמצא");

7.2. putIfAbsent ()

נניח שאנחנו צריכים לשים מילה "חתול“ רק אם זה עדיין לא נמצא במילון.

לפני Java 8:

אם (! table.containsKey (מילה חדשה ("חתול"))) {table.put (מילה חדשה ("חתול"), הגדרה); }

אחרי Java 8:

table.putIfAbsent (מילה חדשה ("חתול"), הגדרה);

7.3. הסר בוליאני ()

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

לפני Java 8:

אם (table.get (Word חדש ("חתול")). שווה ("בעל חיים")) {table.remove (מילה חדשה ("חתול")); }

אחרי Java 8:

תוצאה בוליאנית = table.remove (מילה חדשה ("חתול"), "חיה");

לבסוף, בעודו זקן לְהַסִיר() השיטה מחזירה את הערך, השיטה החדשה מחזירה בוליאני.

7.4. החלף()

נניח שעלינו להחליף הגדרה של "חתול", אך רק אם ההגדרה הישנה שלה היא "יונק טורף קטן מבוית".

לפני Java 8:

if (table.containsKey (מילה חדשה ("חתול")) && table.get (מילה חדשה ("חתול")). שווה ("יונק טורף קטן מבוית")) {table.put (מילה חדשה ("חתול") ), הגדרה); }

אחרי Java 8:

table.replace (מילה חדשה ("חתול"), "יונק טורף קטן מבוית", הגדרה);

7.5. computeIfAbsent ()

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

table.computeIfAbsent (מילה חדשה ("חתול"), מפתח -> "חיה");

לפיכך, השורה הנ"ל שווה ערך ל:

if (! table.containsKey (cat)) {הגדרת מחרוזת = "חיה"; // שימו לב שחישובים מתרחשים בתוך אם block.put חסום (Word חדש ("חתול"), הגדרה); }

7.6. computeIfPresent ()

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

נניח שעלינו לשנות את ההגדרה:

table.computeIfPresent (cat, (key, value) -> key.getName () + "-" + value);

לפיכך, השורה הנ"ל שווה ערך ל:

אם (table.containsKey (cat)) {מחרוזת concatination = cat.getName () + "-" + table.get (cat); table.put (חתול, ריכוז); }

7.7. לְחַשֵׁב()

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

מחרוזת [] בעלי חיים = {"חתול", "כלב", "כלב", "חתול", "ציפור", "עכבר", "עכבר"};

כמו כן, אנו רוצים ליצור a טבלת גיבוב המכיל בעל חיים כמפתח ומספר התרחשויותיו כערך.

להלן פיתרון:

שולחן Hashtable = Hashtable חדש (); עבור (מחרוזת חיה: בעלי חיים) {table.compute (חיה, (מפתח, ערך) -> (ערך == null? 1: ערך + 1)); }

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

assertThat (table.values ​​(), hasItems (2, 2, 2, 1));

7.8. לְמַזֵג()

יש דרך נוספת לפתור את המשימה הנ"ל:

עבור (חיה מחרוזת: בעלי חיים) {table.merge (חיה, 1, (oldValue, value) -> (oldValue + value)); }

הטיעון השני, 1, הוא הערך הממופה למפתח אם המפתח עדיין לא על השולחן. אם המפתח כבר נמצא בטבלה, אנו מחשבים אותו כ- oldValue + 1.

7.9. לכל אחד()

זו דרך חדשה לחזור על הערכים. בואו נדפיס את כל הערכים:

table.forEach ((k, v) -> System.out.println (k.getName () + "-" + v)

7.10. החלף הכל()

בנוסף, אנו יכולים להחליף את כל הערכים ללא איטרציה:

table.replaceAll ((k, v) -> k.getName () + "-" + v);

8. מסקנה

במאמר זה תארנו את מטרת מבנה טבלת החשיש והראינו כיצד לסבך מבנה טבלה של כתובת ישירה כדי להשיג אותה.

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

לבסוף, דיברנו על טבלת גיבובהמאפיינים ו- API 8 ספציפי ל- Java.

כרגיל, קוד המקור השלם זמין ב- Github.