רעננו את הדף והקליקו למעבר לנושא הבא:

Hashable objects -אובייקטים ניתנים לגיבוב

Hashable objects -אובייקטים ניתנים לגיבוב

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





משהוא כזה. פונקציית הגיבוב מתאימה את המספר 3 למפתח "a" אח"כ לפי האינדקס אנו יודעים ש- 3 מקבל את הערך "alfa" . כמובן שהיא צריכה להיות חד ערכית, כלומר שלכל מספר יהיה רק ערך אחד, אחרת מה עשינו.

פייתון משתמשת בגיבוב כברירת מחדל בכל ה- immutable objects – אובייקטים שלא ניתנים לשינוי מרגע יצירתם, כמו integer, bool True או False, tuple או string. כדי לדעת את המספר המתקבל מהגיבוב, נשתמש במתודה ()__hash__


stringa="abc" tuplea=(1,2) n=None t=True f=False print(stringa.__hash__()) >>> 9075183606561537427 print(tuplea.__hash__()) >>> 3713081631934410656 print(n.__hash__()) >>> 109031757 print(t.__hash__()) >>> 1 print(f.__hash__()) >>> 0

אנו רואים שכל אובייקט מקבל מספר hash גם אובייקט מסוג None ומה שמעניין לשים לב אליו הוא שהאובייקט True מקבל את המספר 1 והאובייקט False מקבל את המספר 0.

לרשימות, מילונים וסטים למשל לא יהיה hash משום שהם mutable ניתנים לשינוי (אפשר להוסיף ולגרוע איברים בלי לשנות את האובייקט לאחד חדש).

איך אנו יודעים שמדובר באותו אובייקט ? פשוט. בפייתון נתנו לו מספר זהות- ()id. שווה לראות דוגמא של העניין הזה –


lista=[1,2,3]

print(id(lista)) >>> 2120179395784

lista.remove(1)

print(lista) >>> [2, 3]

print(id(lista)) >>> 2120179395784

לאחר שיצרנו רשימה lista היא מקבלת מספר זהות שאינו משתנה גם לאחר שגרענו את המספר 1 מהרשימה. זה אובייקט שניתן לשינוי mutable.

היות שלמילון ולרשימה אין מספר גיבוב, לא ניתן להשתמש ברשימה כמפתח במילון של פייתון. מפתח יכול להיות רק אובייקט שיש לו מתודת hash.

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


class MyClass: def __init__(self, x): self.x = x def __hash__(self): return int(self.x) o1=MyClass(2) o2=MyClass(2) print(o1.__hash__()) >>> 2 print(o2.__hash__()) >>> 2 dicta={o1:"alfa",o2:"beta"} print(dicta)

>>>

{<__main__.MyClass object at 0x00000212963A43C8>: 'alfa', <__main__.MyClass object at 0x00000212963A45F8>: 'beta'}

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

אובייקט ניתן לגיבוב חייב להיות immutable - אבל זה לא מספיק, מה לגבי tuple שהוא אימוטבילי המכיל רשימה שהיא כן מוטבילית ? יש חיה כזאת בפייתון והיא יכולה להראות למשל כך: (1,2,3,[42]) . האם הדבר הזה יכול להיות מפתח במילון ? האם הוא ניתן לגיבוב (hashable). בקיצור, לא ! גם אובייקט שהוא אימוטבלי, כמו טופל, אם הוא מכיל אלמנט שניתן לשנות, אינו ניתן לגיבוב.

Related Posts

See All

בסיסי מספרים

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