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

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

תבנית:הארה

הבעיה

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

1	Values = Make-Array(∞)

2	Values[13] = 3

3	...

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

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

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

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

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

הרעיון הכללי

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

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

טבלת ערבול.

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

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

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

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

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

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

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

תבנית:הארה

מפתחות אחרים

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

תבנית:מבנה תבנית

תבנית:מבנה תבנית

תבנית:שימו לב

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

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").

תבנית:מבני נתונים ואלגוריתמים - מחברת קורס