טבלת גיבוב

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
Gnome-colors-emblem-development-2.svg הערך נמצא בשלבי עבודה: כדי למנוע התנגשויות עריכה ועבודה כפולה אתם מתבקשים שלא לערוך ערך זה בטרם תוסר הודעה זו, אלא אם כן תיאמתם זאת עם מניחי התבנית.
אם הדף לא נערך במשך שבוע ניתן להסיר את התבנית ולערוך אותו, אך רצוי לתת קודם תזכורת בדף שיחת הכותבים.
ספר טלפונים קטן כטבלת גיבוב. ניתן לראות כיצד המפתחות השמיים מוחלפות באינדקסים מספריים באמצעות פונקציית גיבוב; כך ניתן לגשת לרשומות.

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

מבנה טבלת הגיבוב[עריכת קוד מקור | עריכה]

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

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

בעיית ההתנגשות[עריכת קוד מקור | עריכה]

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

טבלה פתוחה וסגורה[עריכת קוד מקור | עריכה]

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

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

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

קיימת שיטה נוספת לפתרון התנגשויות הנקראת גיבוב קוקייה.

פונקציית הגיבוב[עריכת קוד מקור | עריכה]

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

סיבוכיות זמן השבת ערך בטבלת גיבוב[עריכת קוד מקור | עריכה]

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

שימושים שונים לטבלאות גיבוב[עריכת קוד מקור | עריכה]

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

מבנים לטבלת גיבוב מתקדמת[עריכת קוד מקור | עריכה]

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

זמן החיפוש של פעולת חיפוש בטבלה זו הוא לינארי.

ראו גם[עריכת קוד מקור | עריכה]