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

{{מבנה נתונים|תמונה = [[תמונהקובץ: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'''), היא [[מבנה נתונים]] [[מילון (מבנה נתונים)|מילוני]], שנותן גישה [[רשומה|לרשומה]] באמצעות [[מפתח (מדעי המחשב)|המפתח]] המתאים לה. המבנה עובד באמצעות הפיכת המפתח על ידי [[פונקציית גיבוב]], למספר המייצג אינדקס ב[[מערך (מבנה נתונים)|מערך]] שמפנה אל הרשומה המבוקשת. הפעולה העיקרית שבה היא תומכת ביעילות היא אחזור מידע מתוך מבנה הנתונים: בהינתן מפתח נתון (למשל שם של אדם), מצא את הרשומה המתאימה (למשל מספר הטלפון של אותו אדם).

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

פונקציית הגיבוב מתאימה עבור כל מפתח, אינדקס במערך שיוכל להתאים עבורו. כדי שפעולות הטבלה יהיו מהירות, הפונקציה צריכה להתבצע בסיבוכיות נמוכה ביותר ביחס לערכו של המפתח עד כדי שלא יהיו תלויות בו. דרישה נוספת היא שהפונקציה תחזיר ערכים באופן קרוב עד כמה שאפשר ל[[התפלגות אחידה]]. במידהאם והפונקציההפונקציה תחזיר ערכים מסוימים בתדירות גבוהה, זמן ביצוע פעולות הטבלה יגדל ואף יכול יכול להגיע לסיבוכיות שתלויה במספר הרשומות בטבלה. החזרת ערכים זהים במערך, יכולה להוביל להעמסה על מבנה הנתונים אליו מפנה המערך בטבלה סגורה מה שיכול להוביל לסיבוכיות גבוהה בהתאם למבנה הנתונים. בטבלה פתוחה כדאי להימנע ממצב בו יצטברו רשומות בגושים. כלומר, בגלל שיטת הגיבוב, מספר ההתנגשויות עבור שימוש בפונקציה יהיה גבוה. למשל, אם פונקציית הגיבוב מטפלת בהתנגשות על ידי בחירה של התא הבא במערך, אז עבור רצף של תאים, נתקל בהתנגשות נוספת עבור כל תא בהמשך הרצף שלא מוביל לרשומה הרצויה. אם מדובר בפעולת הכנסה לטבלה אז הרשומה תוכנס לתא הבא אחרי הרצף והיא תגדיל את הרצף באחד.

עבור פונקציית גיבוב טובה, סיבוכיות הזמן תהיה תלויה במספר ההתנגשויות בזמן חיפוש ערך ותהיה גבוהה יותר ככל שמספר הרשומות בטבלה, מתקרב לגודל המערך (מסומן "B<<n" כאשר B - גודל המערך, n - מספר הרשומות בפועל במערך). הסיבוכיות תהיה תלויה גם בכמות הרשומות שהוכנסו לטבלה אפילו אם הן כבר לא נמצאות בה כיוון שהרבה תאים יסומנו כתאים ש"אוכלסו". כאשר כמות הרשומות אינה גבוהה, מספר ההתנגשויות צפוי להיות בודד ולכן סיבוכיות החיפוש תהיה במקרה הממוצע <math>\ O(1)</math>. במקרה הגרוע של הרבה התנגשויות הסיבוכיות תהיה <math>\ O(n)</math>.

עבור פונקציית גיבוב טובה, כאשר כמות הרשומות באותו סדר גודל של מספר התאים במערך (מסומן "B~n"), סיבוכיות החיפוש תהיה במקרה הממוצע <math>\ O(1)</math> כיוון שבכל מבנה נתונים יהיה בממוצע מספר בודד של רשומות. במקרה הגרוע, הסיבוכיות תהיה כמו הסיבוכיות במקרה הגרוע של מבנה הנתונים בו משתמשים.

עבור הכנסה בטבלה פתוחה, גם כאשר מוצאים תא שהיה בעבר מאוכלס, מכניסים לתוכו את הרשומה. סיבוכיות ההכנסה עבור פונקציה טובה וטבלה שמספר הרשומות בה קטן באופן משמעותי ממספר התאים, תהיה במקרה הממוצע <math>\ O(1)</math>. במקרה הגרוע של הרבה התנגשויות הסיבוכיות תהיה <math>\ O(n)</math>.

עבור טבלה סגורה, ניתן להשתמש במבנה הנתונים [[רשימה מקושרת]] ולמרותואף על פי שבמקרה הגרוע, היעילות תהיה <math>\ O(n)</math> עבור כל אחת משלושתמשלוש הפעולות, קלות התפיסה של פעולת הרשימות המקושרות והתכנות שלהם, יכולים לפצות על כך. ניתן להשתמש גם ב[[עץ חיפוש]] מאוזן כמו [[עץ AVL]] ו[[עץ B Plus|עץ B+]] שיקטינו את החיפוש במקרה הגרוע ל <math>\ O(\log n)</math>. ב[[מערכת זמן אמת|מערכות זמן אמת]] בהם זמן ביצוע פעולה הוא קריטי גם במקרה הגרוע, בחירה במבני נתונים אלו יכולה לשפר את ביצועי המערכת.

* '''[[בדיקה לינארית]]''' {{אנ|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> - מספר התאים בטבלה. ההצטברות בגיבוב כפול מתרחשת רק עבור מפתחות שבאופן נדיר שנישתי הפונקציות מחזירות עבורם את אותו הערך ובכך עדיפה על הבדיקה הריבועית אבל לא נשמרת המקומיות בכלל.