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

 

קיימת שיטה נוספת לפתרון התנגשויות הנקראת [[גיבוב קוקייה]].

 

== פונקציית הגיבוב ==

 

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

 

== שיטות גיבוב ==

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

 

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