גישור (Hashing)
הוצג| English | משמעות |
|---|---|
| hash function/hæʃ ˈfʌŋkʃn/ | פונקציית גישור (Hash) |
| key/kiː/ | מפתח |
| address/əˈdres/ | כתובת |
| deterministic/dɪˌtɜːmɪˈnɪstɪk/ | דיטמיניסטיבי |
| collision/kəˈlɪʒn/ | תנגשות |
| linear probing/ˈlɪnɪə ˈprəʊbɪŋ/ | חיפוש ליניארי |
| chaining/ˈtʃeɪnɪŋ/ | קישוריות |
| load factor/ləʊd ˈfæktə/ | גורל עומס |
מציאת שורה אחת מתוך חמישים מיליון ללא בדיקה
- קופה במרכול זורק ברקוד ברקוד והמחיר מופיע לפני ידכם עוזבת את המוצר. תיק המוצרים מכיל חמישים מיליון שורות.
- אף אחד לא בדק אותם. מספר הרקוד עבר דרך חישוב קצר שייצר מיקום, והמחשב קרא את המיקום הזה: קריאה אחת, ללא השוואות, אותו זמן בין אם הקובץ מכיל חמישים שורות או חמישים מיליון.
- החישוב הוא פונקציית גיבוי, והרעיון כולו נשען עליו: אל תאגרו נתונים במקום שישתלבו, אלא במקום שמפתח עצמו אומר שהוא שייך לו.
- שיעור זה עוסק באלגוריתמי גיבוי, מה קורה כשני מפתחות רוצים את אותו מקום, וכיצד לבצע חיפוש והוספה.
פונקציית הגיבוי
- פונקציית גיבוי, או אלגוריתם גיבוי, לוקחת את המפתח של שטח ומייצרת את הכתובת בה השטח מאוחסן.
- פונקציה טובה היא מהירה, דיטרמיניסטית (אותו מפתח תמיד נותן אותו כתובת), ומפיצה מפתחות באופן שווה על פני המקומות הזמינים.
- עבור $N$ מקומות, שלושת האלו שתיבת הסילבוס מצפה להם: מודולו,
address ← key MOD N; קיפול, לחלק את המפתח לחלקים, לחבר אותם, ואז MOD $N$; גיבוי מחרוזת, לחבר קודי האותיות, ואז MOD $N$.
פונקציית גישור:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
פונקציית גיבול מתמפה מפתח לכתובת, מה שמאפשר חיפוש ישיר קרוב למיידי.
מה הופך פונקציית גיבול לתפקוד טוב? בחר את כולן שמתאימות.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
מהירה, דטרמיניסטית ומפוזרת באופן אחיד. אין פונקציית גיבול ריאלית שתמנע התנגשות לחלוטין, ולכן כל עיצוב כולל אסטרטגיית פתרון.
דוגמה פתורה: יישום כל אלגוריתם
- קובץ מכיל 10 מקומות, מסופקים 0 עד 9. לאן ילך המפתח 4517?
- מודולו: $4517 \bmod 10 = 7$, ולכן תא 7.
- קיפול בזוגות: $45 + 17 = 62$, ולאחר מכן $62 \bmod 10 = 2$, ולכן תא 2.
- ומה המפתח "CAB" באמצעות hash מחרוזת? $67 + 65 + 66 = 198$, ולאחר מכן $198 \bmod 10 = 8$, ולכן תא 8.
- הציג את החישוב. הנקודה היא עבור החישוב, לא רק מספר התא.
שימוש בפונקציית גיבול מודולו address ← key MOD N עם מפתח = 27 ו-N = 10, איזה כתובת תיוצר?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
27 MOD 10 = 7 (השארית כאשר 27 מחולק ב-10).
יש טבלה עם 10 סלונים. שימוש בשיטה של קיפול זוגות במפתח 4517 (חיבור 45 ו-17, ואז MOD 10), לאיזה סלון הוא ייכנס?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
45 + 17 = 62, ו-62 MOD 10 = 2. אותו מפתח תחת פונקציית גיבול מודולו היה ניכנס לסלון 7 במקום זאת.
התנגשויות
- התנגשות מתרחשת כאשר שני מפתחות שונים מתמזגים לאותו כתובת. עם כל פונקציית hash וכדי קובץ ריאליסטי, התנגשויות בלתי נמנעות, ולכן אסטרטגיה להתמודדות איתן הן חלק מהעיצוב, ולא תוספת מאוחרת.
- חיפוש ליניארי מכניס את הרקורד לתא הפנוי הבא, ומתחבר לחלק העליון של הטבלה בסוף הטבלה. פשוט, אך רקורדים צברים: מקטע מלא גדל וכל מפתח שנופל בו לוקח יותר זמן.
- שילוב (Chaining) הופך כל תא לראש של רשימה מקושרת של כל הרקורדים שהתמזגו שם. אין צבירה, אך יש צורך במרחב נוסף לשערי רמייה והליכה קצרה לאורך הרשימה.
- Rehashing מיישם פונקציית hash שנייה למציאת תא אחר, ומפיץ מפתחות טוב יותר על חשבון חישוב נוסף.
התנגשות מתרחשת כאשר:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
שני מפתחות הממופים לסלון זהה הם התנגשות; יש לפתור אותה באמצעות חיפוש, שרשרת או גיבול מחדש.
התאם את כל רעיונות הטיפול בהתנגשות למה שהן עושות.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
התנגשויות פותרות באמצעות קישור או בדיקה; שמירה על גורל עומס נמוך שומר על זמני חיפוש קרובים ל-O(1).
חיפוש והכנסה
- להכניס: המזג את המפתח. אם התא פנוי, כתוב את הרקורד שם. אם לא, עקוב אחר אסטרטגיה לפתרון ההתנגשות, התא הפנוי הבא עבור חיפוש ליניארי, או ראש רשימת התא עבור שילוב.
- לחפש: המזג את המפתח וקרא את התא. אם המפתח השמור תואם, הרקורד נמצא. אם לא, עקוב אחר אותה אסטרטגיה, עד שמצאים התאמה או שתא ריק מוכיח שהרקורד אינו בקובץ.
- שתי הפעולות משתמשות באותה אסטרטגיה. חיפוש שיעצור בהתנגדות הראשונה יפספס כל רקורד שהוזז לעולם על ידי התנגשות.
דוגמה פתורה: מעקב אחרי התנגשות
- טבלה בעלת 10 תאים משתמשת ב-
key MOD 10עם חיפוש ליניארי. הכנס 23, 33, 43 בסדר זה, ואז חפש את 43. - 23 מתמזג ל-3; תא 3 פנוי, ולכן הוא נכנס שם. 33 מתמזג ל-3; תא 3 תפוס על ידי 23, ולכן חיפוש ליניארי מכניס אותו לתא 4. 43 מתמזג ל-3; תאים 3 ו-4 תפוסים, ולכן הוא נכנס לתא 5.
- חיפוש אחר 43: המזג ל-3, קרא תא 3, המפתח הוא 23, אין התאמה, ולכן המשך בחיפוש; תא 4 מכיל 33, אין התאמה; תא 5 מכיל 43, נמצא, לאחר שלושה קריאות.
- רצף הגדל הזה של שלושה הוא הצבירה שחיפוש ליניארי גורם לה.
משוך כל מפתח ישר למיכל (bucket)
פונקציית גישור ממיר מפתח למספר מיכל, כך שאתה יכול לקפוץ ישר לרישום במקום לחפש. כאשר שני מפתחות נופלים באותו מיכל, זוהי התנגשות — הם מחוברים ביניהם באותו מיכל.
בעת חיפוש בטבלת גיבוי, אם הרשומה אינה קיימת בקובץ, המצד יגיע לקראת התא הראשון הקורא בעל מפתח שונה.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
יתכן שהרשומה הוחלפה בשל התנגשות. החיפוש ממשיך לפי אותה אסטרטגיית פתרון עד למציאת התאמה או תא ריק.
מקדם העומס
- מקדם העומס הוא מספר הרשומות חלקי מספר התאים. זהו המספר היחיד שחוזה את ביצועי הטבלה.
- מתחת ל-70% בערך, חיפוש ממוצע דורש קריאה אחת. מעל סף זה, אורך רצפי החיפוק מתאר בחוד וביצועים יורדים לעבר חיפוש ליניארי.
- הפתרון הוא להגדיל את הטבלה ולעשות TODO rehash לכל רשומה לתוכה; לכן טבלת TODO hash נבנית בהתאם למידע שתכיל, ולא למידע הקיים היום.
טבלה בעלת 10 תאים משתמשת במפתח MOD 10 עם בדיקה ליניארית. לאחר הכנסת 23, 33 ו-43 בסדר זו, איזה תא מכיל את 43?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
כל שלושתם מגיעים ל-3. 23 תופס את תא 3, 33 נבדק ל-4, ו-43 ל-5. שלושה מפתחות ברצף הם בדיוק הצביר הליניארי ש-bdiqa ליניארית גורמת לו.
סימונים נופלים מהיד
- התנגשות היא שתי מקדדים, כתובת אחת. זו אינה שגיאה ואין בה רשומה אבודה; זו תופעה נורמלית שאסטרטגיה מטפלת בה.
- חיפוש חייב לעקוב אחרי אותה אסטרטגיה כמו ההכנסה, ולהיעצר רק במצאת התאמה או ב-תא ריק.
- TODO linear probing יוצר צבירים; TODO chaining עולה ב-זיכרון. יש לתת משקל לאיזון בין האסטרטגיות, לא רק למנגנון עצמו.
- מקדם העומס הוא רשומות חלוקה ב תאים, והסף הוא כ-70%, לא 100%.
כדי לשמור על זמני חיפוש מהירים בטבלת גיבוי, יש לשמור על גורל העומס (רשומות ÷ תאים):
Difficulty 1/5 · 100 coins + a small bonus on first completion today
גורל עומס נמוך יותר משמעותו פחות התנגשויות, ולכן זמני החיפוש נשארים קרובים ל-O(1).
הבנתך מושלמת
- פונקציית TODO hash ממירה מקדם ל-כתובת: מהירה, דיטרמיניסטית, מפוזרת באופן שווה; מודולו, קיפול (folding) ו TODO hash של מחרוג הם השלושה שיש לדעת.
- TODO collision היא שני מקדדים TODO hash לכתובת אחת, שנפתרים על ידי todo linear probing (התא הפנוי הבא, צבירים), todo chaining (רשימה מקושרת לכל תא, יותר זיכרון) או rehashing.
- הכנסה וחיפוש עוקבים אחרי אותה אסטרטגיה; חיפוש נסתיים בהתאמה או בתא ריק.
- שמרו על מקדם העומס, רשומות חלוקה בתאים, מתחת לכ-70% כדי לקבל חיפושים בקריאה אחת.