טבלת גיבוב

הרעיון לטבלת גיבוב התגלה כבר ב-1953 במזכר של H. P. Luhn ועבודות מקבילות של חוקרים אחרים, כולל ג'ין אמדל. גם אנדריי ארשוב הגיע לרעיונות דומים.

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

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

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

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

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

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

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

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

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

בטבלה סגורה אפשר לקשר כל תא לרשימה מקושרת או לעץ מאוזן (למשל AVL או B+). עצים אלה מקצרים את הזמן במקרה הגרוע ל-O(log n). בטבלה פתוחה יש מספר שיטות פרובינג שונות לטיפול בהתנגשויות.

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

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

יש מערך של תאים. כל תא יכול להכיל ערך או להצביע לרשימה.
דוגמה: מפעל עם 1,000 עובדים. כל עובד שומר בתא שמתאים למספרו.

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

מיעון פתוח: מחפשים תא אחר במערך אם התא תפוס.
מיעון סגור: כל תא מפנה לרשימה של פריטים.

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

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

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