How to Demonstrate Hashing and It’s Application to Beginner using Structure and Array in C: The Easy Way-Part-4 (Chaining)
This is fourth and final part of articles series on hashing and hash collision, previous three parts are prerequisites to understand this part clearly and work on earlier concepts and those can be found at below links.
Hashing: Part1 Application of Hashing: Demo Part2 Hash Collision: Part3
In part 3, Hash collision and various methods under open addressing to resolve collision were discussed. In this article Collision Resolution by Chaining is discussed in details with demo examples.
Chaining is very simple method of hash resolution, in this the colliding keys are stored as linked list and hash value is serve as index of hash table. In simple term, all the keys which having same hash value are stored as a linked list and root/head of the linked list is stored based on the hash value in the hash table. So, in case of collision a new node is inserted to the linked list for which head/ root value is taken from hash table based upon the hash value.
So basically, hash table can be seen as an array of root of many linked list and all key with same hash value go into same linked list. Continuing with our previous demo application, in case of multiplication hashing with m=11, roll number 136001 and 136009 both results in same hash value 2. Different collision resolution methods stored the record for 136009 different but with different index than the hash value. Now, in chaining both these record with create a linked list and the head of this link list will be stored at index 2 of hash table which is based on hash value i.e. 2.
Implementation
The implementation of chaining method is very similar to the single linked list. The following are two examples, first example demonstrate the use of chaining to store the records and then printing them all and second example demonstrate the searching for a particular record based on the key.
Storing record
To store a record using chaining, first the student structure is changed i.e. at line 25 a pointer variable of type student structure is added which will used to hold the address of other records which have same hashed value and hence collision. A node is initialized with all the user’s given data and then hash table is checked if on the calculated hash value any record is previously stored then the that array index won’t be equal to default value i.e. 0 which indicate a collision of hash value is occurred and hence need to add record to the previous existing record (lines 57–68) else if index value is zero then the new record will be stored with the hash value and it simple changing the *next pointer of student structure (line 70–74).
Printing all stored records
During printing of records, care should be taken for index having only single record (no collision), or no records (free location) or have more than one records (collision). Line 83–97 perform all these tasks, lines 86–89 take care of single or no record and rest of code print the linked chain.
Below is the second demo example in which records are stored and search using multiplication hashing and chaining is used to resolve the collision.
Searching
Searching is also very similar to printing all records. The search key i.e. roll number is taken from user and hash value is calculated. Then record stored at the location equal to the hash value is access and the search key is compare, if it matches then the record is display else the case is of collision and then sequential search on the linked list is started i.e. every record is access using the address stored in *next pointer and the key value is compare if match found, record is display and the search break out from the loop (lines 100–110).
With this series on Hashing is come to an end. Please write for any suggestions or improvments.
