טבלת גיבוב – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
Badidipedia (שיחה | תרומות) ממציאים |
Badidipedia (שיחה | תרומות) הוספת תבנית:מבנה נתונים |
||
שורה 1:
{{בעבודה}}
{{מבנה נתונים|תמונה = [[תמונה:HASHTB08-he.svg|300px]]|כתובית = ספר טלפונים קטן כטבלת גיבוב. ניתן לראות כיצד המפתחות השמיים מוחלפים באינדקסים מספריים באמצעות [[פונקציית גיבוב]]; כך ניתן לגשת לרשומות|תאריך המצאה = [[1953]]|זיכרון ממוצע = {{ltr|O(n)}}|זיכרון במקרה הגרוע = {{ltr|O(n)}}|קישור חיפוש = #פעולת חיפוש|חיפוש ממוצע = {{ltr|O(1)}}|חיפוש במקרה הגרוע = {{ltr|O(n)}}|קישור הכנסה = #פעולת הכנסה|הכנסה ממוצע = {{ltr|O(1)}}|הכנסה במקרה הגרוע = {{ltr|O(n)}}|הוצאה ממוצע = {{ltr|O(1)}}|הוצאה במקרה הגרוע = {{ltr|O(n)}}|קישור הוצאה = #פעולת מחיקה}}ב[[מדעי המחשב]], '''טבלת גיבוב''' או '''טבלת ערבול''' (באנגלית: '''Hash table'''), היא [[מבנה נתונים]] [[מילון (מבנה נתונים)|מילוני]], שנותן גישה [[רשומה|לרשומה]] באמצעות [[מפתח (מדעי המחשב)|המפתח]] המתאים לה. המבנה עובד באמצעות הפיכת המפתח על ידי [[פונקציית גיבוב]], למספר המייצג אינדקס ב[[מערך (מבנה נתונים)|מערך]] שמפנה אל הרשומה המבוקשת. הפעולה העיקרית שבה היא תומכת ביעילות היא אחזור מידע מתוך מבנה הנתונים: בהינתן מפתח נתון (למשל שם של אדם), מצא את הרשומה המתאימה (למשל מספר הטלפון של אותו אדם). ▼
▲ב[[מדעי המחשב]], '''טבלת גיבוב''' או '''טבלת ערבול''' (באנגלית: '''Hash table'''), היא [[מבנה נתונים]] [[מילון (מבנה נתונים)|מילוני]], שנותן גישה [[רשומה|לרשומה]] באמצעות [[מפתח (מדעי המחשב)|המפתח]] המתאים לה. המבנה עובד באמצעות הפיכת המפתח על ידי [[פונקציית גיבוב]], למספר המייצג אינדקס ב[[מערך (מבנה נתונים)|מערך]] שמפנה אל הרשומה המבוקשת. הפעולה העיקרית שבה היא תומכת ביעילות היא אחזור מידע מתוך מבנה הנתונים: בהינתן מפתח נתון (למשל שם של אדם), מצא את הרשומה המתאימה (למשל מספר הטלפון של אותו אדם).
הרעיון לטבלת הגיבוב הופיע כבר ב[[1953]] במזכר פנימי בחברת [[IBM]] שפורסם על ידי ה.פ. לון (H. P. Luhn) ובמקביל פותחה על ידי ג'ן אמדל (Gene amdahl), ה.מ בוהם (E. M. Boehme), נתניאל רוצ'סטר (Nathaniel Rochester) וארתור סמואל (Arthur Samuel) תוכנית שמשתמשת בגיבוב. כאשר למדען המחשב הרוסי אנדריי ארשוב (Andrey Ershov), היה את אותו רעיון כמו לאמדל.
שורה 28 ⟵ 27:
פונקציית הגיבוב מתאימה עבור כל מפתח, אינדקס במערך שיוכל להתאים עבורו. כדי שפעולות הטבלה יהיו מהירות, הפונקציה צריכה להתבצע בסיבוכיות נמוכה ביותר ביחס לערכו של המפתח עד כדי שלא יהיו תלויות בו. דרישה נוספת היא שהפונקציה תחזיר ערכים באופן קרוב עד כמה שאפשר ל[[התפלגות אחידה]]. במידה והפונקציה תחזיר ערכים מסוימים בתדירות גבוהה, זמן ביצוע פעולות הטבלה יגדל ואף יכול יכול להגיע לסיבוכיות שתלויה במספר הרשומות בטבלה. החזרת ערכים זהים במערך, יכולה להוביל להעמסה על מבנה הנתונים אליו מפנה המערך בטבלה סגורה מה שיכול להוביל לסיבוכיות גבוהה בהתאם למבנה הנתונים. בטבלה פתוחה כדאי להימנע ממצב בו יצטברו רשומות בגושים. כלומר, בגלל שיטת הגיבוב, מספר ההתנגשויות עבור שימוש בפונקציה יהיה גבוה. למשל, אם פונקציית הגיבוב מטפלת בהתנגשות על ידי בחירה של התא הבא במערך, אז עבור רצף של תאים, נתקל בהתנגשות נוספת עבור כל תא בהמשך הרצף שלא מוביל לרשומה הרצויה. אם מדובר בפעולת הכנסה לטבלה אז הרשומה תוכנס לתא הבא אחרי הרצף והיא תגדיל את הרצף באחד.
== פעולת חיפוש
כדי לחפש ערך בטבלה משתמשים בפונקציית הגיבוב שמקבלת כמשתנה את המפתח של הרשומה המבוקשת כאשר המטרה היא שהערך שהפונקציה מחזירה יוביל אותנו אל הרשומה.
שורה 46 ⟵ 45:
בטבלה סגורה ההכנסה מתבצעת באמצעות מציאת המקום המתאים בטבלה על ידי פונקציית הגיבוב ואז שימוש בפונקציית ההכנסה של מבנה הנתונים הנוסף אתו עובדים. סיבוכיות ההכנסה תהיה כמו בחיפוש.
== פעולת
גם הוצאת רשומה מטבלת הגיבוב דומה לחיפוש.
| |||