How to Demonstrate Hashing and It’s Application to Beginner using Structure and Array in C: The Easy Way-Part-2 (Application of Hashing)
This is the second part of a multi-parts hashing article. The first part is prerequisite to follow this and further article in the series. First part can be read through below link.
The basic understanding of hashing and learning few hashing techniques through example and implementation, now the time is to answer and demonstrate the usage and benefits hashing. So, here is the demo problem.
A user want to store students' information such as name, roll and marks, and on request search a student’s details and display to user. It is very simple task to perform and can be implemented with ease using C’s structure and array. Below is simple implementation.
Implementation: Students’ information storing and searching
Using loop the aforementioned program will accept all 16 students (MAX value is 16) information and will store them sequentially using array (arr_student[MAX]). From line 45–56 will provide the search functionality where a user will asked to give a roll number to search through array and show the details of that student. Below is a digram to show the data arrangement in memory using above program.
This program will work fine with few students details but as number of students records increase (which is a real time situation) searching will become time-consuming (O(N) ) due to linear search. Now, to reduce search time hashing is suitable and will bring search to O(1).
To adopt the hashing and harness it’s benefits the aforementioned program need to modify during storing of the infomation. In previous example, the student’s record are stored sequentially in array but now with hashing student’s will be stored in a non-linear way i.e. the array index (hash table ) to store a student’s record will be decided by the hash function using hash value. During search the same hash function will be use and the resulting hash value will be use to access the record directly from the array (hash table). Below is the modified program with hashing.
Implementation: Storing and Searching Student’s information using Hashing
In the aforementioned program, multiplication hashing is used (discussed in part 1) and only 10 students’s information is being store for demo purpose. Lines 16–19 have the hashing function declartion and at line 42 the hash function is called and the resulting hash value (arrayIndex) is used to decide the array index where to store the record. Lines 60–66 have search function where a student’s roll number is asked and then again hash value is calculated (line 63) the hashvalue is then used to display the student’s details. One can notice here that there is no loop to go through the array sequentially and compare the searching roll number with all other, this is due to hashing and so the search time is O(1) using hashing. Below is the hash value for each roll (136001 to 136010) and the arrangment of records based on hash value.
Now, one can observed that students information are not stored as the order of insertion but based on the hash value of key i.e. the roll number in this case. During access/ or search only hash value have to cacluated and can be use to access a student’s record directly.
Note: The red highlighted section in the Figure 2 and Figure 3 is hash collision which will be discussed in next article as below( part-3).
