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

מנהל: TA_Isana

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

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

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

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

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

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


שלומי

TA_Gila
הודעות: 66
הצטרף: 14:56 24/04/2009
יצירת קשר:

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

שליחה על ידי TA_Gila » 17:23 23/07/2009

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

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

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

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

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

תודה רבה.

שלח תגובה

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