מבני נתונים ומבוא לאלגוריתמים

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

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

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

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

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

פעולות בסיסיות

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

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

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

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

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

שרשור (Chaining)

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

כתובות פתוחות (Open Addressing)

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

שיטות לפתרון התנגשויות בכתובות פתוחות

בדיקה לינארית (Linear Probing)

כאשר אינדקס h(k) תפוס, בודקים את התאים הבאים ברצף: (h(k) + 1) mod m, (h(k) + 2) mod m, וכן הלאה, עד שנמצא תא פנוי. פשוטה ליישום אך סובלת מבעיית צבירה ראשונית (primary clustering) הפוגעת בביצועים.

בדיקה ריבועית (Quadratic Probing)

כאשר אינדקס h(k) תפוס, בודקים את התאים הבאים לפי סדר ריבועי: (h(k) + 1^2) mod m, (h(k) + 2^2) mod m, וכן הלאה. מפחיתה צבירה ראשונית אך עלולה לסבול מצבירה משנית (secondary clustering) ואינה מבטיחה למצוא תא פנוי אם הטבלה מלאה למחצה.

גיבוב כפול (Double Hashing)

משתמשים בשתי פונקציות גיבוב: h1(k) לאינדקס הראשוני, ו-h2(k) לקביעת גודל הצעד בבדיקות הבאות. סדרת הבדיקות היא: (h1(k) + i * h2(k)) mod m. נחשבת לשיטה הטובה ביותר מבין כתובות פתוחות, מפזרת טוב יותר ומפחיתה צבירה.

ניתוח ביצועים

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

פקטור עומס (Load Factor, α): היחס בין מספר האיברים בטבלה (n) לגודל הטבלה (m). כלומר, α = n/m. ככל ש-α גבוה יותר, כך גדל הסיכוי להתנגשויות ופוחתים הביצועים.

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

מורכבות זמן (Time Complexity)

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

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

שאלות לדיון

הסבירו מדוע פקטור עומס (α) גבוה מסוכן יותר עבור טבלאות גיבוב בשיטת כתובות פתוחות מאשר בשיטת שרשור.
תארו מצב שבו פונקציית גיבוב פשוטה כמו h(k) = k mod m עלולה להיות גרועה במיוחד. הציעו פתרון.
השוו בין בדיקה לינארית לגיבוב כפול במונחים של ביצועים במקרה הממוצע והגרוע, וציינו יתרונות וחסרונות של כל אחת.
כיצד ניתן להתמודד עם מצב שבו טבלת הגיבוב מתמלאת ופקטור העומס הופך גבוה מדי?

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

פקטור עומס: בכתובות פתוחות, α > 1 אינו אפשרי. ככל ש-α מתקרב ל-1, מספר הבדיקות הממוצע עולה באופן אקספוננציאלי, מכיוון שיש פחות תאים פנויים. בשרשור, α יכול להיות גדול מ-1, והביצועים מידרדרים לינארית עם α (אורך הרשימות המקושרות).
פונקציית גיבוב גרועה: אם המפתחות מגיעים בדפוס מסוים (למשל, כולם זוגיים ו-m הוא זוגי), או כולם כפולות של מספר מסוים, פונקציית k mod m עלולה למפות את כולם למספר קטן של תאים, מה שיוביל להתנגשויות רבות. פתרון: שימוש בפונקציית גיבוב אוניברסלית (Universal Hashing) או פונקציה שמערבבת את הביטים טוב יותר (למשל, שיטת הכפל).
השוואה בין בדיקה לינארית לגיבוב כפול:
- לינארית: יתרון - פשוטה ליישום, ניצול טוב של מטמון (cache). חיסרון - צבירה ראשונית חמורה, ביצועים מידרדרים במהירות עם α.
- גיבוב כפול: יתרון - מפזרת טוב יותר, מפחיתה צבירה ראשונית ומשנית, ביצועים טובים יותר במקרה הממוצע. חיסרון - מורכבת יותר ליישום (דורשת שתי פונקציות גיבוב).
- בשניהם, מקרה גרוע הוא O(n).
התמודדות עם טבלה מלאה/פקטור עומס גבוה: יש לבצע שינוי גודל דינמי (Dynamic Resizing) או גיבוב מחדש (Rehashing). זה כרוך ביצירת טבלת גיבוב חדשה וגדולה יותר (לרוב בגודל ראשוני גדול יותר, למשל הכפלת הגודל), והכנסה מחדש של כל האיברים מהטבלה הישנה לחדשה. פעולה זו יקרה (O(n)) אך מתרחשת לעיתים רחוקות, מה ששומר על ממוצע O(1) לפעולות.

מצאתם טעות או שחסר משהו?