א.17 — טבלאות גיבוב

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

בפרק הקודם ראינו שחיפוש ערך ברשימה דורש מעבר על האיברים, O(n), ושחיפוש בינארי מקצר את העבודה ל־O(log n) אבל דורש רשימה ממוינת. בפרקים א.11 ו־א.12 השתמשנו במילון ובקבוצה, וגילינו שגישה לפי מפתח ובדיקת in מהירות מאוד גם כשהאוסף גדול. בפרק זה נבין מדוע: המילון והקבוצה בנויים על טבלת גיבוב, שבה הוספה, שליפה ועדכון לפי מפתח אורכות בממוצע זמן קבוע, O(1), בלי תלות במספר האיברים. נכיר את פונקציית הגיבוב, נבנה טבלה קטנה בעצמנו, נראה מה קורה כששני מפתחות מגיעים לאותו מקום, ונחזור למילון ולקבוצה של פייתון עם הבנה של המנגנון שמאחוריהם.

מחברות האוניברסיטה הפתוחה — 11-מבני נתונים מתקדמים

הרעיון: לחשב את המיקום במקום לחפש אותו

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

הפונקציה הפשוטה ביותר למפתחות שהם מספרים שלמים היא שארית החלוקה בגודל המערך, הפעולה % שלמדנו בפרק א.3. במערך של 10 תאים, key % 10 מחזירה תמיד מספר בין 0 ל־9: זו בדיוק ספרת האחדות של המפתח. נשמור בטבלה מספרי חברים במועדון ואת שמותיהם:

SIZE = 10

def hash_index(key):
    return key % SIZE

members = [(51, "Dana"), (92, "Yoav"), (15, "Noa"),
           (17, "Omer"), (88, "Tal"), (29, "Maya")]

table = [None] * SIZE
for key, value in members:
    table[hash_index(key)] = (key, value)
print(table)

פלט

[None, (51, 'Dana'), (92, 'Yoav'), None, None, (15, 'Noa'), None, (17, 'Omer'), (88, 'Tal'), (29, 'Maya')]

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

print(table[hash_index(88)])

פלט

(88, 'Tal')

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

מדוע הגישה היא O(1)?

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

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

import time

numbers_list = list(range(1_000_000))
numbers_set = set(numbers_list)

start = time.time()
for i in range(1000):
    999_999 in numbers_list
print(f"list: {time.time() - start:.2f} seconds")

start = time.time()
for i in range(1000):
    999_999 in numbers_set
print(f"set: {time.time() - start:.2f} seconds")

פלט

list: 3.34 seconds
set: 0.00 seconds

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

התנגשויות

מה קורה כשמצטרף למועדון חבר מספר 71? 71 % 10 הוא 1, אבל בתא 1 כבר נמצא הזוג של 51. מצב שבו שני מפתחות שונים מקבלים אותו אינדקס נקרא התנגשות — Collision. התנגשויות הן בלתי נמנעות: לטבלה יש מספר קבוע של תאים, ומספר המפתחות האפשריים גדול ממנו בהרבה. לכן טבלת גיבוב אמיתית חייבת לדעת לטפל בהן. יש שתי גישות עיקריות.

שרשור: כל תא מחזיק רשימה

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

def insert(table, key, value):
    bucket = table[hash_index(key)]
    for i in range(len(bucket)):
        if bucket[i][0] == key:
            bucket[i] = (key, value)
            return
    bucket.append((key, value))

def get(table, key):
    bucket = table[hash_index(key)]
    for stored_key, value in bucket:
        if stored_key == key:
            return value
    return None

table = [[] for _ in range(SIZE)]
for key, value in members:
    insert(table, key, value)
insert(table, 71, "Ron")
print(table)

פלט

[[], [(51, 'Dana'), (71, 'Ron')], [(92, 'Yoav')], [], [], [(15, 'Noa')], [], [(17, 'Omer')], [(88, 'Tal')], [(29, 'Maya')]]

ב־insert, הלולאה בודקת תחילה אם המפתח כבר קיים בתא, ואם כן מעדכנת את הערך במקום להוסיף זוג כפול; כך מתנהג גם מילון כשמציבים ערך למפתח קיים. הביטוי [[] for _ in range(SIZE)] יוצר עשר רשימות ריקות נפרדות; הכתיב [[]] * SIZE היה יוצר עשר הפניות לאותה רשימה אחת, בדומה לשני השמות לאותה רשימה שראינו בפרק א.10. נבדוק את השליפה:

print(get(table, 71))
print(get(table, 51))
print(get(table, 33))

פלט

Ron
Dana
None

המפתח 33 מוביל לתא 3, שרשימתו ריקה, ולכן מוחזר None: המפתח אינו בטבלה.

טבלה פתוחה: מחפשים את התא הפנוי הבא

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

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

מה קובע כמה התנגשויות יהיו?

ככל שיש פחות התנגשויות, הרשימות בתאים קצרות יותר והגישה קרובה יותר ל־O(1). שני גורמים קובעים זאת.

• גודל הטבלה ביחס למספר האיברים. בטבלה של עשרה תאים עם מאה זוגות, לכל תא יגיעו בממוצע עשרה זוגות, וכל שליפה תצטרך לעבור עליהם. לכן שומרים על טבלה גדולה מספיק, ומגדילים אותה כשהיא מתמלאת.
• איכות פונקציית הגיבוב. פונקציה טובה מפזרת את המפתחות באופן אחיד על פני התאים. key % 10 מתאימה למפתחות שספרת האחדות שלהם מגוונת, אבל אם כל מספרי החברים מסתיימים באפס, כולם יתנגשו בתא 0, והטבלה תתנוון לרשימה אחת ארוכה שבה החיפוש הוא O(n).

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

גיבוב של מחרוזות ושל ערכים אחרים

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

def string_hash(text):
    total = 0
    for char in text:
        total += ord(char)
    return total % SIZE

for name in ["Dana", "Yoav", "Noa", "Maya"]:
    print(name, string_hash(name))

פלט

Dana 2
Yoav 5
Noa 6
Maya 2

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

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

print(hash(42))
try:
    hash([1, 2, 3])
except TypeError as error:
    print(error)

פלט

42
unhashable type: 'list'

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

מילון וקבוצה הם טבלאות גיבוב

עכשיו אפשר לסגור את המעגל. מילון בפייתון הוא טבלת גיבוב שבה כל מפתח עובר דרך hash, והזוג של המפתח והערך נשמר בתא המתאים; זו הסיבה שהגישה phones["Dana"] מהירה גם במילון ענק, ושמפתח חייב להיות ערך שאינו משתנה. קבוצה היא טבלת גיבוב שבה שומרים מפתחות בלבד, בלי ערכים, ולכן בדיקת in בקבוצה היא O(1), בעוד שאותה בדיקה ברשימה היא O(n).

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