גיבוב קוקייה – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ הגהה |
Luckas-bot (שיחה | תרומות) מ r2.7.1) (בוט מוסיף: cs:Kukaččí hašování |
||
שורה 13: | שורה 13: | ||
[[en:Cuckoo hashing]] |
[[en:Cuckoo hashing]] |
||
[[cs:Kukaččí hašování]] |
|||
[[de:Kuckucks-Hashing]] |
[[de:Kuckucks-Hashing]] |
||
[[lt:Gegutės maiša]] |
[[lt:Gegutės maiša]] |
גרסה מ־15:00, 26 ביוני 2011
גיבוב קוקייה (מאנגלית: Cuckoo hashing) הוא שיטה במדעי המחשב ליישוב התנגשויות בטבלת גיבוב. בשיטה זו, כל איבר ממופה לשני תאים או יותר במערך. כאשר מכניסים איבר חדש למערך, בודקים אם אחד מהתאים אליהם האיבר ממופה פנוי. אם כן, ממקמים בו את האיבר החדש. אם כל התאים אליהם האיבר החדש ממופה תפוסים, ממקמים את האיבר החדש באחד מהתאים התפוסים, ומעבירים את האיבר ששכן בתא קודם לכן לאחד מתאיו האלטרנטיביים.
מקור השם נובע משיטות הקינון של זנים מסוימים של ציפור הקוקייה. הקוקייה מטילה את ביציה בקניהן של ציפורים אחרות. כאשר גוזל הקוקייה בוקע מן הביצה, הוא דוחף את הביצים או את הגוזלים האחרים מן הקן.
השיטה תוארה לראשונה על ידי רסמוס פאף (Rasmus Pagh) ופלמינג פריש רודלר (Flemming Friche Rodler) בשנת 2001.
קישורים חיצוניים
- Static cuckoo hashtable generator for C/C++
- Cuckoo hashtable written in Java
- Generic Cuckoo hashmap in Java