טבלת גיבוב
מתוך ויקיפדיה, האנציקלופדיה החופשית
 |
יש לשכתב ערך זה ייתכנו לכך מספר סיבות: ייתכן שהמידע המצוי בדף זה מכיל טעויות, או שהניסוח וצורת הכתיבה שלו אינם מתאימים לוויקיפדיה. אתם מוזמנים לסייע ולתקן את הבעיות בדף זה, אך אנא אל תורידו את ההודעה כל עוד לא תוקן הדף. אם אתם סבורים כי אין בדף בעיה, ניתן לציין זאת בדף השיחה שלו. |
במדעי המחשב, טבלת גיבוב, היא מבנה נתונים שמקשר מפתחות עם ערכים. הפעולה העיקרית שבה הוא תומך ביעילות היא בדיקה: בהינתן מפתח (למשל שם של אדם), מצא את הערך המתאים (למשל מספר הטלפון של אותו אדם). המבנה עובד על ידי הפיכת המפתח באמצעות פונקציית גיבוב למספר שהמבנה משתמש בו כדי לאתר את הערך הרצוי.
[עריכה] סיבוכיות זמן ושימושים נפוצים בטבלאות גיבוב
טבלאות גיבוב משמשות לעתים למימוש מערכים אסוציאטיביים,קבוצות, ומטמון (אזור אחסון של נתונים שלהם יזדקק המחשב בתדירות גבוהה). כמו מבנה המערך, טבלת הגיבוב מאפשרת בדיקת נתון בסיבוכיות זמן ממוצעת של(O(1 ללא תלות במספר האלמנטים בטבלה. אולם, במקרה הגרוע ביותר והנדיר הבדיקה עשויה להתבצע בסיבוכיות זמן פחות טובה של (O(n. בהשוואה למבני מערך, טבלאות גיבוב מועילות כאשר יש לאחסן מספר גדול של רשומות ובמיוחד כאשר גודל קבוצת הנתונים ניתן לחיזוי.
בשח ממוחשב, טבלת גיבוב משמשת בדרך כלל למימוש טבלת מעברים.
[עריכה] סוגים של טבלאות גיבוב
- שיטת העץ המאורך- הנתונים נשמרים בתבנית של עץ ברוש מצוי באופן זה מהירות צמיחת העץ לינארית.
- שיטת הקיפול הכפול- הנתונים נשמרים בצורת נדבכים/ערימה, וניתן לארגן אותם גם בצורה כפולה.
- שיטת יוהן- הנתונים בשיטה זו נשמרים באופן רציף כך שסופו של הנתון האחד היא תחילתו של הנתון השני.
זמן החיפוש של פעולת חיפוש בטבלה זו הוא לינארי.
