TechCodeview

מבוא ל-Hash במבנה הנתונים:

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

מה זה האשינג?

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

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

מהו מפתח hash?

בהקשר של hashing, מפתח hash (הידוע גם כ-hash value או hash code) הוא ייצוג מספרי או אלפאנומרי בגודל קבוע שנוצר על ידי אלגוריתם hashing. הוא נגזר מנתוני הקלט, כגון מחרוזת טקסט או קובץ, באמצעות תהליך המכונה hashing.

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

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

איך עובד Hashing?

ניתן לחלק את תהליך הגיבוב לשלושה שלבים:

css מודגש

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

אלגוריתמי גיבוב:

ישנם אלגוריתמי גיבוב רבים, לכל אחד מהם יתרונות וחסרונות ברורים. האלגוריתמים הפופולריים ביותר כוללים את הדברים הבאים:

• MD5: אלגוריתם גיבוב בשימוש נרחב המייצר ערך גיבוב של 128 סיביות.
• SHA-1: אלגוריתם גיבוב פופולרי המייצר ערך גיבוב של 160 סיביות.
• SHA-256: אלגוריתם גיבוב מאובטח יותר המייצר ערך גיבוב של 256 סיביות.

פונקציית Hash:

פונקציית Hash: פונקציית Hash היא סוג של פעולה מתמטית שלוקחת קלט (או מפתח) ומוציאה תוצאה בגודל קבוע המכונה קוד Hash או Hash. פונקציית ה-hash חייבת תמיד להניב את אותו קוד hash עבור אותו קלט כדי להיות דטרמיניסטית. בנוסף, פונקציית ה-hash צריכה לייצר קוד hash ייחודי עבור כל קלט, המכונה מאפיין hash.

ישנם סוגים שונים של פונקציות גיבוב, כולל:

שיטת חלוקה:

שיטה זו כוללת חלוקת המפתח בגודל הטבלה ולקחת את היתרה כערך ה-hash. לדוגמה, אם גודל הטבלה הוא 10 והמפתח הוא 23, ערך הגיבוב יהיה 3 (23% 10 = 3).

שיטת הכפל:

שיטה זו כוללת הכפלת המפתח בקבוע ולקחת את החלק השברי של המוצר כערך ה-hash. לדוגמה, אם המפתח הוא 23 והקבוע הוא 0.618, ערך הגיבוב יהיה 2 (floor(10*(0.61823 - floor(0.61823))) = floor(2.236) = 2).

גיבוב אוניברסלי:

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

מכיל שיטת java

רזולוציית התנגשות

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

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

דוגמה לרזולוציית התנגשות

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

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

0:

1:

2:

3:

מרחף ב-CSS

4: ג'ון: 123456 -> מרי: 987654

5:

טבלת גיבוב:

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

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

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

Hash Table Operations

ישנן מספר פעולות שניתן לבצע בטבלת גיבוב, כולל:

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

יצירת טבלת Hash:

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

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

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

 unsigned long hash(char* str) { unsigned long hash = 5381; int c; while (c = *str++) { hash = ((hash << 5) + hash) + c; } return hash; } 

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

טבלאות Hash ב-C++

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

כדי להשתמש במיכל unordered_map ב-C++, עליך לכלול את קובץ הכותרת. הנה דוגמה כיצד ליצור מיכל unordered_map ב-C++:

 #include #include int main() { // create an unordered_map container std::unordered_map my_map; // insert some key-value pairs into the map my_map['apple'] = 10; my_map['banana'] = 20; my_map['orange'] = 30; // print the value associated with the 'banana' key std::cout << my_map['banana'] << std::endl; return 0; } 

הֶסבֵּר:

