במסגרת הקורס באוניברסיטה נתנו לנו את השאלה הזאת:

יש לשמור קבוצה דינמית של איברים, כאשר כל איבר מכיל :שם, מספר זהות ופרטים נוספים.

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

תאר מבנה נתונים יעיל למימוש הפעולות הללו.

חשבתי על שימוש ב-MAP, אבל MAP ממיין ומכניס איברים לפי מפתח אחד שבוצע עליו HASHCODE.

השאלה שלי היא האם יש מבנה דומה לMAP שיכול למיין לפי 2 מפתחות?

תודה מראש,

אביעד

יש לך טעות. Map, כ- ADT - לא ממיין. הוא רק מאפשר שליפות לפי מפתח.

אתה יכול להחזיק שני Maps. באחד ה- key זה השם, ובשני ה- key זה מספר ת"ז.

בהכנסה - אתה מכניס לשני ה- maps.

במחיקה - אתה מחפש ב- map השני, מוצא את השם, מחפש אותו ב- map הראשון, ומוחק את שניהם.

אתה יכול להשתמש בשני map-ים, אחד עם ת.ז כמפתחות ואחד עם השם כמפתח. כשאתה מבצע הכנסה אתה מכניס את האובייקט לשני ה הmap-ים.

עריכה: בדיוק כשהגבתי גם Boomerang הציע את אותו הפתרון.

נכון, התכוונתי מאפשר שליפות לפי מפתח ולא מיון. טעות שלי.

הבנתי את הרעיון שלכם, ואני אראה איך אני מממש אותו.

בכל מקרה, הסיבוכיות נשארת (O(1 נכון?

בכל מקרה, הסיבוכיות נשארת (O(1 נכון?

כן, בתנאי שחישוב ה- Hash הוא (O(1 ומספר ה- hash collisions שלך חסום ע"י קבוע.

חישוב ההאש יהיה ללא תלות במספר האיברים,

hash collisions - לא זוכר שנתקלתי במושג הזה, תוכל לפרט קצת?

מדובר באיברים שמתמפים לאותו מס' (תא) ע"י פונקצית ההאש.

התנגשויות נפתרות ע"י עץ אדום שחור בתאים שמחזיר ערך בזמן logN

תודה רבה לכם על העזרה,

אני יותר מאוחר אתחיל לממש את זה ואם יהיו לי בעיות אני אתיעץ איתכם.