Arrays - 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.

Input: operations = ["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
values = [[], [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]]

Constraints:

0 <= key, value <= 10⁶
At most 10⁴ calls will be made to put, get, and remove.

Solution 1 - Using an array of LinkedLists

This is similar to Design HashSet solution, in this approach, we will use an array of LinkedLists to store elements, we will initialize the array with some initial size, in below implementation we are initializing array with 10000, and the reason we are initializing array with this size is just to have more distribution of elements instead of skewing many element under same index.

In order to find the index where to insert a given key, we will do a modular operation on the key value with array length, this will ensure that we will never got out of bounds of array. int hashIndex = key % array.length;

Implementation steps:

Constructor: we will initialize array elements with empty LinkedList, so that we don't need to do null checks later.
put(int key, int value): we will get the index using key % array.length, then check if the key already in the LinkedList at that index or not, if it does not contain the key, then add a new Entry to the linked list, it if exists then update the value.
get(int key): we will get the index using key % array.length, then loop through LinkedList elements at that index, and if any key matches with the key supplied, then return the corresponding value, return -1 otherwise.
remove(int key): we will get the index using key % array.length, then remove the entry with the key from the LinkedList at that index.

import java.util.LinkedList; public class MyHashMap { LinkedList<Entry>[] map = new LinkedList[10000]; static class Entry { int key; int value; public Entry(int key, int value) { this.key = key; this.value = value; } } public MyHashMap() { for(int i=0; i<map.length; i++) { map[i] = new LinkedList<>(); } } // If key exists, update the value, otherwise add a new entry public void put(int key, int value) { int hashIndex = key % map.length; LinkedList<Entry> list = map[hashIndex]; for(Entry entry: list) { if(entry.key == key) { entry.value = value; return; } } list.add(new Entry(key, value)); } public int get(int key) { int hashIndex = key % map.length; LinkedList<Entry> list = map[hashIndex]; for(Entry entry: list) { if(entry.key == key) { return entry.value; } } return -1; } public void remove(int key) { int hashIndex = key % map.length; LinkedList<Entry> list = map[hashIndex]; for(Entry entry: list) { if (entry.key == key) { list.remove(entry); return; } } } 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, The map is now [[1,1], [2,2]] System.out.println(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) System.out.println(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]] System.out.println(myHashMap.get(2)); // return -1 (i.e., not found), The map is now [[1,1]] } }

Complexity Analysis:

Time complexity: All opeeration runs in O(1) time, add operation runs in constant time, since we are looking up element using an index and then adding element to the tail of a LinkedList, both remove and contains also runs in constant average time, when you look at the maximum key as per the problem will be 10⁶ and our array size is 10⁴, so even if some of the numbers are skewed at one index, it is still going to be a constant number.
Space complexity: O(1) since we are storing elements into an array of linked lists.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: