HashMap is a data structure that maps key to value. The basic operations are put, get, remove, contains.
The pointer to the values are stored in an array/list. The key's hash value is used as the index of the array. Since keys can have the same hash value (collision), the array value is actually the header node of a linked list. Whenever a new key/value pair is inserted, a new node is added to the tail of the linked list. The implementation of get, contains and remove are similar. For example, removing a key/value pair can be implemented by calculating the hash code of the key, then use the hash code as index to find the header node in the array, then traversal the linked list until finding the matching node, then remove the node from the linked list.
 | |
|
The primary data structure is a List of header nodes LNode, LNode has two fields: the value and a pointer to next LNode, the value of LNode has type of Tuple. Tuple class contains 2 fields map's key and map's value.
private List<LNode<Tuple>> store = new ArrayList<>();
When we pass in a key in map.get(Key)
The index of the List is calculated as
Key.hasCode() % maxSize
this int is used to retrieve the value in the List.
The value corresponding to that hashCode calculated index is a linked list's header node.
Through that header, we can traversal the linked list, find the LNode whose value.key == key, then we can deal with this target LNode, eg. change its value.value = value, remove this LNode, return its value.value.
Notice each of the following step takes constant time:
- calculate hash value of the key
- retrieve head node with hash value as index from list
- traversal a linked list with finite length (assuming hash code collision is rare)
- check linked list node value
- add or remove a linked list node
As a result put, get, remove, contains all have time complexity O(1).
In order to implement a HashMap with size N, we need at most N list elements to store headers and N linked list nodes to store the key-value pairs. The space complexity is O(N).
Sample code:
HashMapImpl.java
