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