היי
בשאלה המדוברת התבקשנו להציע דרך למימוש פונקציית (k)Delete) לטבלת האשינג המשתמשת בopen addressing.
בפתרון השאלה היה כתוב להוסיף ערך Deleted לכל תא שאותו מוחקים, ואז בפעולות חיפוש בטבלה נתעלם מתאים בהם כתוב Deleted.
השאלה שלי היא למה לעשות את זה? מה ההגיון בפתרון?
שלומי
תרגול 5 שאלה 5 - hash tables
מנהל: TA_Isana
Re: תרגול 5 שאלה 5 - hash tables
נניח שרצית להכניס לטבלה את המפתח 17 אבל התא הראשון שפונקצית הגיבוב נתנה לך היה תפוס ע"י המספר 8.
אז אתה מגדיל את I ומחשב מקום חדש בטבלה ונניח שהוא כבר פנוי ואתה מכניס לשם את 17.
אח"כ נניח שאתה אתה מוחק מהטבלה את 8 ואז אתה מחפש את 17.
כמובן שהתא הראשון שפונקצית הגיבוב תחזיר יהיה אותו תא שהיא חישבה בפעם הקודמת, זה ש-8 היה בו. אבל עכשיו התא הזה פנוי ולכן אתה תחשוב ש-17 לא קיים בכלל בטבלה!
אם היה בתא הזה סימון מיוחד שאומר לך שפעם הוא היה תפוס, אז אתה תדע שאתה צריך להמשיך לחפש את 17 כי אולי הוא נמצא בתא אחר.
אז אתה מגדיל את I ומחשב מקום חדש בטבלה ונניח שהוא כבר פנוי ואתה מכניס לשם את 17.
אח"כ נניח שאתה אתה מוחק מהטבלה את 8 ואז אתה מחפש את 17.
כמובן שהתא הראשון שפונקצית הגיבוב תחזיר יהיה אותו תא שהיא חישבה בפעם הקודמת, זה ש-8 היה בו. אבל עכשיו התא הזה פנוי ולכן אתה תחשוב ש-17 לא קיים בכלל בטבלה!
אם היה בתא הזה סימון מיוחד שאומר לך שפעם הוא היה תפוס, אז אתה תדע שאתה צריך להמשיך לחפש את 17 כי אולי הוא נמצא בתא אחר.
Re: תרגול 5 שאלה 5 - hash tables
תודה רבה.