Hashing is a technique for storing and retrieving information faster. Hashing can give a complexity of O(1) in best case; however the worst case is still O(n).
COMPONENTS OF HASHING
Important components of hashing are:
- Hash buckets
- Hashing functions
BASIC HASHING EXPLAINED
- There will be storage locations called buckets.
- Your hash function will generate a bucket number for every object.
- When you want to store any element, you use the hash function to get the bucket number and store the element in that bucket.
- When you need the element back, you use the same hash function to get the bucket number of your object and then get the object from that bucket.
Note: If a bucket contain only one element, you can retrieve in O(1) time, but if one bucket contain all elements, you might need O(n) complexity in worst case.
IMPLEMENTING USING ARRAYS
You may implement a hashing data structure using arrays. Each array location can be considered as a bucket. The value generated by your hash function can be mapped to one of array location using a simple mod function.
Even though the ideal hashing algorithm will generate a different bucket for every object, in practical scenarios, more than one object will have the same hash code. Thus more than one element will be mapped to a single bucket. Mapping more than one element to a single bucket is called as collision.
If you are implementing using arrays, this means that, more than one element needs to be stored in one array location. However this is not possible in most programming languages like Java.
Collision resolution techniques
We can have a linked list of elements in each array location. This is one of the popular collision resolution techniques.
Based on the hash code generated by the hash function, you can find the array location (or bucket) and then traverse through the associated linked list and place the elements to the end of the linked list. You may also add elements to the beginning of the linked list for faster O(1) insertion.
When you want to retrieve elements, you can use the same hash function to get the array location, then traverse through the associated linked list to find the element.
Note that even if you have collisions, this is better than using a linked list alone, as now you will need to only search on a subset of elements and not the complete set of elements.
HASHING IN JAVA
- In earlier Java versions, hashing is implemented (in case of HashMap) using arrays and linked list roughly as explained above.
- Java uses Object class’s hashCode method to generate the hashcode and uses it to find the array location, and then use Object class’s equals method to find the right object in the bucket (the associated linked list).
Find out how hash maps are implemented in your programming language of choice (if it has one).