8.4 טבלאות גיבוב (hash tables)

מבנה נתונים ואלגוריתמים

 

 

8.4.1 טבלאות כתובת ישירות (Direct Address Tables)

אם יש לנו אוסף פריטים בעל n אלמנטים שהמפתחות שלהם הם מספרים שלמים ייחודיים בטווח של (m,1), כאשר m>=n, אזי אנו יכולים לאחסן את הפריטים בטבלת כתובת ישירה - T(m), כאשר T_i יכול להיות ריק או להכיל פריטים מהאוסף.

 

 

 

חיפוש בטבלת כתובת ישירה הוא פעולה בסדר

גודל של O(1) :

עבור מפתח k, ניגש לתא T_k.

·        אם התא מכיל פריט - אז יש להחזירו.

·        אם התא לא מכיל פריט - אז יש להחזיר NULL.

 

 

 

קיימים שני אילוצים לגבי טבלאות מסוג זה:

1.      המפתחות חייבים להיות ייחודיים.

2.      הטווח של המפתח חייב להיות תחום.

 

 

 

אם המפתחות אינם ייחודיים, אזי ניתן לבנות סט של

 m רשימות, ולאחסן את ראשי הרשימות בטבלה.

 הזמן הנדרש כדי למצוא פריט יישאר עדיין O(1).

 

 

בכל אופן, אם לכל פריט באוסף הנתונים יש תכונה מבדילה

כלשהי אחרת (מלבד המפתח שלו), וכאשר המספר העותקים

המקסימלי הוא n_dup^max, אזי חיפוש פריט מסוים ידרוש

O(n_dup^max). אם העותקים הם היוצא מן הכלל ולא הכלל

עצמו, אזי  n_dup^max הינו קטן בהרבה מאשר n, וטבלת כתובת

ישירה תספק ביצוע טוב. אך אם n_dup^max קרוב ל- n, אזי זמן

החיפוש של כל פריט הוא O(n), ומבנה של עץ יהיה יעיל

 יותר.

 

 

 

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

 

כתובת ישירה מוכללת בקלות למקרה שבו יש פונקציה h(k)=>(1,m), אשר ממפה כל ערך של המפתח k, בטווח של (1,m).

במקרה כזה נמקם פריט ב- T[h(k)] במקום ב- T[k], ונוכל לחפש ב- O(1) כמו קודם.

 

 

8.4.2 פונקציות מיפוי

גישת הכתובת הישירה דורשת כי הפונקציה h(k), הינה מיפוי של אחד לאחד עבור כל k למספר שלם בטווח (1,m). פונקציה כזו נקראת פונקצית גיבוב מושלמת (perfect hashing function), והיא ממפה כל מפתח למספר שלם שונה בטווח, ומאפשרת לבנות באופן פשוט טבלה שבה זמן החיפוש הוא O(1).

 

לרוע המזל, מציאת פונקציה כזו אינה אפשרית תמיד. ניתן למצוא פונקצית גיבוב (hash function) h(k), אשר ממפה את רוב המפתחות אל ערכים שלמים ייחודיים, אך עם זאת ממפה מספר מפתחות אל אותו

ערך שלם. אם מספר ההתנגשויות (collisions) (מקרים שמספר מפתחות ממופים אל אותו ערך שלם) קטן יחסית, אז טבלת גיבוב פועלת בצורה טובה ומאפשרת זמני חיפוש של O(1).

 

טיפול בהתנגשויות

במספר קטן של מקרים, שבהם מספר מפתחות ממופים אל אותו ערך, פריטים עם מפתחות שונים

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

 

1.      שרשור (chaining).

2.      אזור גלישה (overflow area).

3.      גיבוב חוזר (re-hashing).

4.      בדיקה לינארית (linear probing).

5.      בדיקה ריבועית (quadratic probing).

 

שרשור

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

 

 

גיבוב חוזר  

בטכניקה זו נעשה שימוש נוסף בפונקצית גיבוב

