Hash Map
- פותח הנושא מיס פטל
- פורסם בתאריך
תשובה:
map: (ללא הגדרות מיוחדות) עושה מיפוי כאשר לכל x בקבוצה X יש y בקבוצה Y כך שגודל הקבוצה X שווה לגודל הקבוצה Y (למרות שהערכים בקבוצה Y יכולים לחזור על עצמם) לדוגמא bitmap: לכל bit במפת התמונה יש יצוג שונה. או דוגמא נוספת מיפוי עוצמות: 1 2 3 4 5 6 2 4 6 8 10 12 לכל טבעי יש את הזוגי המתאים לו... hash לעומת זאת מציינת שלכל x בקבוצה X יש מיפוי ל y בקבוצה Y כאשר Y קטנה מ X. כלומר כל כמה ערכים ב X ממופים לערך יחיד ב Y. לדוגמא מיפוי ידוע כזה זה באמצעות module: הערכים 12.3 17.3 1236.3 ממופים כולם לערך 3. ב hash מספר הערכים בדוגמא זו ב Y ידוע ושווה ל 10. לעומת זאת מספר הערכים בקבוצה X הוא אין סופי
map: (ללא הגדרות מיוחדות) עושה מיפוי כאשר לכל x בקבוצה X יש y בקבוצה Y כך שגודל הקבוצה X שווה לגודל הקבוצה Y (למרות שהערכים בקבוצה Y יכולים לחזור על עצמם) לדוגמא bitmap: לכל bit במפת התמונה יש יצוג שונה. או דוגמא נוספת מיפוי עוצמות: 1 2 3 4 5 6 2 4 6 8 10 12 לכל טבעי יש את הזוגי המתאים לו... hash לעומת זאת מציינת שלכל x בקבוצה X יש מיפוי ל y בקבוצה Y כאשר Y קטנה מ X. כלומר כל כמה ערכים ב X ממופים לערך יחיד ב Y. לדוגמא מיפוי ידוע כזה זה באמצעות module: הערכים 12.3 17.3 1236.3 ממופים כולם לערך 3. ב hash מספר הערכים בדוגמא זו ב Y ידוע ושווה ל 10. לעומת זאת מספר הערכים בקבוצה X הוא אין סופי
נפשט את זה קצת...
ע"י דוגמה פשוטה: נגדיר נוסחאת hash אשר מחזירה מודולור 10 -כלומר: h = X%10 נקצה מערך של זיכרון בגודל 10 תאים __,__,__,__,__,__,__,__,__,__, 0 1 2 3 4 5 6 7 8 9 אנו רוצים לשמור את הערך "AAA" - ונותים לו מפתח 223. החישוב יעשה כך: h = 223%10 = 3 כלומר הערך ישמר בתא מספר 3 המערך החדש __,__,__,AAA,__,__,__,__,__,__, 0 1 2 3 4 5 6 7 8 9 נוסיף את הערך "BBB" עם המפתח 186 -> h = 186%10 = 6 המערך החדש __,__,__,AAA,__,__,BBB,__,__,__, 0 1 2 3 4 5 6 7 8 9 עכשיו אנו רוצים לקבל את הערך של המפתח 223 מבצעים את החישוב שוב: h = 223%10 = 3 כלומר הערך שלנו יושב בתא מספר 3 ==> AAA * בפועל הדבר יותר מורכב, אבל ככה זה בגדול עובד. כמו שרואים, ההכנסה וקריאה הם ב (O (1 בממוצע (זה יהיה שונה אם יהיו לנו מפתחות אשר חישוב הhash יחזיר לנו את אותו תא), אבל ניתן לראות שיש הרבה תאים שלא בשימוש
ע"י דוגמה פשוטה: נגדיר נוסחאת hash אשר מחזירה מודולור 10 -כלומר: h = X%10 נקצה מערך של זיכרון בגודל 10 תאים __,__,__,__,__,__,__,__,__,__, 0 1 2 3 4 5 6 7 8 9 אנו רוצים לשמור את הערך "AAA" - ונותים לו מפתח 223. החישוב יעשה כך: h = 223%10 = 3 כלומר הערך ישמר בתא מספר 3 המערך החדש __,__,__,AAA,__,__,__,__,__,__, 0 1 2 3 4 5 6 7 8 9 נוסיף את הערך "BBB" עם המפתח 186 -> h = 186%10 = 6 המערך החדש __,__,__,AAA,__,__,BBB,__,__,__, 0 1 2 3 4 5 6 7 8 9 עכשיו אנו רוצים לקבל את הערך של המפתח 223 מבצעים את החישוב שוב: h = 223%10 = 3 כלומר הערך שלנו יושב בתא מספר 3 ==> AAA * בפועל הדבר יותר מורכב, אבל ככה זה בגדול עובד. כמו שרואים, ההכנסה וקריאה הם ב (O (1 בממוצע (זה יהיה שונה אם יהיו לנו מפתחות אשר חישוב הhash יחזיר לנו את אותו תא), אבל ניתן לראות שיש הרבה תאים שלא בשימוש
נפשט את זה קצת...
ע"י דוגמה פשוטה: נגדיר נוסחאת hash אשר מחזירה מודולור 10 -כלומר: h = X%10 נקצה מערך של זיכרון בגודל 10 תאים __,__,__,__,__,__,__,__,__,__, 0 1 2 3 4 5 6 7 8 9 אנו רוצים לשמור את הערך "AAA" - ונותים לו מפתח 223. החישוב יעשה כך: h = 223%10 = 3 כלומר הערך ישמר בתא מספר 3 המערך החדש __,__,__,AAA,__,__,__,__,__,__, 0 1 2 3 4 5 6 7 8 9 נוסיף את הערך "BBB" עם המפתח 186 -> h = 186%10 = 6 המערך החדש __,__,__,AAA,__,__,BBB,__,__,__, 0 1 2 3 4 5 6 7 8 9 עכשיו אנו רוצים לקבל את הערך של המפתח 223 מבצעים את החישוב שוב: h = 223%10 = 3 כלומר הערך שלנו יושב בתא מספר 3 ==> AAA * בפועל הדבר יותר מורכב, אבל ככה זה בגדול עובד. כמו שרואים, ההכנסה וקריאה הם ב (O (1 בממוצע (זה יהיה שונה אם יהיו לנו מפתחות אשר חישוב הhash יחזיר לנו את אותו תא), אבל ניתן לראות שיש הרבה תאים שלא בשימוש
ע"י דוגמה פשוטה: נגדיר נוסחאת hash אשר מחזירה מודולור 10 -כלומר: h = X%10 נקצה מערך של זיכרון בגודל 10 תאים __,__,__,__,__,__,__,__,__,__, 0 1 2 3 4 5 6 7 8 9 אנו רוצים לשמור את הערך "AAA" - ונותים לו מפתח 223. החישוב יעשה כך: h = 223%10 = 3 כלומר הערך ישמר בתא מספר 3 המערך החדש __,__,__,AAA,__,__,__,__,__,__, 0 1 2 3 4 5 6 7 8 9 נוסיף את הערך "BBB" עם המפתח 186 -> h = 186%10 = 6 המערך החדש __,__,__,AAA,__,__,BBB,__,__,__, 0 1 2 3 4 5 6 7 8 9 עכשיו אנו רוצים לקבל את הערך של המפתח 223 מבצעים את החישוב שוב: h = 223%10 = 3 כלומר הערך שלנו יושב בתא מספר 3 ==> AAA * בפועל הדבר יותר מורכב, אבל ככה זה בגדול עובד. כמו שרואים, ההכנסה וקריאה הם ב (O (1 בממוצע (זה יהיה שונה אם יהיו לנו מפתחות אשר חישוב הhash יחזיר לנו את אותו תא), אבל ניתן לראות שיש הרבה תאים שלא בשימוש
היתרון של hash זה שהוא תופס
פחות מקום בזיכרון, תראי אני לא יודע באיזה הקשר את שואלת את השאלות. עושים בנושאים האלה שימוש בהרבה תחומים. בואי ניקח דוגמא של hash. hash משמש לדוגמא לניהול וארגון רשומות בקבצים בינאריים נניח שיש לך מפתח שמהווה את ת.ז של עובדים במפעל. ואין לך hash. עכשיו את צריכה להכניס לקובץ הבינארי struct ש השדה ת.ז זה 123456. איפה תשימי את זה, את רוצה לשמור על חיפוש מהיר, את יכולה כל פעם להכניס רשומה בסוף ולעשות מעין מיון. אבל אז יהיה לך קשה למצוא לאחר מכן את הרשומה, כי היא לא נמצאת במקום 123456*sizeofstruct. כי יש באמצע רשומות שלא נמצאות. ולכן כל פעם תאלצי לעשות חיפוש. הדרך הכי מהירה היא אם תשימי את הרשומה במקום 123456*sizeofstruct בקובץ. ואז כל פעם תפני למקום הזה בזיכרון ותקבלי את הרשומה מידית, וגם מובטח לך ששום רשומה אחרת לא תדרוס את זו הנוכחית כי 123456 הוא חד חד ערכי. הבעי כפי שאת רואה שאת חייבת להשתמש בקובץ ענק אפילו אם יש לך רק איזה 100 רשומות כאן מגיע הפתרון של hash: יש טווח מיפוי ל 10 מקומות בקובץ בלבד במקומות יש פוינטרים לערך הראשון בקובץ אחר ששיך למקום הזה. וכל ID מתרגם לאחד המקומות האלה (של ה 10) ומשם מצביע בפוינטר על מקום בקובץ ה struct. במקרה ששני ערכים ממופים לאותו מקום נניח 3 (כי המודול של שניהם זה 3) אז בקובץ הנוסף יהיה מעין רשימה מקושרת שה next יהווה את המקום הבא שקשור לאותו ערך. ה next בקובץ ה hash יהווה את המקום הראשון בקובץ השני. אם תדאגי שגודל ה hash לא יהיה רק 10 אלא מספר יותר גדול שעדיין לא יעמיס על הזיכרון זה יהיה אידיאלי מקווה שהבנת הכל
פחות מקום בזיכרון, תראי אני לא יודע באיזה הקשר את שואלת את השאלות. עושים בנושאים האלה שימוש בהרבה תחומים. בואי ניקח דוגמא של hash. hash משמש לדוגמא לניהול וארגון רשומות בקבצים בינאריים נניח שיש לך מפתח שמהווה את ת.ז של עובדים במפעל. ואין לך hash. עכשיו את צריכה להכניס לקובץ הבינארי struct ש השדה ת.ז זה 123456. איפה תשימי את זה, את רוצה לשמור על חיפוש מהיר, את יכולה כל פעם להכניס רשומה בסוף ולעשות מעין מיון. אבל אז יהיה לך קשה למצוא לאחר מכן את הרשומה, כי היא לא נמצאת במקום 123456*sizeofstruct. כי יש באמצע רשומות שלא נמצאות. ולכן כל פעם תאלצי לעשות חיפוש. הדרך הכי מהירה היא אם תשימי את הרשומה במקום 123456*sizeofstruct בקובץ. ואז כל פעם תפני למקום הזה בזיכרון ותקבלי את הרשומה מידית, וגם מובטח לך ששום רשומה אחרת לא תדרוס את זו הנוכחית כי 123456 הוא חד חד ערכי. הבעי כפי שאת רואה שאת חייבת להשתמש בקובץ ענק אפילו אם יש לך רק איזה 100 רשומות כאן מגיע הפתרון של hash: יש טווח מיפוי ל 10 מקומות בקובץ בלבד במקומות יש פוינטרים לערך הראשון בקובץ אחר ששיך למקום הזה. וכל ID מתרגם לאחד המקומות האלה (של ה 10) ומשם מצביע בפוינטר על מקום בקובץ ה struct. במקרה ששני ערכים ממופים לאותו מקום נניח 3 (כי המודול של שניהם זה 3) אז בקובץ הנוסף יהיה מעין רשימה מקושרת שה next יהווה את המקום הבא שקשור לאותו ערך. ה next בקובץ ה hash יהווה את המקום הראשון בקובץ השני. אם תדאגי שגודל ה hash לא יהיה רק 10 אלא מספר יותר גדול שעדיין לא יעמיס על הזיכרון זה יהיה אידיאלי מקווה שהבנת הכל
כמה הגדרות.
מפה, במובן הכללי שלה, היא מיפוי בין איברים מסוג א' לבין איברים מסוג ב' (הסוגים יכולים להיות זהים). ניתנו לך דוגמאות. בהגדרה הזו אין התחייבות לסדר גודל מסוים של ביצועים. ב-STL של ++C תמצאי map שממומשת על ידי עץ מאוזן, כמו למשל red-black tree או עץ 2-3. במפה רגילה אין הנחות יסוד - כלומר, כל ערך מסוג א' יכול להיות ממופה לכל ערך שהוא מסוג ב'. hash map היא מפה שמתבססת על הנחת יסוד מסוימת, לפיה כמות האיברים בפועל תהיה קטנה משמעותית מהטווח האפשרי שייתכן. למשל, בואי נגיד שאת רוצה לעשות טבלת ימי הולדת ל-50 סטודנטים, כשהמפתח שלך הוא תאריך הלידה. בואי נייצג אותו ב-4 ספרות לצורך העניין, DDMM. הטווח שלך הוא 10000 מספרים. אם היית רוצה יעילות מקסימלית, יכולת להחזיק מערך של 10000 איברים, ואז היה לך (O(1 תמיד לכל פעולה, כמובן. הבעיה היא זיכרון, כמובן. 10000 תאים זה עוד איכשהו יכול להתקבל, אבל אם זה היה 10000000, זה היה סיפור אחר. ובכלל, יש לך 50 תלמידים, למה שתשמרי מערך של 10000 תאים בשביל 50 תלמידים? (אם נדייק, הטווח הוא 0101 עד 3112 שזה קצת פחות, אבל לצורך הדוגמה נמשיך ככה...) פה נכנס המנגנון של HASH. ניקח נוסחה מאוד פשטנית - מודולו 50. אם נגיד יצא לך 1508 בתור תאריך לידה, אז מודולו 50 ייתן 8, ואז את צריכה לשים את הנתון בתא מספר 8 במערך שלך, שעכשיו גודלו יהיה 50 ולא 10000. כמו שאת בטח מבינה, המנגנון הוא בעייתי, כי כל מי שנולד באוגוסט ייפול בתא מספר 8, שזה לא ממש מוצלח. ואכן, שתי בעיות שאיתן מתמודדים יישומי HASH MAP מוצלחים הן בעיית הכפולים, כלומר - מה לעשות כשיש שני נתונים שנוחתים באותו תא, ובעיית הנוסחה הראשונית, כאשר למעשה המטרה המרכזית היא בחירת נוסחה באופן כזה שיפזר את הנתונים בצורה מיטבית על פני כל המערך המוקטן, תוך כדי מניעת כפולים. זה היה HASH MAP על קצה המזלג. בעיקרון השאיפה היא ל-(1)O במקרה הטוב, מה שאכן מושג. רוב הזמן, אם ה-HASH MAP ממומשת בצורה טובה, מספר הפעולות שיידרשו הוא קטן, גם אם לא 1 הוא יהיה 2-3 ולא יותר (שוב - בד"כ).
מפה, במובן הכללי שלה, היא מיפוי בין איברים מסוג א' לבין איברים מסוג ב' (הסוגים יכולים להיות זהים). ניתנו לך דוגמאות. בהגדרה הזו אין התחייבות לסדר גודל מסוים של ביצועים. ב-STL של ++C תמצאי map שממומשת על ידי עץ מאוזן, כמו למשל red-black tree או עץ 2-3. במפה רגילה אין הנחות יסוד - כלומר, כל ערך מסוג א' יכול להיות ממופה לכל ערך שהוא מסוג ב'. hash map היא מפה שמתבססת על הנחת יסוד מסוימת, לפיה כמות האיברים בפועל תהיה קטנה משמעותית מהטווח האפשרי שייתכן. למשל, בואי נגיד שאת רוצה לעשות טבלת ימי הולדת ל-50 סטודנטים, כשהמפתח שלך הוא תאריך הלידה. בואי נייצג אותו ב-4 ספרות לצורך העניין, DDMM. הטווח שלך הוא 10000 מספרים. אם היית רוצה יעילות מקסימלית, יכולת להחזיק מערך של 10000 איברים, ואז היה לך (O(1 תמיד לכל פעולה, כמובן. הבעיה היא זיכרון, כמובן. 10000 תאים זה עוד איכשהו יכול להתקבל, אבל אם זה היה 10000000, זה היה סיפור אחר. ובכלל, יש לך 50 תלמידים, למה שתשמרי מערך של 10000 תאים בשביל 50 תלמידים? (אם נדייק, הטווח הוא 0101 עד 3112 שזה קצת פחות, אבל לצורך הדוגמה נמשיך ככה...) פה נכנס המנגנון של HASH. ניקח נוסחה מאוד פשטנית - מודולו 50. אם נגיד יצא לך 1508 בתור תאריך לידה, אז מודולו 50 ייתן 8, ואז את צריכה לשים את הנתון בתא מספר 8 במערך שלך, שעכשיו גודלו יהיה 50 ולא 10000. כמו שאת בטח מבינה, המנגנון הוא בעייתי, כי כל מי שנולד באוגוסט ייפול בתא מספר 8, שזה לא ממש מוצלח. ואכן, שתי בעיות שאיתן מתמודדים יישומי HASH MAP מוצלחים הן בעיית הכפולים, כלומר - מה לעשות כשיש שני נתונים שנוחתים באותו תא, ובעיית הנוסחה הראשונית, כאשר למעשה המטרה המרכזית היא בחירת נוסחה באופן כזה שיפזר את הנתונים בצורה מיטבית על פני כל המערך המוקטן, תוך כדי מניעת כפולים. זה היה HASH MAP על קצה המזלג. בעיקרון השאיפה היא ל-(1)O במקרה הטוב, מה שאכן מושג. רוב הזמן, אם ה-HASH MAP ממומשת בצורה טובה, מספר הפעולות שיידרשו הוא קטן, גם אם לא 1 הוא יהיה 2-3 ולא יותר (שוב - בד"כ).
זה בדיוק הרעיון של HASH
נניח שאנחנו מחפשים מחרוזות. דרך אחת זה לשמור אותן במערך רגיל ולעבור עליו כאשר משווים כל מחרוזת למחרוזת אותה מחפשים. בטבלת גיבוב (HASH), יוצרים ערך מהמחרוזת. אחת הדרכים זה ליצור חתימה שלה (למשל CRC). עכשיו מגדירים מערך בגודל מסויים (נניח 1023). את המחרוזת אנחנו ממירים למספר (0-1022) ומוצאים את המיקום במהירות בלי להתחיל לסרוק את כל המערך. אני מצרף קוד פשוט ביותר לטבלה בגודל 256.
נניח שאנחנו מחפשים מחרוזות. דרך אחת זה לשמור אותן במערך רגיל ולעבור עליו כאשר משווים כל מחרוזת למחרוזת אותה מחפשים. בטבלת גיבוב (HASH), יוצרים ערך מהמחרוזת. אחת הדרכים זה ליצור חתימה שלה (למשל CRC). עכשיו מגדירים מערך בגודל מסויים (נניח 1023). את המחרוזת אנחנו ממירים למספר (0-1022) ומוצאים את המיקום במהירות בלי להתחיל לסרוק את כל המערך. אני מצרף קוד פשוט ביותר לטבלה בגודל 256.
char hash(const char* szString) { for (char result=0xff;*szString;result^=*szString++); return result; } const int size=255; struct item { const char* szKey; int nValue; } void insert(item pTable[size],const char* szString,int nValue) { char pos=hash(szString); pTable[pos].szKey=szString; pTable[pos].nValue=nValue; } int find(item pTable[size],const char* szString) { return pTable[hash(szString)].nValue; }
כמובן שבמקרה הנ"ל יכולים להיות כפילויות. בדר"כ זה ממומש עם רשימה מקושרת בכל NODE של הטבלה.
Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.