## Algorithm

Problem Name: 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`.

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

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class MyHashMap {

/** Initialize your data structure here. */
Integer[][] map;
int NUM_OF_BUCKETS = 1000;
int BUCKET_SIZE = 1000;
public MyHashMap() {
map = new Integer[NUM_OF_BUCKETS][BUCKET_SIZE];
}

/** value will always be non-negative. */
public void put(int key, int value) {
Integer[] bucket = getBucket(key);
int keyHash = getKeyHash(key);
bucket[keyHash] = 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) {
Integer[] bucket = getBucket(key);
int keyHash = getKeyHash(key);
return bucket[keyHash] == null ? -1 : bucket[keyHash];
}

/** Removes the mapping of the specified value key if this map contains a mapping for the key */
public void remove(int key) {
Integer[] bucket = getBucket(key);
int keyHash = getKeyHash(key);
bucket[keyHash] = null;
}

private Integer[] getBucket(int key) {
int bucketIdx = key / BUCKET_SIZE;
return map[bucketIdx];
}

private Integer getKeyHash(int key) {
return key % BUCKET_SIZE;
}
}
``````
Copy The Code &

Input

cmd
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"] [[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]

Output

cmd
[null, null, null, 1, -1, null, 1, null, -1]

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const MyHashMap = function() {
this.h = {}
};

MyHashMap.prototype.put = function(key, value) {
this.h[key] = value
};

MyHashMap.prototype.get = function(key) {
return {}.hasOwnProperty.call(this.h, key) ? this.h[key] : -1
};

MyHashMap.prototype.remove = function(key) {
delete this.h[key]
};
``````
Copy The Code &

Input

cmd
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"] [[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]

Output

cmd
[null, null, null, 1, -1, null, 1, null, -1]

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class MyHashMap:

def __init__(self):
self.arr = [-1] * 1000001

def put(self, key, value):
self.arr[key] = value

def get(self, key):
return self.arr[key]

def remove(self, key):
self.arr[key] = -1
``````
Copy The Code &

Input

cmd
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"] [[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]

Output

cmd
[null, null, null, 1, -1, null, 1, null, -1]

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _0706_DesignHashmap
{
private const int size = 10000;
private int[] keyTable;
private int[] valTable;

/** Initialize your data structure here. */
public _0706_DesignHashmap()
{
keyTable = new int[size];
valTable = new int[size];
for (int i = 0; i < size; i++)
{
keyTable[i] = -1;
valTable[i] = -1;
}
}

/** value will always be non-negative. */
public void Put(int key, int value)
{
var i = Hash(key);
while (keyTable[i] != -1 && keyTable[i] != key)
{
if (i == size - 1)
i = 0;
else
i++;
}

keyTable[i] = key;
valTable[i] = 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)
{
var i = Hash(key);
while (keyTable[i] != -1 && keyTable[i] != key)
{
if (i == size - 1)
i = 0;
else
i++;
}

return valTable[i];
}

/** Removes the mapping of the specified value key if this map contains a mapping for the key */
public void Remove(int key)
{
var i = Hash(key);
while (keyTable[i] != -1 && keyTable[i] != key)
{
if (i == size - 1)
i = 0;
else
i++;
}

// tombstone is -2.
keyTable[i] = -2;
valTable[i] = -2;
}

private int Hash(int key)
{
return key % size;
}
}
}
``````
Copy The Code &

Input

cmd
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"] [[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]

Output

cmd
[null, null, null, 1, -1, null, 1, null, -1]