דף 1 מתוך 1

תרגול 5 שאלה 5 - hash tables

נשלח: 13:04 23/07/2009
על ידי שלומי
היי
בשאלה המדוברת התבקשנו להציע דרך למימוש פונקציית (k)Delete) לטבלת האשינג המשתמשת בopen addressing.

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

השאלה שלי היא למה לעשות את זה? מה ההגיון בפתרון?


שלומי

Re: תרגול 5 שאלה 5 - hash tables

נשלח: 17:23 23/07/2009
על ידי TA_Gila
נניח שרצית להכניס לטבלה את המפתח 17 אבל התא הראשון שפונקצית הגיבוב נתנה לך היה תפוס ע"י המספר 8.
אז אתה מגדיל את I ומחשב מקום חדש בטבלה ונניח שהוא כבר פנוי ואתה מכניס לשם את 17.
אח"כ נניח שאתה אתה מוחק מהטבלה את 8 ואז אתה מחפש את 17.

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

Re: תרגול 5 שאלה 5 - hash tables

נשלח: 18:00 23/07/2009
על ידי שלומי
תודה רבה.