Design a HashMap
Author: Mohammad J Iqbal
Follow Mohammad J Iqbal on LinkedIn
HashMap: A HashMap is a data structure that is used to store and retrieve values based on keys.
Constraints and assumptions
Design a HashMap class named MyHashMap and implement the below methods:
class MyHashMap {
public MyHashMap() {
}
/*
inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
*/
public void put(int key, int value) {
}
/*
returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
*/
public int get(int key) {
}
/*
removes the key and its corresponding value if the map contains the mapping for the key.
*/
public void remove(int key) {
}
}
If watching the topic on video more convenient to you, you can watch it on YouTube below:
HashMap Internals:
Before we jump on the HashMap Design, let’s discuss some important terms related to HashMap
-
bucket: For data storage, we can use array, each element of the array is called bucket.
-
hashing: an algorithm to map object data to some representative integer value. The hash function is applied to the key object to calculate the index of the bucket in order to store and retrieve any key-value pair.
-
capacity: Capacity is the number of buckets in the HashMap. The initial capacity is the capacity at the time the Map is created. Finally, the default initial capacity of the HashMap is 16
-
Loadfactor: The load factor is the measure that decides when to increase the capacity of the Map. The default load factor is 75% of the capacity.
-
threshold: approximately the product of current capacity and load factor
-
rehashing: Rehashing is the process of re-calculating the hash code of already stored entries
-
collision: A collision occurs when a hash function returns the same bucket location for two different keys.
Prior to Java 8, HashMap in Java handles collision by using LinkedList to store map entries.
If a key ends up in the same bucket where another entry already exists, it’s added at the head of the LinkedList. In the worst case, this will increase complexity to O(n).
To avoid this issue, Java 8 and later versions use a balanced tree (also called a red-black tree) instead of a LinkedList to store collided entries.
This improves the worst-case performance of HashMap from O(n) to O(log n).
Questions:
-
For collision resolution, can we use chaining?
Yes
-
Do we have to worry about load factors, capacity and rehashing?
No
-
Do we need to handle thread safety?
NO
Constraints:
0 <= key, value <= 106 At most 104 calls will be made to put, get, and remove.
Example 1:
Input:
[“MyHashMap”, “put”, “put”, “get”, “get”, “put”, “get”, “remove”, “get”]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
Output: [null, null, null, 1, -1, null, 1, null, -1]
Explanation:
MyHashMap myHashMap = new MyHashMap(); myHashMap.put(1, 1); // The map is now [[1,1]]
myHashMap.put(2, 2); // The map is now [[1,1], [2,2]]
myHashMap.get(1); // return 1, The map is now [[1,1], [2,2]]
myHashMap.get(3); // return -1 (i.e., not found), The map is now [[1,1], [2,2]]
myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value)
myHashMap.get(2); // return 1, The map is now [[1,1], [2,1]]
myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]]
myHashMap.get(2); // return -1 (i.e., not found), The map is now [[1,1]]
Implementation of HashMap:
package com.spsoft.hashmap;
public class MyHashMap {
private class Node {
int key;
int value;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private static final int SIZE = 10001;
private Node[] bucket;
public MyHashMap() {
bucket = new Node[SIZE];
}
/**
* Adds a key-value pair to the HashMap or updates the value if the key already exists.
*/
public void put(int key, int value) {
int index = hash(key);
Node node = bucket[index];
if (node == null) {
bucket[index] = new Node(key, value);
return;
}
Node prev = null;
while (node != null) {
if (node.key == key) {
node.value = value;
return;
}
prev = node;
node = node.next;
}
prev.next = new Node(key, value);
}
/**
* Retrieves the value associated with the given key.
* @return the value if found, or -1 if the key does not exist.
*/
public int get(int key) {
int index = hash(key);
Node node = bucket[index];
while (node != null) {
if (node.key == key) {
return node.value;
}
node = node.next;
}
return -1;
}
/**
* Removes the key-value pair from the HashMap.
*/
public void remove(int key) {
int index = hash(key);
Node node = bucket[index];
Node prev = null;
while (node != null) {
if (node.key == key) {
if (prev != null) {
prev.next = node.next;
} else {
bucket[index] = node.next;
}
return;
}
prev = node;
node = node.next;
}
}
/**
* Computes the hash index for a given key.
* @param key the key to be hashed.
* @return the computed hash index.
*/
private int hash(int key) {
return Integer.hashCode(key) % SIZE;
}
public static void main(String[] args) {
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // The map is now [[1,1]]
myHashMap.put(2, 2); // The map is now [[1,1], [2,2]]
System.out.println(myHashMap.get(1)); // return 1
System.out.println(myHashMap.get(3)); // return -1 (not found)
myHashMap.put(2, 1); // update the existing value
System.out.println(myHashMap.get(2)); // return 1
myHashMap.remove(2); // remove the mapping for 2
System.out.println(myHashMap.get(2)); // return -1 (not found)
}
}