# Design HashMap
**Difficulty:** EASY
[External](https://leetcode.com/problems/design-hashmap)
Canonical: https://scaleengineer.com/dsa/problems/design-hashmap
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design), [Hash Function](https://scaleengineer.com/dsa/patterns/hash-function)
**Algorithms:** [Consistent Hashing](https://scaleengineer.com/algorithms/consistent-hashing), [LRU Cache](https://scaleengineer.com/algorithms/lru-cache)
**Data structures:** Array, Hash Table, Linked List
**Companies:** [Deutsche Bank](https://scaleengineer.com/companies/deutsche-bank), [Nvidia](https://scaleengineer.com/companies/nvidia), [Palo Alto Networks](https://scaleengineer.com/companies/palo-alto-networks), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Snowflake](https://scaleengineer.com/companies/snowflake), [Two Sigma](https://scaleengineer.com/companies/two-sigma), [Applied Intuition](https://scaleengineer.com/companies/applied-intuition)
---
## Problem
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`.

**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]]

**Constraints:**

* `0 <= key, value <= 106`
* At most `104` calls will be made to `put`, `get`, and `remove`.

# Approaches
## Brute Force using a List of Pairs
This is a straightforward but inefficient approach. We can use a dynamic array (like `ArrayList` in Java) to store the key-value pairs. For each operation (`put`, `get`, `remove`), we would need to iterate through the list to find the relevant key.
**Time:** O(k) for all operations (`put`, `get`, `remove`), where `k` is the number of keys in the HashMap. Each operation requires a linear scan of the list. · **Space:** O(k), where `k` is the number of keys stored in the HashMap. We only store the key-value pairs that are actually inserted.
**Pros:** Simple to implement.; Space-efficient, as it only uses space for the elements inserted.
**Cons:** Very slow. The time complexity for all operations is linear, which is not acceptable for a HashMap implementation, especially with a large number of entries. It will likely result in a 'Time Limit Exceeded' error for larger test cases.
### Explanation
We maintain a list of custom objects or pairs, where each object holds a key and its corresponding value.
- For the `put(key, value)` operation, we first scan the entire list. If we find an entry with the same key, we update its value. If we traverse the whole list without finding the key, we append a new `(key, value)` pair to the end of the list.
- For the `get(key)` operation, we perform a linear scan of the list. If we find an entry with the matching key, we return its value. If the key is not found after checking all entries, we return `-1`.
- For the `remove(key)` operation, we again scan the list. If we find the key, we remove that entry from the list. This might involve shifting subsequent elements if an `ArrayList` is used.

```java
import java.util.ArrayList;
import java.util.List;

class MyHashMap {
    private List<int[]> map;

    public MyHashMap() {
        map = new ArrayList<>();
    }

    public void put(int key, int value) {
        for (int[] pair : map) {
            if (pair[0] == key) {
                pair[1] = value;
                return;
            }
        }
        map.add(new int[]{key, value});
    }

    public int get(int key) {
        for (int[] pair : map) {
            if (pair[0] == key) {
                return pair[1];
            }
        }
        return -1;
    }

    public void remove(int key) {
        for (int i = 0; i < map.size(); i++) {
            if (map.get(i)[0] == key) {
                map.remove(i);
                return;
            }
        }
    }
}
```
### Algorithm
- Initialize an empty list, `map`, to store `(key, value)` pairs.
- **`put(key, value)`**:
  - Iterate through `map`.
  - If an entry with `entry.key == key` exists, update `entry.value = value` and return.
  - If not found, add a new pair `(key, value)` to `map`.
- **`get(key)`**:
  - Iterate through `map`.
  - If an entry with `entry.key == key` exists, return `entry.value`.
  - If the loop finishes, return `-1`.
- **`remove(key)`**:
  - Iterate through `map` with an index.
  - If an entry with `entry.key == key` is found at index `i`, remove the element at index `i` and return.

## Direct Addressing with a Large Array
Given that the keys are non-negative integers within a known range (`0` to `10^6`), we can use a simple array as a direct address table. The key itself serves as the index into the array. This approach trades significant space for constant-time operations.
**Time:** O(1) for `put`, `get`, and `remove`. All operations are constant time as they involve direct array access. · **Space:** O(M), where `M` is the maximum possible value of a key (`10^6 + 1`). This approach pre-allocates memory for all possible keys, regardless of how many are actually used.
**Pros:** Extremely fast with `O(1)` time complexity for all operations.; Very simple to implement.
**Cons:** Highly inefficient in terms of space. It allocates a very large array, which can be wasteful if the number of actual keys is small compared to the range of possible keys. In this problem, we have at most `10^4` keys but a range of `10^6`, so we use `100` times more space than necessary.
### Explanation
We declare an integer array, let's call it `data`, with a size large enough to accommodate the maximum possible key value. Since keys are up to `10^6`, the array size will be `10^6 + 1`.
We need a way to indicate whether a key is present or not. Since the problem states that `get` should return `-1` for a non-existent key and values are non-negative (`0 <= value <= 10^6`), we can use `-1` as a sentinel value. We initialize the entire array with `-1`.
- `put(key, value)`: This operation becomes a simple array assignment: `data[key] = value`.
- `get(key)`: This is a direct lookup: `return data[key]`. If the key was never inserted, the value will be the initial `-1`.
- `remove(key)`: To remove a key, we simply reset the value at that index back to our sentinel value: `data[key] = -1`.

```java
import java.util.Arrays;

class MyHashMap {
    int[] data;

    public MyHashMap() {
        data = new int[1000001];
        // Initialize all values to -1 to indicate that no key is present.
        Arrays.fill(data, -1);
    }

    public void put(int key, int value) {
        data[key] = value;
    }

    public int get(int key) {
        return data[key];
    }

    public void remove(int key) {
        data[key] = -1;
    }
}
```
### Algorithm
- Initialize an integer array `data` of size `10^6 + 1`.
- Fill the entire `data` array with `-1` to act as a sentinel value indicating an empty slot.
- **`put(key, value)`**: Set `data[key] = value`.
- **`get(key)`**: Return `data[key]`.
- **`remove(key)`**: Set `data[key] = -1`.

## Hashing with Separate Chaining
This is the classic and most practical approach to implementing a HashMap. It combines an array with linked lists to handle collisions efficiently, balancing the trade-offs between time and space. This method is known as separate chaining.
**Time:** Average case is `O(1)` for all operations, assuming a good hash function and a reasonable load factor. The load factor `λ` is `k/N` (number of keys / number of buckets). The complexity is more precisely `O(1 + λ)`. In the worst case, where all keys hash to the same bucket, the complexity degrades to `O(k)`. · **Space:** O(N + k), where `N` is the number of buckets and `k` is the number of keys stored. This is efficient as it scales with the number of items stored, plus a fixed overhead for the bucket array.
**Pros:** Provides a good balance between time and space complexity.; Average `O(1)` performance makes it very fast for typical use cases.; Space usage is proportional to the number of elements, making it much more efficient than direct addressing for sparse key sets.
**Cons:** More complex to implement than the other two approaches.; Performance can degrade to `O(k)` in the worst-case scenario of many hash collisions, where `k` is the number of keys.
### Explanation
The core idea is to use a hash function to map a key to an index in an array of 'buckets'. Since multiple keys can map to the same index (a 'collision'), each bucket stores a data structure to hold all the key-value pairs that hash to it. A linked list is a common choice for this.
- We start by creating an array of a fixed size. This size should ideally be a prime number to help distribute keys more evenly. A size of around `10000` is reasonable given the constraints. Let's choose `10007`. This array will store the heads of linked lists.
- The hash function will be `key % array_size`.
- For `put(key, value)`: Calculate the bucket index, then traverse the linked list at that index. If the key exists, update the value. Otherwise, add a new node to the front of the list.
- For `get(key)`: Calculate the bucket index, then traverse the list to find the key and return its value. If not found, return `-1`.
- For `remove(key)`: Calculate the bucket index, find the node in the list, and remove it by adjusting the `next` pointers.

```java
class MyHashMap {
    class ListNode {
        int key, val;
        ListNode next;

        ListNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    final int SIZE = 10007; // A prime number
    ListNode[] buckets;

    public MyHashMap() {
        buckets = new ListNode[SIZE];
    }

    private int hash(int key) {
        return key % SIZE;
    }

    public void put(int key, int value) {
        int index = hash(key);
        ListNode head = buckets[index];
        ListNode current = head;
        while (current != null) {
            if (current.key == key) {
                current.val = value;
                return;
            }
            current = current.next;
        }
        ListNode newNode = new ListNode(key, value);
        newNode.next = head;
        buckets[index] = newNode;
    }

    public int get(int key) {
        int index = hash(key);
        ListNode current = buckets[index];
        while (current != null) {
            if (current.key == key) {
                return current.val;
            }
            current = current.next;
        }
        return -1;
    }

    public void remove(int key) {
        int index = hash(key);
        ListNode head = buckets[index];
        if (head == null) return;

        if (head.key == key) {
            buckets[index] = head.next;
            return;
        }

        ListNode prev = head;
        ListNode current = head.next;
        while (current != null) {
            if (current.key == key) {
                prev.next = current.next;
                return;
            }
            prev = current;
            current = current.next;
        }
    }
}
```
### Algorithm
- Define a `ListNode` class to store `key`, `value`, and a `next` pointer.
- Initialize an array of `ListNode` called `buckets` of a chosen prime size (e.g., `10007`).
- Define a hash function, `hash(key) = key % SIZE`.
- **`put(key, value)`**:
  - Get `index = hash(key)`.
  - Traverse the linked list at `buckets[index]`.
  - If a node with the same key is found, update its value and return.
  - Otherwise, create a new `ListNode(key, value)` and add it to the front of the list at `buckets[index]`.
- **`get(key)`**:
  - Get `index = hash(key)`.
  - Traverse the linked list at `buckets[index]`.
  - If a node with the same key is found, return its value.
  - If the list is fully traversed, return `-1`.
- **`remove(key)`**:
  - Get `index = hash(key)`.
  - Find the node with the given key in the list at `buckets[index]`, keeping track of the previous node.
  - Once found, update the `next` pointer of the previous node to skip the current node. Handle the case where the node to be removed is the head of the list separately.

# Solutions
### Java

```java
class MyHashMap { private int [] data = new int [ 1000001 ]; public MyHashMap () { Arrays . fill ( data , - 1 ); } public void put ( int key , int value ) { data [ key ] = value ; } public int get ( int key ) { return data [ key ]; } public void remove ( int key ) { data [ key ] = - 1 ; } } /** * Your MyHashMap object will be instantiated and called as such: * MyHashMap obj = new MyHashMap(); * obj.put(key,value); * int param_2 = obj.get(key); * obj.remove(key); */
```

### CPP

```cpp
class MyHashMap { public: int data [ 1000001 ]; MyHashMap () { memset ( data , - 1 , sizeof data ); } void put ( int key , int value ) { data [ key ] = value ; } int get ( int key ) { return data [ key ]; } void remove ( int key ) { data [ key ] = - 1 ; } }; /** * Your MyHashMap object will be instantiated and called as such: * MyHashMap* obj = new MyHashMap(); * obj->put(key,value); * int param_2 = obj->get(key); * obj->remove(key); */
```

### Python

```python
class MyHashMap : def __init__ ( self ): self . data = [ - 1 ] * 1000001 def put ( self , key : int , value : int ) -> None : self . data [ key ] = value def get ( self , key : int ) -> int : return self . data [ key ] def remove ( self , key : int ) -> None : self . data [ key ] = - 1 # Your MyHashMap object will be instantiated and called as such: # obj = MyHashMap() # obj.put(key,value) # param_2 = obj.get(key) # obj.remove(key) ############# class MyHashMap : # hash to bucket def __init__ ( self ): """ Initialize your data structure here. """ self . size = 1000 self . buckets = [[] for _ in range ( self . size )] def _hash ( self , key : int ) -> int : """ Generate a hash for a given key. """ return key % self . size def put ( self , key : int , value : int ) -> None : """ Value will always be non-negative. """ hash_key = self . _hash ( key ) for i , ( k , v ) in enumerate ( self . buckets [ hash_key ]): if k == key : self . buckets [ hash_key ][ i ] = ( key , value ) return self . buckets [ hash_key ]. append (( key , value )) def get ( self , key : int ) -> int : """ Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key. """ hash_key = self . _hash ( key ) for k , v in self . buckets [ hash_key ]: if k == key : return v return - 1 def remove ( self , key : int ) -> None : """ Removes the mapping of the specified value key if this map contains a mapping for the key. """ hash_key = self . _hash ( key ) for i , ( k , v ) in enumerate ( self . buckets [ hash_key ]): if k == key : del self . buckets [ hash_key ][ i ] return ############### class MyHashMap : # open addressing with linear probing def __init__ ( self ): self . capacity = 10000 self . data = [ None ] * self . capacity self . DELETED = ( None , None ) # Marker for deleted entries def _hash ( self , key ): return key % self . capacity def put ( self , key : int , value : int ) -> None : idx = self . _hash ( key ) while self . data [ idx ] not in ( None , self . DELETED , key ): idx = ( idx + 1 ) % self . capacity self . data [ idx ] = ( key , value ) def get ( self , key : int ) -> int : idx , found_key = self . _find ( key ) if found_key : return self . data [ idx ][ 1 ] return - 1 def remove ( self , key : int ) -> None : idx , found_key = self . _find ( key ) if found_key : self . data [ idx ] = self . DELETED def _find ( self , key ): original_idx = idx = self . _hash ( key ) while self . data [ idx ] is not None : if self . data [ idx ] != self . DELETED and self . data [ idx ][ 0 ] == key : return idx , True idx = ( idx + 1 ) % self . capacity if idx == original_idx : # Came full circle break return original_idx , False
```