טבלת גיבוב מוסברת בפשטות - Hash Table¶
אם יש מבנה נתונים אחד שאתם משתמשים בו כל יום בלי לדעת את זה, זו טבלת גיבוב. כל פעם שכתבתם dictionary["key"] בפייתון, השתמשתם בה. אז בואו נבין סוף סוף מה קורה שם מתחת למכסה המנוע, כי זה אחד הרעיונות היפים באמת בתכנות.
הבעיה שטבלת גיבוב פותרת¶
תדמיינו שיש לכם מיליון מוצרים בחנות, וכל פעם שלקוח מחפש מוצר לפי שם, אתם עוברים אחד-אחד על כל המוצרים ובודקים אם השם תואם. זה עובד, אבל זה איטי בצורה מטורפת. עכשיו תדמיינו שבמקום זה, יש לכם דרך לחשב בדיוק באיזו "מדף" נמצא כל מוצר, בלי לחפש בכלל. זה בדיוק מה שטבלת גיבוב עושה.
איך זה עובד בפועל¶
הרעיון מתחיל בפונקציה שנקראת פונקציית גיבוב - hash function. תפקידה לקחת כל ערך, נגיד את המחרוזת "מקלדת", ולהמיר אותה למספר. אותה מחרוזת תמיד תניב אותו מספר. את המספר הזה משתמשים כדי לקבוע ישר לאיזה "תא" בזיכרון לשים את הערך.
עכשיו כשאתם מחפשים "מקלדת", המחשב לא צריך לחפש בכלל. הוא פשוט מריץ את אותה פונקציית גיבוב על "מקלדת", מקבל את אותו מספר בדיוק, וקופץ ישר לתא הנכון. אין חיפוש, יש קפיצה ישירה. זו הסיבה שפעולות על טבלת גיבוב מהירות כל כך - בממוצע, הזמן שלוקח לחפש ערך לא תלוי כמעט בכלל בכמות הפריטים שיש בטבלה, בין אם יש בה עשרה פריטים או עשרה מיליון.
מה קורה כששני ערכים "נופלים" לאותו תא¶
זו נקודה שכדאי להכיר כי היא מגיעה בכל ראיון עבודה. לפעמים שתי מחרוזות שונות ייתנו את אותו מספר מהפונקציית גיבוב - זה נקרא התנגשות, collision. טבלאות גיבוב טובות יודעות להתמודד עם זה, בדרך כלל על ידי שמירת רשימה קטנה של ערכים בכל תא במקום ערך בודד. אם התנגשויות קורות לעיתים רחוקות, זה כמעט לא פוגע בביצועים. אם פונקציית הגיבוב גרועה וכולם נופלים לאותו תא, טבלת הגיבוב הופכת בפועל לרשימה איטית - בדיוק מה שרצינו להימנע ממנו.
איפה זה משמש חוץ ממילונים¶
ברגע שמבינים את הרעיון, מגלים שהוא בכל מקום:
- מילון בפייתון, אובייקט בג'אווהסקריפט, HashMap בג'אווה - כולם בעצם טבלאות גיבוב.
- שמירת סיסמאות במסד נתונים לא שומרת את הסיסמה עצמה, אלא תוצאה של פונקציית גיבוב עליה - וזה עולם שלם בפני עצמו באבטחת מידע.
- קאש - cache - שמאחסן תוצאות של פעולות יקרות כדי לא לחשב אותן שוב, בנוי כמעט תמיד על טבלת גיבוב.
- מסדי נתונים משתמשים בגיבוב כדי לבדוק במהירות אם ערך כבר קיים, למשל לוודא ששם משתמש לא כפול.
למה כדאי להבין את זה ולא רק להשתמש בזה¶
אתם יכולים לכתוב שנים של קוד בפייתון בלי לדעת מה קורה בתוך מילון, ולהסתדר מצוין. אבל ברגע שתבינו את הרעיון, תתחילו לזהות הזדמנויות בעצמכם - "רגע, אני עובר על רשימה כדי לבדוק אם ערך קיים בה, אני יכול פשוט להפוך את זה לסט (set) ולקבל בדיקה מיידית". זו בדיוק סוג ההברקה הקטנה שמבדילה קוד סביר מקוד טוב.
הדרך הכי טובה להפנים את זה היא לפתור תרגיל קלאסי כמו למצוא את הפריט הראשון שחוזר על עצמו ברשימה, פעם אחת בשיטה האיטית עם לולאות מקוננות, ופעם שנייה עם מילון או סט. ההבדל בזמן הריצה יפתיע אתכם.
בקורס התכנות הבסיסי שלנו עוברים בדיוק על התרגילים האלה, כדי שתבינו לא רק איך משתמשים במילון אלא למה הוא כל כך חזק.
תתחילו את קורס התכנות הבסיסי כאן
לסיכום¶
טבלת גיבוב היא רעיון פשוט להפליא - לחשב בדיוק איפה למצוא כל ערך, במקום לחפש אותו. זה מה שהופך מילונים וסטים לכלים כל כך מהירים, וזה בדיוק הסיבה שהם נמצאים כמעט בכל תוכנה שתכתבו.
יש לכם שאלה בדרך? זה בדיוק מה שהקהילה שלנו בדיסקורד נועדה בשבילו.