שאלה

[ronihp]

שאלה

אולי אתם יודעים היכן אפשר למצוא ברשת דוגמאות לפונקציות hash table? אני מחפש דוגמאות מוחשיות שאפשר ללמוד מהם את הנושא.

 

[הולך בין הטיפות]

במרבית האתרים הכוללים

את נושא JAVA ישנם דוגמאות. נסה בראש ובראשונה את SUN. www.sun.java.com

 

[ronihp]

כן. חפשתי שם

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

 

[yair24]

הנה הסבר:

אני אסביר לך מה זה HASH פתוח (לא סגור, אם אתה רוצה הסבר ממש טוב על HASH סגור, יש בספר של קורמן) HASH פתוח: תחשוב על מערך של פוינטרים לרשימה מקושרת של סטודנטים בגודל 100 אוקיי? (כל איבר במערך הוא בעצם "ראש" של רשימה מקושרת ריקה בינתיים) עכשיו תחשוב שיש לך רשימת סטודנטים ולכל סטודנט יש מספר תעודת זהות. (כל סטודנט הוא איבר של רשימה מקושרת) אתה רוצה למיין את הסטודנטים בצורה יעילה: הצורה היעילה ביותר היא להשתמש בHASH פתוח בצורה הבאה: אתה לוקח את הסטודנט הראשון, עושה מודולו 100 על התעודת זהות שלו, והולך למערך במקום של המספר שיצא לך, למשל נגיד שיצא לך 56 אז אתה הולך למקום ה56 במערך ומשרשר את הסטודנט לשם. לוקח את הבא בתור עושה מודולו, נגיד שעכשיו יצא לך 40 אתה הולך למקום ה40 במערך (שם יש "ראש" של רשימה ריקה) ומשרשר שם את הסטודנט. ככה אתה ממשיך וממשיך ואז נגיד שאחרי 50 סטודנטים יוצא לך עוד סטודנט שהמודולו שלו הוא 56, אתה הולך למערך למקום ה56 אבל שם כבר יש סטודנט אחד!!!! אז מה שאתה עושה זה פשוט מאוד: משרשר את הסטודנט לסטודנט שכבר שם. הבנת את הרעיון? עכשיו גמרת לשרשר את כל הסטודנטים. מישהו בא אליך ואומר לך ככה: "שלוף נא את הנתונים של הסטודנט מוישה זוכמן מהHASH TABLE" ואז אתה אומר לו אוקיי מה המספר תעודת זהות שלו? ואז אתה עושה מודולו... יצא נגיד 30, אז אתה הולך למערך למקום ה30 ומתחיל לחפש את מוישה זוכמן שם. אתה מבין? נגיד שהסטודנט הראשון הוא לא מוישה זוכמן אז אתה הולך לסטודנט הבא שמשורשר אליו ואם גם זה לא הוא אז אתה הולך לבא בתור וכולי עד שאתה מגיע אליו. ככה בעצם יש לך טבלה HASH TABLE שהסיבוכיות לחיפוש בה היא (1)O יש לציין שאם לכל הסטודנטים יש אותו מודולו אז תהיה לך רשימה מקושרת ארוכה מאוד שהסיבוכיות בה יהיה O של N אבל מבחינה הסתברותית תהיה לך כאן סיבוכיות ממש נמוכה (בעקרון O של 1) יאיר

 

[ronihp]

תודה!!!! ../images/Emo13.gif ../images/Emo13.gif

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

 

[ihovav]

מצורף קוד ב C

ל HASH סגור

 

[The_Mighty_Perr]

ניא לא מכיר את הנושא טוב, אבל

בס"ד נראה לי שהרעיון של HASH TAVLES לא קשור לרשימות מקושרות בכלל. הרעיון של אם יש 2 רכיבים שקיבלו אותו "קדו HASH" לשרשר אותם אחד לשני הוא לא טוב כ"כ. 1. כל מה שעושים זה יוצרים "קוד" לכל אלמנט, ושומרים לפי הקוד. 2. יש הרבה אלגוריתמים ל-HASHING, והאלגוריתם שלך(שלא התעמקתי בו) מתאים במיוחד לדוגמא שהבאת(כנראה, שוב, לא התעמקתי בו) 3. יש הרבה שיטות לשמור 2 רכיבים עם אותו "קוד"... בברכה...

 

[ronihp]

דווקא ממה שקראתי

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

 

[linuxius]

זה נקרא אזור גלישה

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