טבלת גיבוב

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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