טבלת גיבוב – הבדלי גרסאות

ב[[מדעי המחשב]], '''טבלת גיבוב''' או '''טבלת ערבול''' (באנגלית: '''Hash table'''), היא [[מבנה נתונים]] [[מילון (מבנה נתונים)|מילוני]], שנותן גישה [[רשומה|לרשומה]] באמצעות [[מפתח (מדעי המחשב)|המפתח]] המתאים לה. המבנה עובד באמצעות הפיכת המפתח על ידי [[פונקציית גיבוב]], למספר המייצג אינדקס ב[[מערך (מבנה נתונים)|מערך]] שמפנה אל הרשומה המבוקשת. הפעולה העיקרית שבה היא תומכת ביעילות היא אחזור מידע מתוך מבנה הנתונים: בהינתן מפתח נתון (למשל שם של אדם), מצא את הרשומה המתאימה (למשל מספר הטלפון של אותו אדם).

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

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