טבלת גיבוב – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
Badidipedia (שיחה | תרומות) |
Matanyabot (שיחה | תרומות) מ בוט החלפות: תיתכן\1 |
||
שורה 59:
* '''[[בדיקה לינארית]]''' {{אנ|Linear probing}} '''-''' עבור כל התנגשות נבדוק סדרתית האם האינדקס הבא במערך פנוי. שיטה זו קלה לחישוב ולהבנה ושומרת על מקומיות בזיכרון דבר [[מדרג זיכרון|שחוסך גישה]] ל[[דיסק קשיח|דיסק הקשיח]] אך יכולה לצור בעיה של הצטברות רשומות בסדרת אינדקסים ובעקבות כך יהיה מספר גדול של התנגשויות עבור הרשומות באותם באינדקסים. ההצטברות תתהווה בגלל שעבור כל ניסיון הכנסה של רשומה לצביר רשומות, ההצטברות תגדל בעוד אחד וכך גם מספר האינדקסים שיגדילו את הצביר יגדל באחד.
* '''[[בדיקה ריבועית]]''' {{אנ|Quadratic probing}} '''-''' עבור כל התנגשות נבדק מקום מתאים אחר תוך שימוש בהעלאה בריבוע של מספר ההתנגשויות שהיו עד כה עבור אותו מפתח. הפונקציה עבור הבדיקה הריבועית היא:<math>h(k,i) = ( h(k) + c_1 i + c_2 i^2 ) \mod m</math> כאשר: <math>h</math> - פונקציית הגיבוב, <math>k</math> - המפתח המבוקש, <math>i</math> - מספר ההתנגשויות, <math>m</math> - מספר התאים בטבלה ו<math>c_1,c_2</math> - מספרים קבועים. בשיטה זו אמנם
* '''[[גיבוב כפול]]''' {{אנ|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> - מספר התאים בטבלה. ההצטברות בגיבוב כפול מתרחשת רק עבור מפתחות שבאופן נדיר שני הפונקציות מחזירות עבורם את אותו הערך ובכך עדיפה על הבדיקה הריבועית אבל לא נשמרת המקומיות בכלל.
| |||