פונקציית Hash
בסעיף זה, נדון בפונקציית ה-hash שעוזרת להפעיל את קוד ה-hash של המפתח הקשור לפריט הנתונים במבנה הנתונים כפי שהוזכר בהמשך:
Int hashItem ( int מַפְתֵחַ ){
לַחֲזוֹר מַפְתֵחַ % גודל שולחן ;
}
תהליך ביצוע האינדקס של מערך נקרא hashing. לפעמים, אותו סוג של קוד מבוצע כדי ליצור את אותו אינדקס באמצעות אותם מפתחות הנקראים התנגשויות אשר מטופל באמצעות שרשור שונה (יצירת רשימה מקושרת) ויישום אסטרטגיות מענה פתוחות.
עבודה של טבלת Hash ב-C++
המצביעים על הערכים האמיתיים נשמרים בטבלת הגיבוב. הוא משתמש במפתח כדי לחפש את האינדקס של מערך שבו יש לאחסן את הערכים מול המפתחות במיקום הרצוי במערך. לקחנו את טבלת הגיבוב בגודל 10 כפי שהוזכר בהמשך:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
הבה ניקח באקראי נתונים כלשהם מול מפתחות שונים ונשמור את המפתחות הללו בטבלת hash רק על ידי חישוב האינדקס. אז הנתונים מאוחסנים מול המפתחות באינדקס המחושב בעזרת פונקציית hash. נניח שניקח נתונים = {14,25,42,55,63,84} ומפתחות =[ 15,9,5,25,66,75 ].
חשב את האינדקס של נתונים אלה באמצעות פונקציית ה-hash. ערך המדד מוזכר בהמשך:
| מַפְתֵחַ | חֲמֵשׁ עֶשׂרֵה | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| חשב אינדקס | 15%10 = 5 | 9%10=0 | 29%10=9 | 43%10=3 | 66%10=6 | 71%10=1 |
| נתונים | 14 | 25 | 42 | 55 | 63 | 84 |
לאחר יצירת האינדקס של מערך, מקם את הנתונים מול המפתח באינדקס המדויק של מערך נתון כפי שתואר קודם לכן.
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
לאחר מכן, אנו יכולים לראות שהתנגשות מתרחשת אם לשני מפתחות או יותר יש את אותו קוד hash אשר מביא לאותו אינדקס של האלמנטים במערך. יש לנו פתרון אחד כדי למנוע את סיכויי ההתנגשות: בחירת שיטת hash טובה ויישום האסטרטגיות המדויקות.
כעת, בואו נדון בטכניקות היישום השונות בעזרת דוגמאות מתאימות.
דוגמה: הוסף נתונים בטבלת Hash באמצעות טכניקת Hash פתוחה
בדוגמה זו, אנו לוקחים טכניקת יישום כמו Open Hashing כדי למנוע התנגשות בטבלת ה-hash. בגיבוב פתוח או שרשור, אנו יוצרים רשימה מקושרת כדי לשרשר את הערכים של טבלת הגיבוב. קטע הקוד של דוגמה זו מצורף בהמשך המתאר את טכניקת הגיבוב הפתוחה:
#include#include <רשימה>
מעמד טבלת גיבוב {
פְּרָטִי :
סטָטִי const int גודל שולחן = 10 ;
סטד :: רשימה < int > לשולחן יש [ גודל שולחן ] ;
int hashFunc ( int מַפְתֵחַ ) {
לַחֲזוֹר מַפְתֵחַ % גודל שולחן ;
}
פּוּמְבֵּי :
בָּטֵל לְהַכנִיס ( int מַפְתֵחַ ) {
int אינדקס = hashFunc ( מַפְתֵחַ ) ;
לשולחן יש [ אינדקס ] . התנגדות ( מַפְתֵחַ ) ;
}
בָּטֵל ViewTable ( ) {
ל ( int אני = 0 ; אני < גודל שולחן ; ++ אני ) {
סטד :: cout << '[' << אני << ']' ;
ל ( אוטומטי זה = לשולחן יש [ אני ] . התחל ( ) ; זה ! = לשולחן יש [ אני ] . סוֹף ( ) ; ++ זה ) {
סטד :: cout << ' -> ' << * זה ;
}
סטד :: cout << סטד :: endl ;
}
}
} ;
int רָאשִׁי ( ) {
HashTable hasTable ;
hasTable. לְהַכנִיס ( חֲמֵשׁ עֶשׂרֵה ) ;
hasTable. לְהַכנִיס ( 33 ) ;
hasTable. לְהַכנִיס ( 23 ) ;
hasTable. לְהַכנִיס ( 65 ) ;
hasTable. לְהַכנִיס ( 3 ) ;
hasTable. ViewTable ( ) ;
לַחֲזוֹר 0 ;
}
זו דוגמה מאוד מעניינת: אנחנו בונים רשימה מקושרת ומכניסים את הנתונים לטבלת הגיבוב. קודם כל, אנחנו מגדירים את הספריות בתחילת התוכנית. ה < רשימה > הספרייה משמשת ליישום הרשימה המקושרת. לאחר מכן, אנו בונים מחלקה בשם 'HashTable' ויוצרים את התכונות של המחלקה שהן פרטיות כגודל טבלה ומערך טבלה באמצעות מילת המפתח 'private:'. זכור שהתכונות הפרטיות אינן ניתנות לשימוש מחוץ לכיתה. כאן, אנו לוקחים את גודל הטבלה כ- '10'. אנו מאתחלים את שיטת הגיבוב באמצעות זה ומחשבים את האינדקס של טבלת הגיבוב. בפונקציית ה-hash, אנו מעבירים את המפתח והגודל של טבלת ה-hash.
אנו בונים כמה פונקציות נדרשות והופכים את הפונקציות הללו לציבוריות בכיתה. זכור שפונקציות ציבוריות ניתנות לשימוש מחוץ לכיתה בכל מקום. אנו משתמשים במילת המפתח 'ציבורי:' כדי להתחיל את החלק הציבורי של הכיתה . מכיוון שאנו רוצים להוסיף אלמנטים חדשים לטבלת ה-hash, אנו יוצרים פונקציה בשם 'InsertHash' עם מפתח כארגומנט של הפונקציה. בפונקציה 'הוספה', אנו מאתחלים את משתנה האינדקס. נעביר את פונקציית ה-hash למשתנה האינדקס. לאחר מכן, העבירו את משתנה האינדקס לרשימה המקושרת tableHas[]באמצעות שיטת 'push' כדי להוסיף אלמנט לטבלה.
לאחר מכן, אנו בונים פונקציית 'viewHashTab' כדי להציג את טבלת הגיבוב כדי לראות את הנתונים החדשים שהוכנסו. בפונקציה זו, אנו לוקחים לולאה 'for' שמחפשת את הערכים עד לסוף טבלת הגיבוב. ודא שהערכים מאוחסנים באותו אינדקס שפותחו באמצעות פונקציית hash. בלולאה, אנו מעבירים את הערכים באינדקס המתאימים ומסיימים את המחלקה כאן. בפונקציה 'main', אנו לוקחים את האובייקט של מחלקה בשם 'hasTable'. בעזרת אובייקט המחלקה הזה, נוכל לגשת לשיטת ההכנסה על ידי העברת המפתח בשיטה. המפתח שהעברנו בפונקציה 'main' מחושב בפונקציית 'insert' שמחזירה את מיקום האינדקס בטבלת ה-hash. הצגנו את טבלת הגיבוב על ידי קריאה לפונקציה 'תצוגה' בעזרת אובייקט 'Class'.
הפלט של קוד זה מצורף בקטע הבא:
כפי שאנו יכולים לראות, טבלת הגיבוב נוצרת בהצלחה באמצעות הרשימה המקושרת ב-C++. שרשור פתוח משמש כדי למנוע התנגשות של אותו מדד.
סיכום
בסופו של דבר, הגענו למסקנה שטבלת גיבוב היא הטכניקה המתפתחת ביותר לאחסון ולקבלת המפתחות עם צמדי ערכים לטיפול בכמויות אדירות של נתונים ביעילות. סיכויי ההתנגשות גבוהים מאוד בטבלת ה-hash, והורסים את הנתונים והאחסון שלהם. אנו יכולים להתגבר על התנגשות זו באמצעות טכניקות שונות של ניהול טבלת הגיבוב. על ידי פיתוח טבלת הגיבוב ב-C++, המפתחים יכולים להגביר את הביצועים באמצעות הטכניקה המתאימה ביותר לאחסון הנתונים בטבלת הגיבוב. אנו מקווים שמאמר זה מועיל להבנתך את טבלת הגיבוב.