Hashing is an efficient method to store and retrieve elements.
It’s exactly same as index page of a book. In index page, every topic is associated with a page number. If we want to look some topic, we can directly get the page number from the index.
Likewise, in hashing every value will be associated with a key. Using this key, we can point out the element directly.
Let’s discuss hashing with modulo method.
How to calculate the hash key?
Let's take hash table size as 7.
size = 7
Formula to calculate key is,
key = element % size
If we take modulo of number with N, the remainder will always be 0 to N - 1.
Exactly array index also starts from 0 and ends with index N -1. So we can easily store elements in array index.
Initialize the Hash Bucket
Before inserting elements into array. Let’s make array default value as -1.
-1 indicates element not present or the particular index is available to insert.
Inserting elements in the hash table
Searching elements from the hash table
Deleting an element from the hash table
Here, we are not going to remove the element.
We just mark the index as -1. It is indirectly delete the element from array.
What is collision in hashing?
What if we insert an element say 15 to existing hash table?
Insert : 15
Key = element % key
Key = 15 % 7
Key = 1
But already arr has element 8 !
Here, two or more different elements pointing to the same index under modulo size. This is called collision.
Hash table implementation in c using arrays
We didn't implement any collision avoidance technique in the above code.
We will discuss collision avoidance in the next tutorials.
Collision AvoidanceCollision Avoidance using Linear Probing
Collision Avoidance using Separate Chaining