טבלת גיבוב – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
Badidipedia (שיחה | תרומות) אין תקציר עריכה |
Badidipedia (שיחה | תרומות) אין תקציר עריכה |
||
שורה 1:
[[תמונה:HASHTB08-he.svg|ממוזער|362px|שמאל|ספר טלפונים קטן כטבלת גיבוב. ניתן לראות כיצד המפתחות השמיים מוחלפות באינדקסים מספריים באמצעות [[פונקציית גיבוב]]; כך ניתן לגשת לרשומות.]]
ב[[מדעי המחשב]], '''טבלת גיבוב''' ('''Hash table'''), היא [[מבנה נתונים]] [[מילון (מבנה נתונים)|מילוני]], שמקשר [[מפתח (מדעי המחשב)|מפתחות]] עם ערכים. הפעולה העיקרית שבה הוא תומך ביעילות היא אחזור מידע מתוך מבנה הנתונים: בהינתן מפתח נתון (למשל שם של אדם), מצא את הערך המתאים (למשל מספר הטלפון של אותו אדם). המבנה עובד על ידי הפיכת המפתח באמצעות [[פונקציית גיבוב]] למספר סידורי המייצג למעשה את האינדקס של ה[[מערך (מבנה נתונים)|מערך]]. ניתן לומר, אם כן, כי טבלת גיבוב היא מעין מערך שאליו ניתן לגשת באמצעות מפתחות, ולא אינדקסים.
==סיבוכיות זמן השבת ערך בטבלת גיבוב==
כמו במבנה הנתונים [[מערך (מבנה נתונים)|מערך]], טבלת הגיבוב מאפשרת בדיקת נתון ב[[סיבוכיות זמן]] ממוצעת של (Θ(1 - ללא תלות במספר האלמנטים בטבלה. אולם, במקרה הגרוע ביותר, הבדיקה עשויה להתבצע בסיבוכיות זמן טובה פחות, של (O(n, כאשר n מייצג את מספר האיברים בטבלה. בהשוואה למבני מערך, טבלאות גיבוב מועילות כאשר יש לאחסן מספר גדול של רשומות ובמיוחד כאשר גודל קבוצת הנתונים ניתן לחיזוי.
| |||