ויקיפדיה

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

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמתהעריכה הבאה ←
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
הורדת הפסקה "מבנים לטבלת גיבוב מתקדמת", בהתאם לנאמר בדף השיחה.
שורה 57:
 
בטבלה הפתוחה קיימות מספר שיטות לפתירת בעיית ההתנגשות:
* '''[[בדיקה לינארית]]''' {{אנ|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> - מספרים קבועים. בשיטה זו אמנם תתכן הצטברות שתבוא לידי ביטוי בסדרות של תאים מאוכלסים שמתחילות מ<math>h(k)</math> וממשיכות בתאים שבאופן רצוף האינדקס עבורם הוא <math>h(k,i)</math> והם מאוכלסים. ההצטברות מתהווה בגלל שכל המפתחות שמחזירים <math>h(k)</math> תמיד ינותבו אל אותה סדרת תאים. ההצטברות עבור הבדיקה הריבועית פחות משמעותית מההצטברות המתרחשת עבור הבדיקה הלינארית אך הבדיקה הריבועית שומרת על מקומיות בזיכרון ברמה פחותה.
▲'''בדיקה לינארית''' '''-''' עבור כל התנגשות נבדוק סדרתית האם האינדקס הבא במערך פנוי. שיטה זו קלה לחישוב ולהבנה ושומרת על מקומיות בזיכרון דבר [[מדרג זיכרון|שחוסך גישה]] ל[[דיסק קשיח|דיסק הקשיח]] אך יכולה לצור בעיה של הצטברות רשומות בסדרת אינדקסים ובעקבות כך יהיה מספר גדול של התנגשויות עבור הרשומות באותם באינדקסים. ההצטברות תתהווה בגלל שעבור כל ניסיון הכנסה של רשומה לצביר רשומות, ההצטברות תגדל בעוד אחד וכך גם מספר האינדקסים שיגדילו את הצביר יגדל באחד.
 
* '''בדיקה[[גיבוב ריבועיתכפול]]''' {{אנ|Double hashing}} '''-''' עבורבגיבוב כלכפול התנגשותמשתמשים נבדקבפונקציית מקוםגיבוב מתאיםנוספת אחרכדי תוךלטפל שימוש בהעלאה בריבועבמקרה של מספר ההתנגשויות שהיו עד כה עבור אותו מפתחהתנגשות. הפונקציההנוסחה עבור הבדיקהגיבוב הריבועיתכפול היא: <math>h(k,i) = ( hh_1(k) + c_1 i +\cdot c_2 i^2h_2(k) ) \mod m</math> כאשר: <math>hk</math> - פונקצייתהמפתח הגיבובהמבוקש, <math>kh_1,h_2</math> - המפתחפונקציות המבוקשגיבוב, <math>i</math> - מספר ההתנגשויות, ו<math>m</math> - מספר התאים בטבלה ו<math>c_1,c_2</math> - מספרים קבועים. בשיטהההצטברות זובגיבוב אמנםכפול תתכןמתרחשת הצטברותרק שתבואעבור לידימפתחות ביטוישבאופן בסדרותנדיר שלשני תאיםהפונקציות מאוכלסים שמתחילות מ<math>h(k)</math> וממשיכות בתאים שבאופן רצוף האינדקסמחזירות עבורם הואאת <math>h(k,i)</math>אותו והםהערך מאוכלסים.ובכך ההצטברותעדיפה מתהווה בגלל שכל המפתחות שמחזירים <math>h(k)</math> תמיד ינותבו אל אותה סדרת תאים. ההצטברות עבורעל הבדיקה הריבועית פחות משמעותית מההצטברות המתרחשת עבור הבדיקה הלינארית אך הבדיקה הריבועית שומרת עלאבל מקומיותלא בזיכרוןנשמרת ברמההמקומיות פחותהבכלל.
 
'''גיבוב כפול -''' בגיבוב כפול משתמשים בפונקציית גיבוב נוספת כדי לטפל במקרה של התנגשות. הנוסחה עבור גיבוב כפול היא: <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> - מספר התאים בטבלה. ההצטברות בגיבוב כפול מתרחשת רק עבור מפתחות שבאופן נדיר שני הפונקציות מחזירות עבורם את אותו הערך ובכך עדיפה על הבדיקה הריבועית אבל לא נשמרת המקומיות בכלל.
 
==שימושים שונים לטבלאות גיבוב==
אוחזר מתוך "https://he.wikipedia.org/wiki/טבלת_גיבוב"