טבלאות hash
טבלאות חשיפה: חיפוש מהיר
- טבלת חשיפה מאחסנת פריטים כך שתוכלו למצוא אותם מהר מאוד — בדרך כלל בשלב אחד.
- זוהי רשימה של תאים. פונקציית חשיפה ממירה מקור לתא מספר.
- במקום לחפש בכל פריט, קופצים ישר לתא בו המקור שייך.
פונקציית חשיפה
- פונקציית חשיפה לוקחת מקור ומחזירה אינדקס תא מ
0עדsize - 1. - אותו מקור תמיד נותן אותו תא, כך שתוכלו למצוא אותו שוב מאוחר יותר.
- פשוטה: סכמו קודי האותיות, ואז לקחו
% sizeכדי להישאר בטווח.
def hash_key(key, size):
total = 0
for ch in key:
total += ord(ch) # ord("A") is 65, ord("B") is 66, ...
return total % size
print(hash_key("cat", 10)) # a slot from 0 to 9
print(hash_key("cat", 10)) # same key -> same slot
print(hash_key("dog", 10))
התנגשויות
- שני מקורות שונים יכולים לחשוף לאותו תא. זהו התנגשות.
- לטבלה יש מספר מוגבל של תאים, ולכן התנגשויות בלתי נמנעות כשהיא מתמלאה.
- אנחנו זקוקים לכלל עבור מה לעשות כאשר התא הרצוי תפוס כבר.
סריקה ליניארית
- חיפוש ליניארי: אם תא מלא, נסו את התא הבא, ואז את הבא, עם חזרה למתחילת הטבלה.
- המשיכו לצעוד
(slot + 1) % sizeעד שתמצאו תא פנוי. - למטה,
Aו-Fשואפים לתא 0, לכןFדוחק לתא 1.
def hash_key(key, size):
total = 0
for ch in key:
total += ord(ch)
return total % size
def insert(table, key):
slot = hash_key(key, len(table))
while table[slot] is not None: # slot taken -> try the next one
slot = (slot + 1) % len(table)
table[slot] = key
return slot
table = [None] * 5
print(insert(table, "A")) # 0
print(insert(table, "F")) # 1 (A and F both hash to slot 0)
print(table) # ['A', 'F', None, None, None]
חיפוש מפתח
- כדי למצוא מפתח: חשבו אותו באמצעות פונקציית TODO, ולאחר מכן חפשו קדימה, בהשוואת כל תא למפתח.
- עצרו והחזירו את האינדקס כאשר תמצאו אותו.
- אם הגעתם לתא פנוי (או בדקתם כל תא), המפתח אינו קיים — החזירו
-1.
מדוע טבלאות TODO מהירות
- עם מעט התנגשויות, הוספה ומציאה לוקחות כ-שלב אחד — אנו מכנים זאת
O(1). - ככל שהטבלה מתמלאת, החיפוש נמשך זמן רב יותר, ולכן מומלץ לשמור על כמה תאים פנויים.
- במקרה הגרוע (הכל מתנגש) המהירות יורדת לסריקה ליניארית,
O(n).
טעויות נפוצות
- פונקציית TODO ממפה מפתח לאינדקס בטבלה.
- שני מקדשים יכולים להתנגש באותו אינדקס. יש לטפל בכך, כמו שעשה שיעור זה, באמצעות חיפוש ליניארי; שרשרת (chaining) היא שיטה נפוצה נוספת.
כעת תנסו בעצמכם
- בנה את שלושת החלקים: פונקציית TODO, הוספה עם חיפוש ליניארי, ומציאה.
- כל משימה בודקת את הפונקציה שלך במקרי התנגשות ומקרי חזרה למתחילת הטבלה.
- לחץ על בדיקת תשובה כדי לבדוק אותה.
השמשה למיכל
פונקציית גיבול שולחת כל מפתח למיכל; התנגשויות יוצרות שרשרת.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
כתוב hash_key(key, size). הוסף את קודי האותיות של key (השתמש בord(ch)) והחזר את הסכום % size, כך שהתוצאה תהיה מקום בטוח בין 0 ל-size - 1. דוגמה: hash_key("AB", 10) הוא (65 + 66) % 10 = 1. המחרוזת ריקה נותנת 0.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
hash_key מסופק. כתוב insert(table, key) באמצעות חיפוש ליניארי: עבר למקום הטאבל של הגיבול; בזמן שמקום זה תפוס (לא None), צעד ל(slot + 1) % len(table); השתם את המפתח במקום הפנוי הראשון וחזור על מדדיו.
לחץ על הרץ כדי לראות את התוצא כאן.
רמת קושי 4/5 · 280 מטבעות + בונוס קטן בהשלמה הראשונה היום
hash_key מסופק. כתוב find(table, key) שמחזיר את מדד ה-key, או -1 אם הוא חסר. התחל במיקום הגיבול וחקור קדימה, השווה כל מקום. עצור במקום פנוי (המפתח אינו שם). ודא שהפונקציה תסתיים גם אם הטאבל מומלא — לעולם לא להילך בחיסור אינסופי.
לחץ על הרץ כדי לראות את התוצא כאן.