גיבוב ליניארי
גיבוב ליניארי (Linear probing) היא שיטת תכנות לפתרון התנגשויות בתוך טבלאות גיבוב - מבני נתונים לשמירה על אוסף של זוגות מפתח וערך. הוא הומצא בשנת 1954 על ידי ג 'ין אמדל, איליין מ. מק' גרו, ארתור סמואל הראשון ניתח בשנת 1963 על ידי דונלד קנות'.
יחד עם double hashing, גיבוב ליניארי, הוא סוג של מיעון פתוח. כלומר כל תא מכיל זוג אחד של מפתח-ערך. כאשר פונקציית גיבוב גורמת להתנגשות (כלומר היא מיפתה מפתח למקום שתפוס ע״י ערך אחר בטבלה) נבדוק האם התא הבא בטבלה ריק וכך נמשיך עד למציאת מקום ריק. חיפוש מבוצע באותו אופן, על ידי חיפוש בטבלה החל במיקום שניתן על ידי פונקציית הגיבוב, עד למציאת תא עם התאמת מפתח או תא ריק. במחיקה איננו יכולים להשאיר את התא ריק משום שלאחר מכן בחיפוש נוכל לטעות ולכן במחיקה נשמור בתא דגל לציון המחיקה.
ניתוח
שימוש בגיבוב ליניארי יכול להיות מיושם כך שתוחלת מספר הפעולות קבועה. במילים אחרות, להוסיף, להסיר, פעולות החיפוש יכול להיות מיושם ב - (O(1, כל עוד מקדם העומס של טבלת הגיבוב הוא קטן מאחד.[1]
הערות שוליים
- ^ Knuth, Donald (1963), Notes on "Open" Addressing, אורכב מ-המקור ב-2016-03-03
