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

תוכן שנמחק תוכן שנוסף
אין תקציר עריכה
שורה 6:
טבלת הגיבוב מורכבת ממערך, והתאים שבו מפנים לרשומה הרצויה. כדי להגיע אל התא הרצוי נעשה שימוש בפונקציה שנקראת '''פונקציית גיבוב''' או פונקציית ערבול. הפונקציה מקבלת את המפתח של הרשומה ומחזירה את מספר התא שמפנה אל הרשומה אם היא קיימת. הפונקציה משמשת לחיפוש רשומה רצויה, מציאת מקום מתאים עבור הכנסה של רשומה חדשה, ומציאת המקום של רשומה שצריך למחוק.
 
כדוגמה לטבלת גיבוב פשוטה נוכל לקחת מפעל קטן שבו רוצים לשמור רשומות המכילות את פרטי העובדים והגישה לרשומות תהיה לפי מספר עובד בן 3 ספרות. כדי לבנות טבלת גיבוב מתאימה, נוכל להשתמש במערך בעל אלף תאים ונבחר פונקציית גיבוב פשוטה שעבור כל מספר עובד, מחזירה את המספר עצמו ([[פונקציית הזהות]]) ולמעשה מצביעה על כך שאת המידע על העובד שמספרו X נוכל להשיג בתא מספר X. בדוגמה הזאת ביצענו '''מיעון ישיר''' - השתמשנו ב"[[פונקציה חד-חד-ערכית]]", כלומר, לא קיים יותר ממספר עובד אחד שיופנה לתא מסוים.
 
== בעיית ההתנגשות ==
פעמים רבות לא ניתן להשתמש להשתמש בפונקציהב"פונקציה חד-חד-ערכית", למשל, אם היינו רוצים לגשת לרשומות עובדים בעזרת מספר תעודת הזהות שלהם ושימוש [[פונקציית הזהות|בפונקציית הזהות]], אז היינו צריכים להקצות מערך של מיליארד(!) תאים כדי שיתאים לטווח של הפונקציה. הבעיה נוצרת כאשר מספר המפתחות האפשריים, גדול בהרבה מאשר מספר הרשומות שיהיו בטבלת הגיבוב . כדי להתמודד עם הבעיה משתמשים גם בפונקציות שאינן חד-חד-ערכיות, מה שיאפשר שימוש במערך קטן יותר אך יגרור בעיה נוספת של '''התנגשויות''', כלומר, הפונקציה מחזירה עבור הרשומה, מספר תא שמתאים גם לרשומה אחרת.
 
==== טבלה פתוחה וסגורה ====
שורה 19:
 
קיימת שיטה נוספת לפתרון התנגשויות הנקראת [[גיבוב קוקייה]].
 
== פונקציית הגיבוב ==
פונקציית הגיבוב מתאימה עבור כל מפתח, אינדקס במערך שיוכל להתאים עבורו. כדי שפעולות הטבלה יהיו מהירות, הפונקציה צריכה להתבצע בסיבוכיות נמוכה ביותר ביחס לערכו של המפתח עד כדי שלא יהיו תלויות בו. דרישה נוספת היא שהפונקציה תחזיר ערכים באופן קרוב עד כמה שאפשר ל[[התפלגות אחידה]]. במידה והפונקציה תחזיר ערכים מסוימים בתדירות גבוהה, זמן ביצוע פעולות הטבלה יגדל ואף יכול יכול להגיע לסיבוכיות שתלויה במספר הרשומות בטבלה.
 
==סיבוכיות זמן השבת ערך בטבלת גיבוב==