טבלת גיבוב – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
Badidipedia (שיחה | תרומות) |
Badidipedia (שיחה | תרומות) אין תקציר עריכה |
||
שורה 8:
כדוגמה לטבלת גיבוב פשוטה נוכל לקחת מפעל קטן שבו רוצים לשמור רשומות המכילות את פרטי העובדים והגישה לרשומות תהיה לפי מספר עובד בן 3 ספרות. כדי לבנות טבלת גיבוב מתאימה, נוכל להשתמש במערך בעל אלף תאים ונבחר פונקציית גיבוב פשוטה שעבור כל מספר עובד, מחזירה את המספר עצמו (<math>\ f(x)=x</math>) ולמעשה מצביעה על כך שאת המידע על העובד שמספרו X נוכל להשיג בתא מספר X. בדוגמה הזאת ביצענו '''מיעון ישיר''' - השתמשנו ב[[פונקציה חד-חד-ערכית]], כלומר, לא קיים יותר ממספר עובד אחד שיופנה לתא מסוים.
פעמים רבות לא ניתן להשתמש להשתמש בפונקציה כזאת, למשל, אם היינו רוצים לגשת לרשומות העובדים בעזרת תעודת הזהות שלהם ושימוש באותה פונקציה אז היינו צריכים להקצות מערך של מיליארד(!) תאים כדי שיתאים לטווח של הפונקציה. הבעיה נוצרת כאשר מספר המפתחות האפשריים, גדול בהרבה מאשר מספר הרשומות שיהיו בטבלת הגיבוב . כדי להתמודד עם הבעיה משתמשים גם בפונקציות שאינן חד-חד-ערכיות, מה שיאפשר שימוש במערך קטן יותר אך יגרור בעיה נוספת של "'''התנגשויות'''", כלומר, הפונקציה מחזירה עבור הרשומה, מספר תא שמתאים גם לרשומה אחרת.
== פתרון בעיית ההתנגשות ==
==סיבוכיות זמן השבת ערך בטבלת גיבוב==▼
כמו במבנה הנתונים [[מערך (מבנה נתונים)|מערך]], טבלת הגיבוב מאפשרת בדיקת נתון ב[[סיבוכיות זמן]] ממוצעת של (Θ(1 - ללא תלות במספר האלמנטים בטבלה. אולם, במקרה הגרוע ביותר, הבדיקה עשויה להתבצע בסיבוכיות זמן טובה פחות, של (O(n, כאשר n מייצג את מספר האיברים בטבלה. בהשוואה למבני מערך, טבלאות גיבוב מועילות כאשר יש לאחסן מספר גדול של רשומות ובמיוחד כאשר גודל קבוצת הנתונים ניתן לחיזוי.▼
קיימות טבלאות מיוחדות הקרויות '''טבלאות גיבוב מושלמות''', המאפשרות השגת נתון ב-(O(1 במקרה הגרוע ביותר. טבלה זו קלה לתחזוק, אך נדרש זמן גדול לבנייתה הראשונית והיא דורשת מקום מורחב יחסית לטבלת גיבוב רגילה.▼
==שימושים שונים לטבלאות גיבוב==▼
טבלאות גיבוב משמשות לעתים למימוש [[מילון (מבנה נתונים)|מערכים אסוציאטיביים]], [[קבוצה (מבנה נתונים)|קבוצות]], ו[[זיכרון מטמון|מטמון]] (אזור אחסון של נתונים שלהם יזדקק המחשב בתדירות גבוהה). ב[[שחמט]] [[מחשב|ממוחשב]], טבלת גיבוב משמשת בדרך כלל למימוש [[טבלת מעברים]], ובמסדי נתונים שונים ניתן להשתמש בטבלת גיבוב להחזקת טבלאות תוכן.▼
טבלת גיבוב היא [[טבלה]] המכילה B תאים. קיימים שני סוגים עיקריים לטבלת הגיבוב הפשוטה (פרט למגוון של [[מבנה נתונים|מבני נתונים]] הנגזרים ממנה): טבלה פתוחה וטבלה סגורה.
שורה 25 ⟵ 18:
קיימת שיטה נוספת לפתרון התנגשויות הנקראת [[גיבוב קוקייה]].
▲==סיבוכיות זמן השבת ערך בטבלת גיבוב==
▲כמו במבנה הנתונים [[מערך (מבנה נתונים)|מערך]], טבלת הגיבוב מאפשרת בדיקת נתון ב[[סיבוכיות זמן]] ממוצעת של (Θ(1 - ללא תלות במספר האלמנטים בטבלה. אולם, במקרה הגרוע ביותר, הבדיקה עשויה להתבצע בסיבוכיות זמן טובה פחות, של (O(n, כאשר n מייצג את מספר האיברים בטבלה. בהשוואה למבני מערך, טבלאות גיבוב מועילות כאשר יש לאחסן מספר גדול של רשומות ובמיוחד כאשר גודל קבוצת הנתונים ניתן לחיזוי.
▲קיימות טבלאות מיוחדות הקרויות '''טבלאות גיבוב מושלמות''', המאפשרות השגת נתון ב-(O(1 במקרה הגרוע ביותר. טבלה זו קלה לתחזוק, אך נדרש זמן גדול לבנייתה הראשונית והיא דורשת מקום מורחב יחסית לטבלת גיבוב רגילה.
▲==שימושים שונים לטבלאות גיבוב==
▲טבלאות גיבוב משמשות לעתים למימוש [[מילון (מבנה נתונים)|מערכים אסוציאטיביים]], [[קבוצה (מבנה נתונים)|קבוצות]], ו[[זיכרון מטמון|מטמון]] (אזור אחסון של נתונים שלהם יזדקק המחשב בתדירות גבוהה). ב[[שחמט]] [[מחשב|ממוחשב]], טבלת גיבוב משמשת בדרך כלל למימוש [[טבלת מעברים]], ובמסדי נתונים שונים ניתן להשתמש בטבלת גיבוב להחזקת טבלאות תוכן.
==מבנים לטבלת גיבוב מתקדמת==
| |||