מהי טבלת גיבוב?

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

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

חמש הפעולות העיקריות בטבלת גיבוב הן:

1. Put: אחסון של זוג מפתח וערך, או עדכון הערך אם המפתח כבר קיים.
2. Get: חיפוש הערך של מפתח נתון.
3. ContainsKey: בדיקה אם מפתח מאוחסן בטבלה.
4. Remove: מחיקת זוג מפתח וערך.
5. Size: החזרת מספר הזוגות המאוחסנים כרגע.

בואו ניצור מחלקה HashMap!