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

תוכן שנמחק תוכן שנוסף

בשורה

גרסה מ־05:11, 17 בדצמבר 2011

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

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

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

הכללות

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

קישורים חיצוניים

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

@@ שורה 1: / שורה 1: @@
-'''גיבוב קוקייה''' (מ[[אנגלית]]: '''Cuckoo hashing''') הוא שיטה ב[[מדעי המחשב]] ליישוב [[התנגשות (מדעי המחשב)|התנגשויות]] ב[[טבלת גיבוב]]. בשיטה זו, כל איבר ממופה לשני תאים או יותר במערך. כאשר מכניסים איבר חדש למערך, בודקים אם אחד מהתאים אליהם האיבר ממופה פנוי. אם כן, ממקמים בו את האיבר החדש. אם כל התאים אליהם האיבר החדש ממופה תפוסים, ממקמים את האיבר החדש באחד מהתאים התפוסים, ומעבירים את האיבר ששכן בתא קודם לכן לאחד מתאיו האלטרנטיביים.
+'''גיבוב קוקייה''' (מ[[אנגלית]]: '''Cuckoo hashing''') הוא שיטה ב[[מדעי המחשב]] ליישוב [[התנגשות (מדעי המחשב)|התנגשויות]] ב[[טבלת גיבוב]]. בשיטה זו, כל איבר ממופה לשני תאים במערך. כאשר מכניסים איבר חדש למערך, בודקים אם אחד מהתאים אליהם האיבר ממופה פנוי. אם כן, ממקמים בו את האיבר החדש. אם כל התאים אליהם האיבר החדש ממופה תפוסים, ממקמים את האיבר החדש באחד מהתאים התפוסים, ומעבירים את האיבר ששכן בתא קודם לכן לתא אלטרנטיבי.
 מקור השם נובע משיטות ה[[קן|קינון]] של זנים מסוימים של ציפור ה[[קוקייה]]. הקוקייה מטילה את ביציה בקניהן של ציפורים אחרות. כאשר גוזל הקוקייה בוקע מן הביצה, הוא דוחף את הביצים או את הגוזלים האחרים מן הקן.
 השיטה תוארה לראשונה על ידי רסמוס פאף (Rasmus Pagh) ופלמינג פריש רודלר (Flemming Friche Rodler) בשנת [[2001]].
+==הכללות==
+ווריציה אחת של גיבוב קוקיה ממפה כל איבר ליותר משני תאים. ווריאציה אחרת מאפשרת לכל תא להכיל יותר מאיבר אחד. ווריאציות אלו מגדילות את ניצולת הזכרון אך מגדילות את הזמן הנדרש להכניס איבר.
 ==קישורים חיצוניים==
 * [http://www.theiling.de/projects/lookuptable.html Static cuckoo hashtable generator for C/C++]