Loading AI tools
שיטת תכנות מוויקיפדיה, האנציקלופדיה החופשית
גיבוב ליניארי (Linear probing) הוא שיטת תכנות לפתרון התנגשויות בתוך טבלאות גיבוב - מבני נתונים לשמירה על אוסף של זוגות מפתח וערך. הוא הומצא בשנת 1954 על ידי ג 'ין אמדל, איליין מ. מק' גרו, וארתור סמואל הראשון, ונותח בשנת 1963 על ידי דונלד קנות'.
יחד עם double hashing, גיבוב ליניארי הוא סוג של מיעון פתוח. כלומר כל תא מכיל זוג אחד של מפתח-ערך. כאשר פונקציית גיבוב גורמת להתנגשות (כלומר היא מיפתה מפתח למקום שתפוס על ידי ערך אחר בטבלה) נבדוק האם התא הבא בטבלה ריק וכך נמשיך עד למציאת מקום ריק. חיפוש מבוצע באותו אופן, על ידי חיפוש בטבלה החל במיקום שניתן על ידי פונקציית הגיבוב, עד למציאת תא עם התאמת מפתח או תא ריק. במחיקה איננו יכולים להשאיר את התא ריק משום שלאחר מכן בחיפוש נוכל לטעות ולכן במחיקה נשמור בתא דגל לציון המחיקה.
שימוש בגיבוב ליניארי יכול להיות מיושם כך שתוחלת מספר הפעולות קבועה. במילים אחרות, פעולות הוספה הסרה וחיפוש יכולות להיות מיושם בממוצע - (1)O, כל עוד מקדם העומס של טבלת הגיבוב הוא קטן מאחד.[1]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.