מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/טבלאות ערבול

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

כדאי לדעת: #יש למעשה סוגים רבים של טבלאות ערבול. אנו נתמקד בטבלאות מסוג "collision-chaining". בספר הקורס, הפרק "Hash-Tables" דן בנושא זה.

מימוש C++ std::tr1::unordered_set, std::tr1::unordered_map

הבעיה

נניח שאנו רוצים למפות 100 מספרים, כ"א לערך שרירותי, ולרשותינו כמות בלתי מוגבלת של זיכרון. האם נוכל למצוא מבנה נתונים מהיר יותר מעץ אדום-שחור, לדוגמה? בוודאי, נשתמש במערך אינסופי (דמיוני, כמובן) שכ"א מאיבריו מאותחל בראשית לNil.

1	Values = Make-Array(∞)

2	Values[13] = 3

3	...

	# Prints 3.
4	Print( Values[13] )

	# Prints Nil.
5	Print( Values[14] )

פתרון זה הוא מהיר מאד (למעט האתחול, כמובן), כי כל גישה למערך היא $\displaystyle O(1)$. מה הבעיות, אם כן?

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

מפתחות שלמים אקראיים

הרעיון הכללי

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

בתרשים הבא, לדוגמה, המפתח 13 ממופה לערך 3 (יש עוד מספר איברים שאינם מצוינים במפורש).

טבלת ערבול.

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

1. בשלב הראשון נמצא לאיזו רשימה מקושרת מתאים המפתח. נניח שיש ברשותנו פונקציה אשר בהינתן מפתח מספרי, נותנת מספר רשימה מקושרת. נוכל להשתמש, לדוגמה, בפונקציה % (שארית): אם יש $\displaystyle 100$ רשימות מקושרות, אז $\displaystyle 13\%100=13$. ישנן פונקציות אחרות מתאימות.
2. בשלב השני נבצע את הפעולה המתאימה על הרשימה המקושרת. לדוגמה, כדי לחפש אם מפתח קיים, נחפש אותו בלולאה בכל אחת מחוליות הרשימה המקושרת המתאימה.

כדאי לדעת: מדוע יש צורך בכלל ברשימות המקושרות? אם המבנה מכיל גם את המפתח 113, אז $\displaystyle 113\%100=13\%100=13$, ולכן צריך מבנה נתונים משני שירכז את כל המפתחות שמופו לאותו מקום במערך הראשי. רשימה מקושרת הנה מבנה נתונים פשוט ומתאים לצורך זה.

ניתוח סיבוכיות

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

נניח את ההנחות הבאות:

1. המפתחות הנם מספרים שלמים אקראיים (במקרה זה נשתמש במושג כדי לציין שכל קבוצת מפתחות הנה סבירה ככל קבוצת מפתחות אחרת).
2. מספר המפתחות שווה לגודל המערך.
3. הפונקציה שאנו משתמשים בה כדי למפות מפתחות למקומות במערך היא פונקציה "טובה". זה אומר שהסיכוי של כל מפתח להיות ממופה

למקום כלשהו במערך שווה פחות או יותר לסיכוייו להיות ממופה לכל מקום אחר במערך.

כדאי לדעת: #בתורת ההסתברות, המינוח המתאים שהיינו משתמשים בו הוא שהמפתחות מתפלגים uniform i.i.d. מתורת המספרים ידוע שאם גודל המערך הוא מספר ראשוני (שלא כבדוגמה שלנו, לדוגמה, בה גודל המערך הוא 100), אז הפונקציה  % אכן "טובה".

משפט: אם ההנחות הללו מתקיימות, אז האורך הממוצע של רשימה מקושרת הוא $\displaystyle O(1)$.

משפט: אם ההנחות הללו מתקיימות, אז המחיר הממוצע של כל פעולה הוא $\displaystyle O(1)$.

מפתחות אחרים

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

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

דוגמה: אם המפתחות הנם כ"א מחרוזת בינרית באורך $\displaystyle k$,‏ $\displaystyle b_{1},...,b_{k}$,‏ אז נתן להשתמש בפונקציית הערבול הבאה. נגריל $\displaystyle k$ סיביות בינריות, $\displaystyle r_{1},...,r_{k}$, ונמפה כל מחרוזת למספר $\displaystyle \sum _{i=1}^{k}2^{i}\cdot r_{i}\cdot b_{i}$. אפשר להראות שפונקציה זו הנה פונקציית ערבול "טובה". בנוסף, אם $\displaystyle k$ קבוע, אז זמן החישוב הוא $\displaystyle O(1)$.

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

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

1. מפעילים את פונקציית הערבול על המפתח, ומקבלים מספר שלם.
2. לוקחים את התוצאה, וממפים אותה לרשימה מקשורת במקום המתאים במערך הראשי (לדוגמה ע"י הפונקציה % שראינו כבר).
3. מבצעים את הפעולה המתאימה על הרשימה המקושרת המשנית.

השוואה עם מבני נתונים אחרים

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

לדוגמה, הנה טבלת ערבול של מחרוזות:

1	H = Make-Hash()

2	H["Hello"] = 1
3 	H["World"] = 22

והנה משהו שנשתמש בו רבות בגרפים - טבלת ערבול של זוגות מספרים שלמים:

1	H = Make-Hash()

2	H[(2, 3)] = 1
3	H[(4, 5)] = 22

4	Print( H[(42, 5)] )

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

1. לרוב אכן אין סיבה להעדיף עצי חיפוש בינריים (אפילו עצים אדומים-שחורים) על פני טבלאות ערבול.
2. אם בוחרים פונקציית ערבול "רעה", סיבוכיות טבלאות ערבול עלולה להיות לינארית.
3. עצי חיפוש בינריים שומרים מפתחות על פי הסדר, מה שמאפשר לבצע עליהם פעולות מעניינות במקרים מסויימים (בספר הקורס, תוכל לקרוא על כך בפרק "Augmenting Data Structures").

הפרק הקודם: עצים אדומים-שחורים

טבלאות ערבול

הפרק הבא: תורי קדימויות