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 thekeyalready exists in the map, update the correspondingvalue.int get(int key)returns thevalueto which the specifiedkeyis mapped, or-1if this map contains no mapping for thekey.void remove(key)removes thekeyand its correspondingvalueif the map contains the mapping for thekey.
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
104calls will be made toput,get, andremove.
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;
}
}
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]
#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]
};
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]
#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
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]
#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;
}
}
}
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]