Description

יש לקרוא היטב לפני תחילת העבודה!
מבוא:
במעבדה הנוכחית נממש טבלת גיבוב.
תיאור:
טבלת גיבוב היא מבנה נתונים שנותן גישה לרשומה באמצעות המפתח המתאים לה. המבנה עובדבאמצעות הפיכת המפתח על ידי פונקציית גיבוב, למספר המייצג אינדקס במערך שמפנה אל הרשומההמבוקשת.
למשל: במפעל של 100 איש הוחלט לתת לכל עובד מספר ייחודי בן 3 ספרות. באופן כזה ניתן לשמור אתכל העובדים במערך של 1000 איברים.
אולם, אם משתמשים בת.ז. של העובדים בני 9 ספרות, נצטרך מערך בגודל מיליארד (109)כדי להחזיק 100 עובדים בסה”כ.
ולכן רצוי להשתמש במבנה נתונים שונה ממערך בו עדיין אפשר לבצע חיפוש מהיר.
יתרונות:
חיפוש מהיר: בהינתן מפתח נתון (למשל שם של אדם), מצא את הרשומה המתאימה (למשל מספר הטלפוןשל אותו אדם).
פונקצית גיבוב:
F(key) = key%N
123456%10=6
123467%10=7
123450%10=0
דוגמא 2 לפונקציית גיבוב כאשר המפתח הוא אינו מספר שלם:

למשל, אם נתונים השמות:
Sarah Jones
Tony Balognie
Tom Katz
בשלב ראשון, נעביר את השמות למספרים שלמים ע”י פונקציית מעבר ממחרוזת למספר שלם. דוגמא לפונקציה כזאתיכולה להיות, אם נצמיד לכל תו את קוד הASCII שלו ונחבר את כל הערכים יחד. התוצאה תהיה:
Sarah Jones –> 1038
Tony Balognie –> 1259
Tom Katz –> 746
בשלב שני, נשתמש בפונקציית הגיבוב מהדוגמא הקודמת:
Sarah Jones –> 1038 % 10 –> 8
Tony Balognie –> 1259 % 10 –> 9
Tom Katz –> 746 % 10 –> 6 :התוצאה תהיה

טיפול בהתנגשויות:
לעתים, יתכן כי שני מפתחות שונים יופנו לאותו התא במערך.
למשל, אם נוסיף לדוגמא 2 : 8 >– 10 % 948 >–John Smith . נקבל כי תא מספר 8 כבר תפוס.
במעבדה הנוכחית, נטפל בגישת השרשור(Chaining) לטיפול בהתנגשות לפיה, במקרה של התנגשות, המפתחות ישורשרו ברשימהמקושרת. למשל, עבור דוגמא 2 שלעיל,

משימה:
צרו מחלקה המגדירה טבלת גיבוב (HashTable) המכילה את השיטותcontains, add, remove, clear, isEmpty .תיעוד המחלקה נתון לכם.
מחלקה זו דומה במעט למחלקהHashSet המממשת אתSet :
https://docs.oracle.com/javase/8/docs/api/java/util/Set.html
הדרך התקנית להפוך מפתח כלשהו למספר שלם הוא להשתמש בשיטהhashCode . ניתן ליצור פונקציה כזאות באופןאוטומטי בECLIPSE .
הדרך התקנית לבדוק שוויון של עצמים היא להשתמש בשיטהequals . ניתן ליצור פונקציה כזאות באופן אוטומטי בECLIPSE.
ניתן להשתמש בפתרון של מעבדות קודמות, אבל לא בספריהjava.util .
המשימה (איך לא?) היא לגרום למחלקת הבדיקהHashTableTest לעבוד בצורה תקינה.
1. הוסיפו למחלקהPerson מתודהequals המשווה בין שלושת השדות שלPerson .
הוסיפו מתודתhashCode מתאימה. שימו לב שהשוואה זו שונה ממה שהיה במעבדה של עצי חיפוש.
;package il.ac.telhai.ds.misc : נמצאת בחבילהPerson המחלקה
2. ממשו אתHashTable הנתונה, תוך שימוש במחלקהDLinkedList שמימשנו במעבדות קודמות (היא נתונהלכם עם מימוש המתודות הנדרשות).המחלקהDLinkedList והממשקList נתונים בחבילהil.ac.telhai.ds.linkedlist המחלקהHashTable בחבילהil.ac.telhai.ds.hash .יתכן שבבנאי תקבלו ״הערת אזהרה״. כדי שהקומפיילר לא יתייחס לאזהרה זו, ניתן לכתוב מעליה:
@SuppressWarnings(“unchecked”)
אם עדיין יש אזהרה בבודק האוטומטי – ניתן להחליף שורה זו בשורה הבאה:
@SuppressWarnings({“unchecked”,”rawtypes”})
סדר העבודה ופרטים טכניים
: בקישורGITHUB מתוךDS-Lab09-HashTable שליפת הפרויקט●
https://github.com/ykanizo/DSLab2022-2023Public
○ אם אין לכם גישה לפרויקט שהורדתם מGITHUB במעבדות הקודמות יש לבצע שליפהמחדש.
○ אם יש לכם גישה לפרויקט שהורדתם מGITHUB במעבדה הראשונה אז בצעו:
■ קליק על שם הפרויקט.
עכבר ימני■ Team–>Pull ■ File–>Import->Git->Projects From Git->Existing Local Repository ■
פורמט קובץ ההגשה ובדיקתו:
בשםZIP פורמט : יש להגיש קובץ43_lab09_123456789_987654321.zip
(כמובן, יש להחליף את המספרים עם מספרי ת.ז. של המגישים).
על הקובץ להכיל את כל קבצי הJAVA שכתבתם כאשר הם נמצאים בתתי תיקיות בתוך התיקייה
il/ac/telhai/ds/על פי המבנה של הפרוייקט הנתון.
כלומר, השורש של קובץ ההגשה יכיל רק תיקייה בשםil , והוא יכיל את כל קבצי -java על פיהתבנית הנתונה בפרוייקט.
להמחשה תמונה של קובץ כזה שנפתח ב -WindowsExplorer

בדיקת קובץ ההגשה: בדקו את הקובץ שיצרתם בתוכנת הבדיקה בקישור:
https://csweb.telhai.ac.il/ראו סרטון הדגמה של השימוש בתוכנת הבדיקה.
חשוב!!!
בדיקת ההגשות תבוצע ברובה ע”י תוכנית הבדיקה האוטומטית הנ”ל. תוצאת הבדיקה תהייהבעיקרון זהה לתוצאת הבדיקה הנ”ל שאתם אמורים לערוך בעצמכם . כלומר, אם ביצעתם אתהבדיקה באתר החוג, לא תקבלו הפתעות בדיעבד. אחרת, ייתכן שתרגיל שעבדתם עליו קשהייפסל בגלל פורמט הגשה שגוי וכו.’ דבר שהיה ניתן לתקנו בקלות אם הייתם מבצעים את הבדיקה.
היות ואין הפתעות בדיעבד, לא תינתן אפשרות של תיקונים, הגשות חוזרות וכד.’הגשה שלא מגיעה לשלב הקומפילציה תקבל ציון 0.
הגשה שלא מתקמפלת תקבל ציון נמוך מ- 40 לפי סוג הבעיה.
הגשה שמתקמפלת תקבל ציון 40 ומעלה בהתאם לתוצאות הריצה, ותוצאת הבדיקה הידנית שלהקוד (חוץ ממקרה של העתקה).
תכנית הבדיקה האוטומטית מכילה תוכנה חכמה המגלה העתקות. מקרים של העתקות יטופלובחומרה