גיבוב קוקייה – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ אין בנתיים הערות שוליים |
הגהה קלה |
||
| שורה 1: | שורה 1: | ||
'''גיבוב |
'''גיבוב קוקייה''' (מאנגלית '''Cuckoo hashing''') היא שיטה לישוב התנגשויות ב[[טבלת גיבוב]]. בשיטה זו, כל איבר ממופה לשתיים או יותר תאים במערך. כאשר מכניסים איבר חדש למערך, בודקים אם אחד מהתאים אליהם האיבר ממופה פנוי. אם כן, ממקמים את האיבר החדש באחד מהתאים. אם כל התאים אליהם האיבר החדש ממופה תפוסים, ממקמים את האיבר החדש באחד מהתאים התפוסים, ומעבירים את האיבר ששכן בתא קודם לכן לאחד מתאיו האלטרנטיביים. |
||
מקור השם נובע משיטות הקינון של ציפור ה[[קוקייה]]. הקוקייה מטילה את ביציה בקניהן של ציפורים אחרות. כאשר גוזל הקוקייה בוקע מן הביצה, הוא דוחף את הביצים או את הגוזלים האחרים מן הקן. השיטה תוארה לראשונה על ידי Rasmus Pagh ו-Flemming Friche Rodler ב-2001. |
|||
== ראו גם == |
== ראו גם == |
||
גרסה מ־00:05, 22 בפברואר 2011
גיבוב קוקייה (מאנגלית Cuckoo hashing) היא שיטה לישוב התנגשויות בטבלת גיבוב. בשיטה זו, כל איבר ממופה לשתיים או יותר תאים במערך. כאשר מכניסים איבר חדש למערך, בודקים אם אחד מהתאים אליהם האיבר ממופה פנוי. אם כן, ממקמים את האיבר החדש באחד מהתאים. אם כל התאים אליהם האיבר החדש ממופה תפוסים, ממקמים את האיבר החדש באחד מהתאים התפוסים, ומעבירים את האיבר ששכן בתא קודם לכן לאחד מתאיו האלטרנטיביים.
מקור השם נובע משיטות הקינון של ציפור הקוקייה. הקוקייה מטילה את ביציה בקניהן של ציפורים אחרות. כאשר גוזל הקוקייה בוקע מן הביצה, הוא דוחף את הביצים או את הגוזלים האחרים מן הקן. השיטה תוארה לראשונה על ידי Rasmus Pagh ו-Flemming Friche Rodler ב-2001.