hashtable - מימוש של java

[userit8]

hashtable - מימוש של java

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

http://docs.oracle.com/javase/6/docs/api/java/util/Hashtable.html

ולא מבינה משהו - איפה נכנסת פה הפונקציית hash?

מה הרעיון אם ב put אנחנו קובעים לכל ערך לאיזה תא להיכנס? זה נהיה כמו מערך
תודה

 

[BravoMan]

מאחורי הקלעים:

ה-hash הוא לא על הערך שמאחסנים, אלא על המפתח שמשתמשים בו.

הוא מאפשר השוואה קלה ומהירה של כל סוג של אובייקט שניתן לעשות לו hash, ובצורה כזו ניתן להשתמש ב-hashtable עם הרבה סוגים שונים של אובייקטים בתור מפתחות בצורה יעילה.

למשל, במקרה של מפתח שהוא מחרוזת, במקום לבצע הרבה השוואות של מחרוזות בכל פעולת גישה פשוט מחשבים hash וניגשים לפיו.

 

[nocgod]

אגב אחת המתודות שאת יורשת ממחלקת Object

היא מתודה שנקראת hashCode().
אם את לא נותנת מימוש משלך למתודה, יש מימוש במחלקת הבסיס
אבל זה המתודה שמשתמשים בה כל הMaps למיניהם כדי לקבל מאובייקט (מפתח) איזשהו hash...

"Always override hashCode when you override equals" in Bloch, Joshua (2008), Effective Java (2 ed.)

 

[selalerer]

ב-Java ה-containerים שמשתמשים ב-hash הם...

...בעלי זוגות ערכים, מפתח וערך (key ו-value).

ה-value אינו ממלא שום תפקיד שקשור ב-hash, הוא פשוט מאוחסן שם ליד ה-key.

ה-key הוא למעשה האובייקט שעליו נעשה ה-hash (הפונקציה hashCode שלו נקראת) והוא קובע היכן מאוחסן הזוג הזה במבנה הנתונים.

מערך הוא פשוט בלוק זיכרון רציף שב-Java מכיל referenceים לאובייקטים וניתן לפנות לפי אינדקס, מספר שמציין את המיקום של ה-reference במערך (אבל מתחילים מאפס ולא מאחד).

Associative Container הוא מבנה נתונים שמקשר בין מפתח לערך. Hashtable הוא אחד ממבני הנתונים האלו ב-Java ולכן ה-put מקבל key ו-value. זה לא הופך אותו למערך.

 

[userit8]

אני כנראה עוד לא כל כך מבינה

כתבתם שמשתמשים בפונקציית hashCode , אבל בעצם הפונקציה צריכה להחזיר אינדקס למערך , שתלוי בגודל המערך -> אז איך זה יכול להיות משהו כללי?

איך java מממשת את זה (בקישור שהבאתי) ואיך למשל אני אוכל לממש את זה לבד?

 

[selalerer]

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

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

ה-hashCode מחזירה int. כלומר כל מספר בטווח (הענק) של int.

ה-Hashtable לא משתמש בכל המספר הענק הזה. אם למשל ה-Hashtable הוא בגודל 10 אז הוא לוקח את המספר שמחזירה hashCode ועושה לו מודולו 10 (כלומר מוציא את השארית מחילוק ב-10) וכך מחליט לאיזה תא להכניס את האובייקט.

 

[nocgod]

אם את עדיין באקדמיה

אולי כדאי לך לקפוץ לספריה לקחת את הספר של G.Brassard או אולי Corman (או cormen מי זוכר)
ולחזור על מה זה Hash table/map איך זה עובד, איזה שיטות יש (לדוגמא לאחרונה אחרי דיון בפורום (לאחרונה יש הרבה דיונים מעניינים) גיליתי שjava ו JS משתמשים במימושים שונים לhash table)
מה זה hash function מה הרעיון, איך מגדילים את הטבלה וכו וכו וכו.

בכללי, ב java המבנה מנסה לשמור על רמת מילוי של 75%, וכל פעם שאת מכניסה ערך חדש לטבלה מה שקורה זה hashCode() של האובייקט מודולו הגודל המקסימלי של הטבלה נכון לעכשיו ואז מכניסים
את האובייקט לרשימה מקושרת ששיכת לתא במערך (שערכו חישבנו קודם)
לעומת JS שמשתמש בprobes לדוגמא כדי להכניס ערך למערך...
דווקא נושא מעניין מאוד, נותן פרספקטיבות ורעיונות למימוש מבנים משלך לעתיד...

 

[nocgod]

אחרי הדיון שלנו בעבר למדתי ש...

בjava משתמשים בשיטה של רשימות מקושרות בכל תא
לעומת השיטה של הprobes (לדוגמא בJS)

 

[userit8]

אוקי נראה לי הבנתי

יש לי שאלה אחרת - מדוע חשוב ה load factor? מה משנה לנו אם הטבלה תהיה מלאה?

 

[pattos]

זה כבר הופך להיות לא יעיל