טבלת גיבוב – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ ויקישיתוף בשורה |
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'''), היא [[מבנה נתונים]] [[מילון (מבנה נתונים)|מילוני]], שנותן גישה [[רשומה|לרשומה]] באמצעות [[מפתח (מדעי המחשב)|המפתח]] המתאים לה. המבנה עובד באמצעות הפיכת המפתח על ידי [[פונקציית גיבוב]], למספר המייצג אינדקס ב[[מערך (מבנה נתונים)|מערך]] שמפנה אל הרשומה המבוקשת. הפעולה העיקרית שבה היא תומכת ביעילות היא אחזור מידע מתוך מבנה הנתונים: בהינתן מפתח נתון (למשל שם של אדם), מצא את הרשומה המתאימה (למשל מספר הטלפון של אותו אדם). ▼
|תמונה = [[קובץ:HASHTB08-he.svg|300px]]
|כתובית = ספר טלפונים קטן כטבלת גיבוב. ניתן לראות כיצד המפתחות השמיים מוחלפים באמצעות [[פונקציית גיבוב]] לאינדקסים מספריים וכך ניתן לגשת לרשומות
|תאריך המצאה = [[1953]]
|זיכרון ממוצע = {{משמאל לימין|O(n)}}
|זיכרון במקרה הגרוע = {{משמאל לימין|O(n)}}
|קישור חיפוש = #פעולת חיפוש
|חיפוש ממוצע = {{משמאל לימין|O(1)}}
|חיפוש במקרה הגרוע = {{משמאל לימין|O(n)}}
|קישור הכנסה = #פעולת הכנסה
|הכנסה ממוצע = {{משמאל לימין|O(1)}}
|הכנסה במקרה הגרוע = {{משמאל לימין|O(n)}}
|הוצאה ממוצע = {{משמאל לימין|O(1)}}
|הוצאה במקרה הגרוע = {{משמאל לימין|O(n)}}
▲
הרעיון לטבלת הגיבוב הופיע כבר ב[[1953]] במזכר פנימי בחברת [[IBM]] שפורסם על ידי ה.פ. לון (H. P. Luhn) ובמקביל פותחה על ידי ג'ין אמדל (Gene amdahl), ה.מ בוהם (E. M. Boehme), נתניאל רוצ'סטר (Nathaniel Rochester) וארתור סמואל (Arthur Samuel) תוכנית שמשתמשת בגיבוב. כאשר למדען המחשב הרוסי אנדריי ארשוב (Andrey Ershov), היה את אותו רעיון כמו לאמדל.
| |||