גיבוב קוקייה

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

גיבוב קוקייהאנגלית: Cuckoo hashing) הוא שיטה במדעי המחשב ליישוב התנגשויות בטבלת גיבוב. בשיטה זו, כל איבר ממופה לשני תאים במערך. כאשר מכניסים איבר חדש למערך, בודקים אם אחד מהתאים אליהם האיבר ממופה פנוי. אם כן, ממקמים בו את האיבר החדש. אם שני התאים אליהם האיבר החדש ממופה תפוסים, ממקמים את האיבר החדש באחד מהתאים התפוסים, ומעבירים את האיבר ששכן בתא קודם לכן לתא האלטרנטיבי שלו.

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

השיטה תוארה לראשונה על ידי רסמוס פה (Rasmus Pagh) ופלמינג פריש רודלר (Flemming Friche Rodler) בשנת 2001.

הכללות[עריכת קוד מקור | עריכה]

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

קישורים חיצוניים[עריכת קוד מקור | עריכה]

P Computer-science.png ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.