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

February 8, 2019

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). בקיצור, לא ! גם אובייקט שהוא אימוטבלי, כמו טופל, אם הוא מכיל אלמנט שניתן לשנות, אינו ניתן לגיבוב.

Please reload

Please reload

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