גיבוב ליניארי

גיבוב ליניארי (Linear probing) הוא שיטת תכנות לפתרון התנגשויות בתוך טבלאות גיבוב - מבני נתונים לשמירה על אוסף של זוגות מפתח וערך. הוא הומצא בשנת 1954 על ידי ג 'ין אמדל, איליין מ. מק' גרו, וארתור סמואל הראשון, ונותח בשנת 1963 על ידי דונלד קנות'.

ההתנגשות בין ג 'ון סמית' סנדרה די (hashing תא 873) היא נפתרת על ידי הצבת סנדרה במיקום הבא שריק, תא 874.

יחד עם double hashing, גיבוב ליניארי הוא סוג של מיעון פתוח. כלומר כל תא מכיל זוג אחד של מפתח-ערך. כאשר פונקציית גיבוב גורמת להתנגשות (כלומר היא מיפתה מפתח למקום שתפוס על ידי ערך אחר בטבלה) נבדוק האם התא הבא בטבלה ריק וכך נמשיך עד למציאת מקום ריק. חיפוש מבוצע באותו אופן, על ידי חיפוש בטבלה החל במיקום שניתן על ידי פונקציית הגיבוב, עד למציאת תא עם התאמת מפתח או תא ריק. במחיקה איננו יכולים להשאיר את התא ריק משום שלאחר מכן בחיפוש נוכל לטעות ולכן במחיקה נשמור בתא דגל לציון המחיקה.

ניתוח

שימוש בגיבוב ליניארי יכול להיות מיושם כך שתוחלת מספר הפעולות קבועה. במילים אחרות, פעולות הוספה הסרה וחיפוש יכולות להיות מיושם בממוצע - (1)O, כל עוד מקדם העומס של טבלת הגיבוב הוא קטן מאחד.