טבלת גיבוב (ערבול) - איך מקבלים גישה ב-O(1)?

טבלת 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 - הגדלת הטבלה ומחשבים מחדש את כל המיקומים.

מתי להשתמש?

• ספירת תדירויות (counting frequencies)
• בדיקת שייכות מהירה (set membership)
• מטמון (caching) ו-memoization בתכנון דינמי
• מציאת כפילויות / זוגות שמסכמים לערך נתון