• תוכנית זו מדגימה את השימוש במיכל unordered_map ב-C++, אשר מיושם באמצעות טבלת hash ומספקת גישה מהירה לצמדי מפתח-ערך.
• ראשית, התוכנית כוללת את קבצי הכותרת הדרושים: ו.
• לאחר מכן, התוכנית יוצרת מיכל unordered_map ריק בשם my_map, הכולל מפתחות מחרוזת וערכי מספר שלמים. זה נעשה באמצעות התחביר std::unordered_map my_map;
• לאחר מכן, התוכנה מכניסה שלושה זוגות מפתח-ערך לתוך מיכל my_map באמצעות האופרטור []: 'apple' עם ערך של 10, 'בננה' עם ערך של 20 ו-'orange' עם ערך של 30.
• זה נעשה באמצעות התחביר my_map['apple'] = 10;, my_map['banana'] = 20;, ו-my_map['orange'] = 30; בהתאמה.
• לבסוף, התוכנה מדפיסה את הערך המשויך למפתח 'בננה' באמצעות האופרטור [] ואובייקט std::cout.

פלט תוכנית:

להחליף את המחרוזת ב-java

הוספת נתונים לטבלת Hash

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

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

 typedef struct node { char* key; int value; struct node* next; } node; node* hash_table[100]; void insert(char* key, int value) { unsigned long hash_value = hash(key) % 100; node* new_node = (node*) malloc(sizeof(node)); new_node->key = key; new_node->value = value; new_node->next = NULL; if (hash_table[hash_value] == NULL) { hash_table[hash_value] = new_node; } else { node* curr_node = hash_table[hash_value]; while (curr_node->next != NULL) { curr_node = curr_node->next; } curr_node->next = new_node; } } 

הֶסבֵּר:

• ראשית, מוגדר מבנה הנקרא node, המייצג צומת בודד בטבלת ה-hash.
• לכל צומת יש שלושה איברים: מפתח char* לאחסון המפתח, ערך int לאחסון הערך המשויך, ומצביע לצומת אחר שנקרא ליד כדי לטפל בהתנגשויות בטבלת ה-hash באמצעות רשימה מקושרת.
• מערך של מצביעי צומת הנקרא hash_table מוצהר בגודל 100. מערך זה ישמש לאחסון האלמנטים של טבלת ה-hash.
• פונקציית ה-insert לוקחת מפתח char* וערך int כפרמטרים.
• זה מתחיל על ידי חישוב ערך ה-hash עבור המפתח הנתון באמצעות פונקציית ה-hash, שלפי ההנחה היא מוגדרת במקום אחר בתוכנית.
• לאחר מכן ערך ה-hash מצטמצם כך שיתאים לגודל מערך ה-hash_table באמצעות האופרטור המודולוס % 100.
• צומת חדש נוצר באמצעות הקצאת זיכרון דינמית (malloc(sizeof(node))), והחברים שלו (מפתח, ערך והבא) מוקצים עם המפתח, הערך וה-NULL שסופקו, בהתאמה.
• אם החריץ המתאים במערך hash_table ריק (NULL), מה שמציין שלא התרחשה התנגשות, הצומת החדש מוקצה למשבצת זו ישירות (hash_table[hash_value] = new_node).

עם זאת, אם כבר קיים צומת באותו אינדקס במערך hash_table, הפונקציה צריכה לטפל בהתנגשות. הוא חוצה את הרשימה המקושרת החל מהצומת הנוכחי (hash_table[hash_value]) ועובר לצומת הבא עד שהוא מגיע לסוף (curr_node->next != NULL). ברגע שמגיעים לסוף הרשימה, הצומת החדש מצורף כצומת הבא (curr_node->next = new_node).

הטמעת Hashing ב-C++:

