Hashing and hash code collision

Hashing is all about to optimize or speed up the searching. We can always have an array to store the values and traverse the whole array to search a given value in that collection. That will result in O(n2) complexity. Even if the array is sorted, binary search will result the complexity of O(log n).

Imagine if we know the index of the location where our value lies , we can reduce our complexity by O(1), which remains constant. This technique is called as hashing and the function which will give us the index of location is called as hash function. 

Now , The responsibility of the function is

              1.  To return a number (hash code) for an object,

              2. Two equal object must have same hash code

              3. Two unequal object may have same or different hash code.

Keeping in mind the real time larger set of data, the capability of hash function will always be challenged. What happen when two different objects by equal method have same hash code. This is what we call is hash collision.

How to resolve hash collision?

1. Separate chaining collision resolution :- Put the subsequent values having same hash code in same location . Put them into a linked list. Now hash table will be a array of linked lists in which same hash code values will be listed into linked list. If all values collide at same index , that is a poor hash function and will result into poor load factor.
2. Linear Probing collision resolution :-  Insert the subsequent value into next slot . If i is the index , then insert the value at i+1 location or i+2 depends on availability.

Share on Google Plus

About chetan

Howsstuff