כאשר ישנן התנגשויות. אם לאחר מכן עדיין

ישנן התנגשויות, ממשיכים עד שמוצאים תא פנוי.

המשך השימוש בפונקצית הגיבוב יכול להיות

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

 

 

 

                                                            h(i)=h(k), ולכן נעשה שימוש

                                                            בפונקצית הגיבוב הבאה h₁ .

                                                            שוב מתרחשת התנגשות, ולכן

                                                            נעשה שימוש ב- h_2.

 

 

 

 

בדיקה לינארית

אחת מפונקציות הגיבוב החוזר הפשוטות ביותר היא +1 (או -1). כלומר, במקרה של התנגשות יש לחפש בתא השכן. חישוב הכתובת החדשה הוא מהיר ויעיל מאד במעבד RISC מודרני בשל ניצול יעיל של זיכרון המטמון. בדיקה לינארית מועדת לתופעה הנקראת הצטברות ראשונית (primary clustering) - היווצרות של רצפים ארוכים של תאים תפוסים, המאריכה את זמן החיפוש הממוצע.   

 

בדיקה ריבועית

בדרך כלל ניתן לראות ביצועים טובים יותר בשיטה זו שבה פונקצית הגיבוב המשנית תלויה בערך הגיבוב הקודם:

address=h(key) + ci²

 

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

תופעה של הצטברות משנית (secondary clustering). זוהי צורה מתונה יותר של הצטברות, והיא חמורה פחות מההצטברות הראשונית הנגרמת מבדיקה לינארית.

 

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

 

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

 

אזור גלישה (Overflow area)

בשיטה זו מחולקת הטבלה, לפני ההקצאה, לשני אזורים: האזור הראשי  (Primary area) - שבו המפתחות ממופים ואזור עבור התנגשויות שבדרך כלל נקרא אזור גלישה (Overflow area).

 

 

 

בעת התנגשות, הפריט החדש נכנס אל תא באזור הגלישה,

ונוצר קישור בין התא מהאזור הראשי לבין תא זה, בדומה

לשרשור רגיל, מלבד העובדה שאזור הגלישה מוקצה קודם,

ולכן נגישה אליו מהירה יותר. כמו בשיטת הגיבוב החוזר, גם

במקרה זה יש צורך לדעת מראש את מספר הפריטים האמורים

להיות מאוחסנים, אך כאן יש לקחת בחשבון שני פרמטרים:

הגודל האופטימלי של האזור הראשי והגודל האופטימלי של

אזור הגלישה.

 

אפשר כמובן לתכנן מערכות עם מספר אזורי גלישה או עם

אזור גלישה עבור אזור הגלישה, דבר המאפשר גמישות ללא

איבוד היתרונות של שיטת אזור הגלישה.

 

 

סיכום - ארגון טבלאות גיבוב

 

 

 

מושגים

 

טבלת גיבוב

טבלה שבה ניתן לחפש פריט בזמן של O(1), על ידי שימוש בפונקצית גיבוב הממירה

            ערך של מפתח לכתובת.

פונקצית גיבוב

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

התנגשות

מתרחשת כאשר פונקצית גיבוב ממפה שני מפתחות שונים לאותה כתובת בטבלה.

בדיקה לינארית (linear probing)

שיטת גיבוב חוזר פשוטה שבה בעת התנגשות עוברים לתא השכן בטבלה.

בדיקה ריבועית (quadratic probing)

טכניקת גיבוב חוזר שבה נעשה שימוש בפונקציה מסדר גבוה (לרוב מסדר 2) של ערך

הגיבוב, על מנת לחשב את הכתובת.

הצטברות ראשונית

נטייה של תאים סמוכים להתמלא כתוצאה מהבדיקה הלינארית.

הצטברות משנית

רצף התנגשויות הנגרם על ידי חישוב כתובות בשיטת הבדיקה הריבועית.

פונקצית גיבוב מושלמת

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

 

 

המשך ל: פונקציות גיבוב                חזור ל: תוכן עניינים