בואו נראה יישום של hashing ב-C++ תוך שימוש בכתובת פתוחה וגישוש ליניארי לפתרון התנגשות. ניישם טבלת hash המאחסנת מספרים שלמים.

 #include using namespace std; const int SIZE = 10; class HashTable { private: int arr[SIZE]; public: HashTable() { for (int i = 0; i <size; i++) { arr[i]="-1;" } int hashfunction(int key) return key % size; void insert(int index="hashFunction(key);" i="0;" while (arr[(index + i) size] !="-1" && arr[(index i++; if cout << 'element already exists in the hash table' endl; else remove(int deleted from return; not found display() for (int < (arr[i]="=" -1 || -2) continue; 'index ' ': }; main() hashtable ht; ht.insert(5); ht.insert(15); ht.insert(25); ht.insert(35); ht.insert(45); ht.display(); ht.remove(15); ht.remove(10); ht.insert(55); 0; pre> <p> <strong>Explanation:</strong> </p> <ul> <li>This program implements a hash table data structure using linear probing to handle collisions.</li> <li>A hash table is a data structure that stores data in key-value pairs, where the keys are hashed using a hash function to generate an index in an array. This allows for constant-time average-case complexity for inserting, searching, and deleting elements from the hash table.</li> <li>The HashTable class has a private integer array arr of size SIZE, which is initialized to -1 in the constructor. The hash function method takes an integer key and returns the hash value of the key, which is simply the remainder of the key when divided by SIZE.</li> <li>The insert method takes an integer key and uses the hash function to get the index where the key should be inserted.</li> <li>If the index is already occupied by another key, linear probing is used to find the next available index in the array. Linear probing checks the next index in the array until it finds an empty slot or the key itself.</li> <li>If the key is already in the hash table, the method displays a message saying that the element already exists. Otherwise, it inserts the key at the calculated index.</li> <li>The remove method takes an integer key and uses the hash function to get the index where the key is located.</li> <li>If the key is not in the calculated index, linear probing is used to search for the key in the next indices in the array. Once the key is found, it is deleted by setting its value to -2.</li> <li>If the key is not found in the hash table, the method displays a message saying that the element is not found.</li> <li>The display method simply iterates through the array and prints out all non-empty key-value pairs.</li> <li>In the main function, an instance of the HashTable class is created, and several integers are inserted into the hash table using the insert method.</li> <li>Then, the display method is called to show the contents of the hash table. The remove method is called twice, first to remove an element that exists in the hash table and then to remove an element that does not exist.</li> <li>The display method is called after each remove method call to show the updated contents of the hash table.</li> <li>Finally, another integer is inserted into the hash table, and the display method is called again to show the final contents of the hash table.</li> </ul> <p> <strong>Program Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/hashing-data-structure-3.webp" alt="Hashing in Data Structure"> <h2>Applications of Hashing</h2> <p>Hashing has many applications in computer science, including:</p> <ul> <li>Databases: Hashing is used to index and search large databases efficiently.</li> <li>Cryptography: Hash functions are used to generate message digests, which are used to verify the integrity of data and protect against tampering.</li> <li>Caching: Hash tables are used in caching systems to store frequently accessed data and improve performance.</li> <li>Spell checking: Hashing is used in spell checkers to quickly search for words in a dictionary.</li> <li>Network routing: Hashing is used in load balancing and routing algorithms to distribute network traffic across multiple servers.</li> </ul> <h2>Advantages of Hashing:</h2> <ul> <li>Fast Access: Hashing provides constant time access to data, making it faster than other data structures like linked lists and arrays.</li> <li>Efficient Search: Hashing allows for quick search operations, making it an ideal data structure for applications that require frequent search operations.</li> <li>Space-Efficient: Hashing can be more space-efficient than other data structures, as it only requires a fixed amount of memory to store the hash table.</li> </ul> <h2>Limitations of Hashing:</h2> <ul> <li>Hash Collisions: Hashing can produce the same hash value for different keys, leading to hash collisions. To handle collisions, we need to use collision resolution techniques like chaining or open addressing.</li> <li>Hash Function Quality: The quality of the hash function determines the efficiency of the hashing algorithm. A poor-quality hash function can lead to more collisions, reducing the performance of the hashing algorithm.</li> </ul> <h2>Conclusion:</h2> <p>In conclusion, hashing is a widely used technique in a data structure that provides efficient access to data. It involves mapping a large amount of data to a smaller hash table using a hash function, which reduces the amount of time needed to search for specific data elements. The hash function ensures that data is stored in a unique location within the hash table and allows for easy retrieval of data when needed.</p> <p>Hashing has several advantages over other data structure techniques, such as faster retrieval times, efficient use of memory, and reduced collisions due to the use of a good hash function. However, it also has some limitations, including the possibility of hash collisions and the need for a good hash function that can distribute data evenly across the hash table.</p> <p>Overall, hashing is a powerful technique that is used in many applications, including database indexing, spell-checking, and password storage. By using a good hash function and implementing appropriate collision resolution techniques, developers can optimize the performance of their applications and provide users with a seamless experience.</p> <hr></size;>