יחידה 7: טבלאות גיבוב (Hash Tables)

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

עקרונות הגיבוב ופונקציית הגיבוב

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

תכונות של פונקציית גיבוב טובה:

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

דוגמאות נפוצות לפונקציות גיבוב כוללות פעולת מודולו (key % table_size), קיפול (folding) או שיטות מורכבות יותר המשלבות הזזות ביטים ופעולות XOR.

התנגשויות ופתרונן

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

קיימות שתי גישות עיקריות לפתרון התנגשויות:

גיבוב פתוח מול גיבוב סגור

גיבוב פתוח (Separate Chaining)

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

גיבוב סגור (Open Addressing)

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

שיטות בדיקה נפוצות בגיבוב סגור:

• בדיקה ליניארית (Linear Probing): אם תא h(key) תפוס, נבדקים התאים h(key)+1, h(key)+2, ... מודולו גודל הטבלה.
  אשכולות ראשוניים (Primary Clustering): חסרון מרכזי של בדיקה ליניארית. התנגשויות גורמות ליצירת "אשכולות" של תאים תפוסים. ככל שהאשכול גדל, כך גדלה ההסתברות שמפתחות חדשים יגובבו לתוכו, מה שמגדיל אותו עוד יותר ומפחית את יעילות הטבלה באופן דרמטי. זהו נושא קריטי לבחינה!
• בדיקה ריבועית (Quadratic Probing): אם תא h(key) תפוס, נבדקים התאים h(key)+1^2, h(key)+2^2, ... מודולו גודל הטבלה. מפחיתה אשכולות ראשוניים אך עלולה ליצור אשכולות משניים.
• גיבוב כפול (Double Hashing): משתמשת בשתי פונקציות גיבוב: אחת לקביעת האינדקס הראשוני (h1(key)) ושנייה לקביעת גודל הצעד לבדיקה (h2(key)). האינדקסים הנבדקים הם h1(key), h1(key)+h2(key), h1(key)+2*h2(key), .... זו השיטה הטובה ביותר להפחתת אשכולות בגיבוב סגור.

יעילות טבלאות גיבוב

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

• עבור גיבוב פתוח (Separate Chaining), α יכול להיות גדול מ-1. ככל שα גדל, כך גדל אורך הרשימות המקושרות והביצועים יורדים.
• עבור גיבוב סגור (Open Addressing), α חייב להיות קטן מ-1. ככל שα מתקרב ל-1, כך גדל הסיכוי להתנגשויות, זמן החיפוש אחר תא פנוי מתארך דרמטית, והביצועים צונחים.

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

ביצועים במקרה הגרוע: במקרה הגרוע (לדוגמה, פונקציית גיבוב גרועה שממפה את כל המפתחות לאותו תא, או התנגשויות רבות), הביצועים יכולים להידרדר ל-O(n), בדומה לרשימה מקושרת או מערך לא ממוין.

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

שאלות לדיון

• תיאר/י מצב שבו גיבוב פתוח (Separate Chaining) יהיה עדיף על גיבוב סגור (Open Addressing), ומצב הפוך. נמק/י את בחירתך תוך התייחסות למאפייני הנתונים והפעולות.
• מהי המשמעות של "אשכולות ראשוניים" (Primary Clustering) בגיבוב סגור? הסבר/י כיצד בדיקה ליניארית תורמת לתופעה זו וכיצד גיבוב כפול (Double Hashing) מנסה להתמודד איתה.
• כיצד גורם העומס (α) משפיע על יעילות טבלת גיבוב, הן בגיבוב פתוח והן בגיבוב סגור? מתי נצטרך לבצע "גיבוב מחדש" (Rehashing) ומדוע?

נקודות לתשובת מודל

• השוואת גיבוב פתוח/סגור:
  • גיבוב פתוח עדיף: כאשר מספר הפריטים אינו ידוע מראש ויכול לגדול מאוד, או כאשר יש צורך במחיקות תכופות. פחות רגיש לגורם עומס גבוה.
  • גיבוב סגור עדיף: כאשר יש מגבלות זיכרון חמורות (אין מקום למצביעים נוספים), או כאשר יש חשיבות ל-cache locality. מתאים יותר לטבלאות עם גודל קבוע יחסית ומספר פריטים שלא עולה על גודל הטבלה.
• אשכולות ראשוניים:
  • הגדרה: הצטברות של תאים תפוסים בטבלה, היוצרים "גושים" גדולים.
  • בדיקה ליניארית: כאשר מתרחשת התנגשות, בדיקה ליניארית מחפשת את התא הפנוי הבא ברצף. אם התא הבא תפוס, היא ממשיכה הלאה, ובכך "מאריכה" את האשכול הקיים. ככל שהאשכול ארוך יותר, כך גדל הסיכוי שמפתח חדש יגובב לתוכו ויאריך אותו עוד יותר, מה שמוביל לירידה דרמטית בביצועים.
  • גיבוב כפול: משתמש בשתי פונקציות גיבוב כדי לקבוע את גודל הצעד לבדיקה. זה מבטיח שכל מפתח יקבל רצף בדיקה שונה, ובכך מפזר את המפתחות באופן אחיד יותר ומצמצם משמעותית את תופעת האשכולות.
• גורם העומס ו-Rehashing:
  • השפעה על יעילות: גורם העומס (α) משפיע ישירות על אורך שרשראות החיפוש. ככל שα גבוה יותר, כך אורך השרשראות גדל, וזמן הגישה הממוצע מתקרב ל-O(n).
  • גיבוב פתוח: α יכול להיות > 1. הביצועים יורדים באופן ליניארי עם α.
  • גיבוב סגור: α חייב להיות < 1. הביצועים יורדים באופן אקספוננציאלי ככל שα מתקרב ל-1.
  • Rehashing: נדרש כאשר α עובר סף מסוים (לדוגמה, 0.7-0.8 בגיבוב סגור, או 1.0 בגיבוב פתוח). המטרה היא להקטין את α על ידי הגדלת גודל הטבלה, ובכך לשמור על ביצועים ממוצעים של O(1). למרות שזו פעולה יקרה (O(n)), היא מתרחשת לעיתים רחוקות יחסית, ולכן הביצועים הממוצעים נשארים טובים.