מה זה האשינג

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

מה זה HashMap

HashMap הוא חלק ממסגרת אוסף Java. הוא משתמש בטכניקה שנקראת Hashing. הוא מיישם את ממשק המפה. הוא מאחסן את הנתונים בצמד של מפתח וערך. HashMap מכיל מערך של הצמתים, והצומת מיוצג כמחלקה. הוא משתמש במערך ובמבנה נתונים LinkedList באופן פנימי לאחסון מפתח וערך. ישנם ארבעה שדות ב-HashMap.

לפני שתבין את העבודה הפנימית של HashMap, עליך להיות מודע לשיטת hashCode() ו- equals().

חריתיק רושן

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

הכנס מפתח, צמד ערכים ב-HashMap

אנו משתמשים בשיטת put() כדי להוסיף את צמד המפתח והערך ב-HashMap. גודל ברירת המחדל של HashMap הוא 16 (0 עד 15).

דוגמא

בדוגמה הבאה, אנו רוצים להוסיף שלושה זוג (מפתח, ערך) ב-HashMap.

 HashMap map = new HashMap(); map.put('Aman', 19); map.put('Sunny', 29); map.put('Ritesh', 39); 

בואו נראה באיזה אינדקס יישמר צמד הערכים המפתח ב-HashMap. כאשר אנו קוראים לשיטת put() אז היא מחשבת את קוד ה-hash של המפתח 'Aman'. נניח שקוד ה-hash של 'אמן' הוא 2657860. כדי לאחסן את המפתח בזיכרון, עלינו לחשב את האינדקס.

bfs ו-dfs

חישוב אינדקס

אינדקס ממזער את גודל המערך. הנוסחה לחישוב המדד היא:

 Index = hashcode(Key) & (n-1) 

כאשר n הוא גודל המערך. מכאן שערך המדד עבור 'אמן' הוא:

 Index = 2657860 & (16-1) = 4 

הערך 4 הוא ערך האינדקס המחושב שבו המפתח והערך יאוחסנו ב- HashMap.

Hash Collision

זה המקרה כאשר ערך האינדקס המחושב זהה עבור שני מפתחות או יותר. בואו לחשב את קוד ה-hash עבור מפתח אחר 'Sunny'. נניח שקוד ה-hash עבור 'Sunny' הוא 63281940. כדי לאחסן את המפתח בזיכרון, עלינו לחשב אינדקס באמצעות נוסחת האינדקס.

 Index=63281940 & (16-1) = 4 

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

לולאת תוכנית java

באופן דומה, נאחסן את המפתח 'ריטש'. נניח שקוד ה-hash עבור המפתח הוא 2349873. ערך האינדקס יהיה 1. לפיכך מפתח זה יאוחסן באינדקס 1.

שיטת get() ב-HashMap

שיטת get() משמשת כדי לקבל את הערך לפי המפתח שלו. זה לא יביא את הערך אם אתה לא יודע את המפתח. כאשר קוראים לשיטת get(K Key), היא מחשבת את קוד ה-hash של המפתח.

נניח שעלינו להביא את המפתח 'אמן'. השיטה הבאה תיקרא.

 map.get(new Key('Aman')); 

הוא מייצר את קוד ה-hash כ-2657860. כעת חשב את ערך האינדקס של 2657860 באמצעות נוסחת אינדקס. ערך המדד יהיה 4, כפי שחישבנו לעיל. חיפוש שיטת get() עבור ערך האינדקס 4. הוא משווה את האלמנט הראשון Key עם המפתח הנתון. אם שני המפתחות שווים, הוא מחזיר את הערך else check עבור האלמנט הבא בצומת אם הוא קיים. בתרחיש שלנו, הוא נמצא כאלמנט הראשון של הצומת ומחזיר את הערך 19.

בוא נביא מפתח אחר 'Sunny'.

קוד ה-hash של מפתח 'Sunny' הוא 63281940. ערך האינדקס המחושב של 63281940 הוא 4, כפי שחישבנו עבור שיטת put(). עבור לאינדקס 4 של המערך והשווה את המפתח של האלמנט הראשון למפתח הנתון. זה גם משווה את Keys. בתרחיש שלנו, המפתח הנתון הוא האלמנט השני, והשני של הצומת הוא null. הוא משווה את האלמנט השני Key עם המפתח שצוין ומחזיר את הערך 29. הוא מחזיר null אם הבא בצומת הוא null.