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

מנהל: TA_Isana

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

הודעהעל ידי שלומי » 12:04 23/07/2009

היי
בשאלה המדוברת התבקשנו להציע דרך למימוש פונקציית (k)Delete) לטבלת האשינג המשתמשת בopen addressing.

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

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


שלומי
שלומי
 
הודעות: 19
הצטרף: 00:00 19/11/2008

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

הודעהעל ידי TA_Gila » 16:23 23/07/2009

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

כמובן שהתא הראשון שפונקצית הגיבוב תחזיר יהיה אותו תא שהיא חישבה בפעם הקודמת, זה ש-8 היה בו. אבל עכשיו התא הזה פנוי ולכן אתה תחשוב ש-17 לא קיים בכלל בטבלה!
אם היה בתא הזה סימון מיוחד שאומר לך שפעם הוא היה תפוס, אז אתה תדע שאתה צריך להמשיך לחפש את 17 כי אולי הוא נמצא בתא אחר.
TA_Gila
 
הודעות: 66
הצטרף: 13:56 24/04/2009

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

הודעהעל ידי שלומי » 17:00 23/07/2009

תודה רבה.
שלומי
 
הודעות: 19
הצטרף: 00:00 19/11/2008


חזור אל - מבני נתונים

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ואורח אחד