Hash map, also known as hash table, is a fundamental and powerful data structure to save and retrieve an item in constant time.
In reality at work, an engineer should never write their own hash map, due to the fact that a good hash function is non-trivial to derive. But during an interview, it is good to know the simplest toy implementation of a hash map.
A good practice example can be found at leetcode.com: 706. Design HashMap
Design a HashMap without using any built-in hash table libraries.Implement the MyHashMap class:
MyHashMap() initializes the object with an empty map.void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.
For a hash map implementation, the underlying storage is an array and there are three critical components to consider:
- Hash function
- Load factor
- Collision resolution
Hash Function
This is a deterministic mapping, which converts the key of an item into an index within the bound of the underlying array. For a toy implementation, modulo of the array size is a convenient choice. But modulo can not be used for production strength, because often the input keys are not evenly distributed which leads to very high collision rate.
Load Factor
The load factor should be at about 0.5 to avoid too much collisions, which means the total number of items stored should be about half the size of the array. This implies dynamic resizing of the underlying array. A good toy practice is to double the array size if the load factor reaches 0.5.
Collision resolution
Two common solutions: Separate chaining and open addressing.
In the example the array size is 7, and the three items 38, 24 and 59 have a collision hashing to the same index because 38%7 == 24%7 == 59%7 == 3
When different items hash to the same index, separate chaining uses a linked list to store all the items, while open addressing does a linear probe and move to the next index until an empty slot is found.
Sample code for open addressing
And the implementation with separate chaining is left as an exercise to the reader.
Q.E.D.
References
- https://en.wikipedia.org/wiki/Hash_table
- https://leetcode.com/problems/design-hashmap/
- https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-7-hashing-hash-functions
- https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-8-universal-hashing-perfect-hashing/
