Hash map is an associative data structure which implements an associative array data type. The concept of hash map is quite simple. Hash map stores data as a (key,value) pair. For instance, in (“Jason”,”HKU”), “Jason” is the key and “HKU” is the value.
When the hash map takes a key-value input, hash function is used to convert the key to the appropriate hash code. There are many hash functions but in this particular case, we will be using the hash function where you add up all the characters(int) and perform modular operation by the hash map’s size. So if the size of hash table is 10, then all the keys will be converted into one of the nine baskets(indexed 0–9).
As you might’ve noticed, this might cause a problem. What if two keys have the same hash code? For example, “Jason” and “Johnl” both have 507 as the sum of their characters. Then, their hash code would be 7. This can be resolved by hashing collision handling methods: open addressing(linear probing, quadratic probing, etc), closed addressing(separate chaining).
Open Addressing is a hashing collision handling method which uses probings such as linear probing, quadratic probing or double hashing to avoid collision. In general, hash code is first calculated and if iterate using probing methods until we finds an empty slot for the input. This might be sensitive due to the infinite cycle thus specific probing functions are used.
Closed Addressing(separate chaining) generally uses linked list to handle with the hashing collisions. Whenever there are some data for the same hash code, push the data back to the end of linked list. In this particular case, we will be implementing hash map using separate chaining.
Advantages of Hash Map
- Fast lookup (Best case: O(1), Worst case: O(n))
- Fast Insertion / Deletion
- Synchronization
Disadvantages of hash Map
- Collision is virtually unavoidable
- Not cache-friendly
- Unordered
Time Complexity
- Insert: Best-O(1), Worst-O(n)
- Lookup: Best-O(1), Worst-O(n)
- Delete: Best-O(1), Worst-O(n)
