טבלת גיבוב (ערבול) - איך מקבלים גישה ב-O(1)?
ההסבר המלא לאחד ממבני הנתונים החשובים ביותר: פונקציית Hash, התנגשויות ויחס העומס.
טבלת Hash (Hash Table, או Hash Map) היא מבנה נתונים שמאחסן זוגות מפתח-ערך ומאפשר חיפוש, הוספה ומחיקה ב-O(1) ממוצע. זה אחד ממבני הנתונים הנפוצים ביותר - בכל שפת תכנות מודרנית קיים מימוש שלו (dict בפייתון, HashMap ב-Java, Object/Map ב-JavaScript).
הרעיון המרכזי - פונקציית Hash
פונקציית Hash ממירה מפתח (מחרוזת, מספר, אובייקט) לאינדקס במערך. אנחנו מחשבים index = hash(key) % size ושומרים את הערך שם. בחיפוש - מחשבים את אותו hash ומגיעים ישירות לערך.
function simpleHash(str, size) {
let hash = 0;
for (const ch of str) {
hash = (hash * 31 + ch.charCodeAt(0)) % size;
}
return hash;
}
// 'apple' -> some index between 0 and size-1התנגשויות (Collisions)
כשתי מפתחות שונים מתמפים לאותו אינדקס, יש התנגשות. שתי שיטות נפוצות לטיפול:
- Chaining - בכל תא שומרים רשימה מקושרת של זוגות שהתמפו לשם
- Open Addressing - מחפשים את התא הריק הבא לפי כלל מסוים (לדוגמה, linear probing)
יחס עומס (Load Factor)
Load Factor = n/m, כאשר n הוא מספר האלמנטים ו-m גודל המערך. כשה-load factor עולה מעל סף (בדרך כלל 0.7-0.75), מבצעים rehashing - הגדלת הטבלה ומחשבים מחדש את כל המיקומים.
הסיבוכיות O(1) היא ממוצעת. במקרה הגרוע, כשכל המפתחות מתמפים לאותו תא, גישה הופכת ל-O(n). פונקציית hash טובה ו-load factor נמוך מבטיחים שזה לא יקרה בפועל.
מתי להשתמש?
- ספירת תדירויות (counting frequencies)
- בדיקת שייכות מהירה (set membership)
- מטמון (caching) ו-memoization בתכנון דינמי
- מציאת כפילויות / זוגות שמסכמים לערך נתון
טיפ לראיונות: שאלות רבות ב-LeetCode נפתרות על ידי הוספת hash table - שיפור מ-O(n²) ל-O(n) במחיר של O(n) זיכרון נוסף.
שאלות נפוצות
איך טבלת גיבוב משיגה גישה ב-O(1)?
במקום לחפש את המפתח, הטבלה מחשבת אותו. פונקציית הגיבוב ממירה את המפתח למספר, ומודולו גודל הטבלה הופכת אותו לאינדקס במערך. החישוב אינו תלוי במספר האיברים המאוחסנים, ולכן הגישה היא O(1) בממוצע — בניגוד לחיפוש שדורש מעבר על איברים או ירידה בעץ.
מה זה התנגשות ואיך פותרים אותה?
התנגשות היא כששני מפתחות שונים ממופים לאותו אינדקס — בלתי נמנע כשמספר המפתחות האפשריים גדול מגודל הטבלה. שתי שיטות הפתרון העיקריות הן שרשור, שבו כל תא מחזיק רשימה של כל האיברים שמופו אליו, וכתובת פתוחה, שבה מחפשים את התא הפנוי הבא לפי סדר בדיקה קבוע.
מהו יחס העומס ולמה הוא חשוב?
יחס העומס הוא מספר האיברים המאוחסנים חלקי מספר התאים בטבלה. ככל שהוא עולה, ההתנגשויות מתרבות והביצועים מתדרדרים מ-O(1) לכיוון O(n). לכן מימושים מעשיים מגדילים את הטבלה ומגבבים מחדש את כל האיברים כשהיחס חוצה סף — בדרך כלל 0.75 — ובכך שומרים על הביצועים הממוצעים.