תכנות
—
שיעור 140
28/February/2011
Hash Tables
תיארנו "מדיניות" כיצד להגדיל טבלת hash.
הצצנו בקבץ
hashtable.h
שנמצא בגרסאות עכשויות ב
/usr/include/c++/4.4/backward/hashtable.h
בפרט התמקדנו ברשימת הראשוניים:
__stl_prime_list
ששם. הם "רחוקים" מחזקות של שתיים.
תרגילים
-
שפר את התכנית
hash-pdb-v1
משעור קודם
לגירסא
hash-pdb-v2
שמקימת את הדרישות
השונות או הנוספות
הבאות:
-
הפרמטרים של גודל הטבלה, ומספר מירבי לקריאה מבוטלים.
-
גודל הטבלה רק יגדל לפי רשימת הראשוניים, כפי שמופיעה בקובץ המוזכר למעלה
או בימים אלה ברשת
.
כאשר מספר האברים בטבלה (כולל התנגשויות), גדול מגודל הטבלה,
תִוַצר טבלה חדשה בגודל של המספר הראשוני הבא ברשימה.
יש להעביר את המצביעים של האברים מהרשימות של הטבלה הישנה, לטבלה החדשה.
ההעברה הזו "יקרה" בזמן, אבל פרט להקצאת זכרון לטבלה החדשה (ושחרור הישנה לבסוף)
כל המצביעים עוברים, ואין צורך להעתיק את התוכן האמיתי של האברים (במקרה שלנו: שם, מזהה, משקל).
פונקצית ההכנסה של אֵבר לטבלה, תחליט באופן פנימי אם יש להגדיל את הטבלה ולבצע זאת.
התכנית הראשית אמורה לא לדאוג ולא להיות מודעת להגדלה.
-
יהיה פרמטר אפשרי לקובץ שמות למחיקה. במקרה שהוא ניתן,
לאחר אכלוס הטבלה, יש למחוק מהטבלה את האברים עם השמות האלה.
-
להדפסת הטבלה, ינתנו פרמטרים אפשריים נוספים: התחלה ואורך. כך שאפשר יהיה להדפיס רק קטע מהטבלה.
בדוגמת ההרצה שתשלח, יהיו שורת הפקודה במדויק, עם הדפסה של עד 20 כניסות בטבלה.
חזרה לעמוד האם