Collision
No matter what the hash function, there is the Possibility that two different keys could resolve to the same hash address. This situation is known as a collision
.When this situation occur, there are two simple methods to t1–1.’s problem solve.
chaining
A chain is simply a linked list of all the elements with the same hash key. The hash table slots will no longer hold a table element (key). They will now hold the address of a table element
h(K)= key% table slots e.g., The following keys to be hashed
36, 18, 72, 43, 6, 10 , 5, 15
There are 8 slots in the hash table. So, first of all we have to calculate the hash index of each key.
36 % 8 = 4
18 % 8 = 2
72 % 8 = 0
43 % 8 = 3
6 % 8 = 6
10 % 8 = 2
5 % 8 = 5
15 % 8 = 7
Hashing with Linear Probing
When using a linear probing method the will be stored in the next available slot in the table, assuming that the is not already full. This is implemented via a linear searching for an empty slot, from the point of collision. If the end of table is reached during the linear search, the search will wrap around to the beginning of the table and continue from there.
Key Points
- If an empty slot is not found before reaching the point of collision, the table is
full.
- In chaining, we put all the elements, which to the same slot, in a linked list.
e.g., suppose the keys to be inserted or hashed are as follows
36,18, 72, /13, 6, 10, 5,15
and there are 8 slots in hash table.
Now, we have to find out the hash address of keys.
36 %8 = 4 inserted
18 % 8 = 2 inserted
72 % 8 = 0 inserted
43 % 8 = 3 inserted
6 % 8 = 6 inserted
10 % 8 = 2 problem is here because 2nd place is
already full
5 % 8 = 5
15 % 8 = 7 <—
So, when the hash index, what we get through the hash function is already full, then search the next empty slot. So, for key 10, 2nd index is already full, then search the 3rd, it is also full, then search the 4th, it is also full, the search 5th index it is empty, then fill with key 10.