טבלת גיבוב – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
Orielno Bot (שיחה | תרומות) מ clean up, replaced: התפלגות אחידה ← התפלגות אחידה בדידה באמצעות AWB |
|||
שורה 13:
|הוצאה ממוצע = {{משמאל לימין|O(1)}}
|הוצאה במקרה הגרוע = {{משמאל לימין|O(n)}}
|קישור הוצאה = #פעולת מחיקה}}ב[[מדעי המחשב]], '''טבלת גִּבּוּב''' או '''טבלת ערבול''' (באנגלית: '''Hash table'''), היא [[מבנה נתונים]] [[מילון (מבנה נתונים)|מילוני]], שנותן גישה ל[[רשומה (אחסון נתונים)|רשומה]] באמצעות [[מפתח (מדעי המחשב)|המפתח]] המתאים לה. המבנה עובד באמצעות הפיכת המפתח על ידי [[פונקציית גיבוב]], למספר המייצג אינדקס ב[[מערך (מבנה נתונים)|מערך]] שמפנה אל הרשומה המבוקשת. הפעולה העיקרית שבה היא תומכת ביעילות היא אחזור מידע מתוך מבנה הנתונים: בהינתן מפתח נתון (למשל שם של אדם), מצא את הרשומה המתאימה (למשל מספר הטלפון של אותו אדם).
הרעיון לטבלת הגיבוב הופיע כבר ב-[[1953]] במזכר פנימי בחברת [[IBM]] שפורסם על ידי ה.פ. לון (H. P. Luhn) ובמקביל פותחה על ידי ג'ין אמדל (Gene amdahl), ה.מ בוהם (E. M. Boehme), נתניאל רוצ'סטר (Nathaniel Rochester) וארתור סמואל (Arthur Samuel) תוכנית שמשתמשת בגיבוב. כאשר למדען המחשב הרוסי אנדריי ארשוב (Andrey Ershov), היה את אותו רעיון כמו לאמדל.
שורה 23:
== בעיית ההתנגשות ==
פעמים רבות לא ניתן להשתמש ב"פונקציה חד-חד-ערכית", למשל, אם היינו רוצים לגשת לרשומות עובדים בעזרת מספר תעודת הזהות שלהם ושימוש [[פונקציית הזהות|בפונקציית הזהות]], אז היינו צריכים להקצות מערך של מיליארד(!) תאים כדי שיתאים לטווח של הפונקציה. הבעיה נוצרת כאשר מספר המפתחות האפשריים, גדול בהרבה מאשר מספר הרשומות שיהיו בטבלת הגיבוב. כדי להתמודד עם הבעיה משתמשים גם בפונקציות שאינן חד-חד-ערכיות, מה שיאפשר שימוש במערך קטן יותר אך יגרור בעיה נוספת של '''התנגשויות''', כלומר, הפונקציה מחזירה עבור הרשומה, מספר תא שמתאים גם לרשומה אחרת.
==== טבלה פתוחה וסגורה ====
עבור טבלת גיבוב המכילה מערך עם B תאים. קיימים שני סוגים עיקריים לפתרון בעיית ההתנגשות שנקראים טבלה פתוחה וטבלה סגורה:
'''טבלה פתוחה''' או "מיעון פתוח", פותרת את בעיית ההתנגשות על ידי הקביעה שיש יותר מתא אחד במערך שיכול להפנות לרשומה. למשל, ניתן להשתמש בפונקציית גיבוב שמקבלת בנוסף למפתח, את מספר הניסיונות הכושלים למצוא תא מתאים בטבלה, כך שעבור מספר ניסיון שונה, הפונקציה תחזיר מיקום שונה במערך. טבלת הגיבוב תשתמש בפונקציה כאשר עבור כל ניסיון כושל היא תחשב את הפונקציה מחדש עם הנתון המעודכן עד שימצא מקום פנוי בטבלה. היתרון בשיטה הוא בניצול מקסימלי של המקום, כאשר מספר האיברים המקסימלי הוא B.
'''טבלה סגורה''' פותרת את בעיית ההתנגשות על ידי הפניה מכל תא במערך אל מבנה נתונים שמספק את אותם תכונות כמו טבלת הגיבוב (חיפוש, מחיקה, הוספה וכו'). טבלת הגיבוב משתמשת בפונקציה כדי למצוא את התא המתאים במערך והוא מפנה אל מבנה הנתונים שנותן גישה אל כל הרשומות שנשלחו לתא על ידי הפונקציה. השימוש במבני הנתונים הנוספים, משפיע על מאפייני הטבלה כמו למשל על [[סיבוכיות זמן|סיבוכיות הזמן]] של פעולות הטבלה, המקום ב[[זיכרון גישה אקראית|זיכרון]] שהטבלה תצרוך ומספר הרשומות שיהיה ניתן להכניס לטבלה. דוגמה לכך היא שימוש [[רשימה מקושרת|ברשימות מקושרות]] שכל תא במערך מפנה לאחת מהן. השימוש ברשימה מקושרת, מאפשר להכניס אל טבלת הגיבוב מספר רשומות גדול מ B אבל אם מספר הרשומות (n) יהיה גדול משמעותית מ B, אז לפי [[עקרון שובך היונים]] הרשימות המקושרות תהיינה יותר ארוכות וסיבוכיות הזמן של הטבלה תושפע מהרשימות ותהיה <math>\ O(n)</math>. השימוש במבנה הנתונים הנוסף גם יצרוך יותר מקום בזיכרון בגלל דרישות מבנה הנתונים ובגלל המערך שסביר ויהיו בו יותר תאים ריקים בניגוד לטבלה הפתוחה.
קיימת שיטה נוספת לפתרון התנגשויות הנקראת [[גיבוב קוקייה]].
שורה 38:
== פונקציית הגיבוב ==
{{הפניה לערך מורחב|פונקציית גיבוב}}
פונקציית הגיבוב מתאימה עבור כל מפתח, אינדקס במערך שיוכל להתאים עבורו. כדי שפעולות הטבלה יהיו מהירות, הפונקציה צריכה להתבצע בסיבוכיות נמוכה ביותר ביחס לערכו של המפתח עד כדי שלא יהיו תלויות בו. דרישה נוספת היא שהפונקציה תחזיר ערכים באופן קרוב עד כמה שאפשר ל[[התפלגות אחידה בדידה]]. אם הפונקציה תחזיר ערכים מסוימים בתדירות גבוהה, זמן ביצוע פעולות הטבלה יגדל ואף יכול להגיע לסיבוכיות שתלויה במספר הרשומות בטבלה. החזרת ערכים זהים במערך, יכולה להוביל להעמסה על מבנה הנתונים אליו מפנה המערך בטבלה סגורה מה שיכול להוביל לסיבוכיות גבוהה בהתאם למבנה הנתונים. בטבלה פתוחה כדאי להימנע ממצב בו יצטברו רשומות בגושים. כלומר, בגלל שיטת הגיבוב, מספר ההתנגשויות עבור שימוש בפונקציה יהיה גבוה. למשל, אם פונקציית הגיבוב מטפלת בהתנגשות על ידי בחירה של התא הבא במערך, אז עבור רצף של תאים, נתקל בהתנגשות נוספת עבור כל תא בהמשך הרצף שלא מוביל לרשומה הרצויה. אם מדובר בפעולת הכנסה לטבלה אז הרשומה תוכנס לתא הבא אחרי הרצף והיא תגדיל את הרצף באחד.
== פעולת חיפוש ==
שורה 70:
בטבלה הפתוחה קיימות מספר שיטות לפתירת בעיית ההתנגשות:
* '''[[בדיקה ליניארית]]''' {{אנ|Linear probing}} '''-''' עבור כל התנגשות נבדוק סדרתית האם האינדקס הבא במערך פנוי. שיטה זו קלה לחישוב ולהבנה ושומרת על מקומיות בזיכרון דבר [[מדרג זיכרון|שחוסך גישה]] ל[[דיסק קשיח|דיסק הקשיח]] אך יכולה לצור בעיה של הצטברות רשומות בסדרת אינדקסים ובעקבות כך יהיה מספר גדול של התנגשויות עבור הרשומות באותם באינדקסים. ההצטברות תתהווה משום שעבור כל ניסיון הכנסה של רשומה לצביר רשומות, ההצטברות תגדל בעוד אחד וכך גם מספר האינדקסים שיגדילו את הצביר יגדל באחד.
* '''[[בדיקה ריבועית]]''' {{אנ|Quadratic probing}} '''-''' עבור כל התנגשות נבדק מקום מתאים אחר תוך שימוש בהעלאה בריבוע של מספר ההתנגשויות שהיו עד כה עבור אותו מפתח. הפונקציה עבור הבדיקה הריבועית היא:<math>h(k,i) = ( h(k) + c_1 i + c_2 i^2 ) \mod m</math> כאשר: <math>h</math> - פונקציית הגיבוב, <math>k</math> - המפתח המבוקש, <math>i</math> - מספר ההתנגשויות, <math>m</math> - מספר התאים בטבלה ו<math>c_1,c_2</math> - מספרים קבועים. בשיטה זו אמנם תיתכן הצטברות שתבוא לידי ביטוי בסדרות של תאים מאוכלסים שמתחילות מ<math>h(k)</math> וממשיכות בתאים שבאופן רצוף האינדקס עבורם הוא <math>h(k,i)</math> והם מאוכלסים. ההצטברות מתהווה משום שכל המפתחות שמחזירים <math>h(k)</math> תמיד ינותבו אל אותה סדרת תאים. ההצטברות עבור הבדיקה הריבועית פחות משמעותית מההצטברות המתרחשת עבור הבדיקה הליניארית אך הבדיקה הריבועית שומרת על מקומיות בזיכרון ברמה פחותה.
* '''[[גיבוב כפול]]''' {{אנ|Double hashing}} '''-''' בגיבוב כפול משתמשים בפונקציית גיבוב נוספת כדי לטפל במקרה של התנגשות. הנוסחה עבור גיבוב כפול היא: <math>h(k,i) = ( h_1(k) + i \cdot h_2(k) ) \mod m</math> כאשר <math>k</math> - המפתח המבוקש, <math>h_1,h_2</math> - פונקציות גיבוב, <math>i</math> - מספר ההתנגשויות ו<math>m</math> - מספר התאים בטבלה. ההצטברות בגיבוב כפול מתרחשת רק עבור מפתחות שבאופן נדיר שתי הפונקציות מחזירות עבורם את אותו הערך ובכך עדיפה על הבדיקה הריבועית אבל לא נשמרת המקומיות בכלל.
שורה 88 ⟵ 86:
{{מבני נתונים}}
[[קטגוריה:מבני נתונים]]
| |||