Design HashMap
Design a HashMap without using any built-in hash table libraries. The HashMap should have the following functions: put(key: number, value: number): void, get(key: number): number, remove(key: number): void. The HashMap should be able to store and retrieve values based on the given key.
Constraints:
- 1 <= key <= 10^6
- 0 <= value <= 10^6
- At most 10^6 operations will be performed
Examples:
Input: ["put", "put", "get", "get", "remove", "get"] [[1, 1], [2, 2], [1], [3], [2], [2]]
Output: [null, null, 1, -1, null, -1]
Explanation: The HashMap is initialized. The put function is used to store the key-value pairs (1, 1) and (2, 2). The get function is used to retrieve the values for keys 1 and 3. The remove function is used to remove the key-value pair (2, 2). Finally, the get function is used again to retrieve the value for key 2, which returns -1 because the key has been removed.
Solutions
Separate Chaining
The solution uses separate chaining to handle collisions. Each bucket is an array of key-value pairs. The put function checks if the key already exists in the bucket and updates the value if it does. If the key does not exist, it adds a new key-value pair to the bucket. The get function checks if the key exists in the bucket and returns the value if it does. If the key does not exist, it returns -1. The remove function checks if the key exists in the bucket and removes the key-value pair if it does.
public
class MyHashMap {
private int size;
private int[][] buckets;
public MyHashMap() {
size = 1000;
buckets = new int[size][];
}
public void put(int key, int value) {
int index = key % size;
if (buckets[index] == null) {
buckets[index] = new int[][] {
{
key, value}
}
;
}
else {
for (int i = 0;
i < buckets[index].length;
i++) {
if (buckets[index][i][0] == key) {
buckets[index][i][1] = value;
return;
}
}
int[][] newBuckets = new int[buckets[index].length + 1][];
System.arraycopy(buckets[index], 0, newBuckets, 0, buckets[index].length);
newBuckets[buckets[index].length] = new int[] {
key, value}
;
buckets[index] = newBuckets;
}
}
public int get(int key) {
int index = key % size;
if (buckets[index] == null) {
return -1;
}
for (int i = 0;
i < buckets[index].length;
i++) {
if (buckets[index][i][0] == key) {
return buckets[index][i][1];
}
}
return -1;
}
public void remove(int key) {
int index = key % size;
if (buckets[index] == null) {
return;
}
for (int i = 0;
i < buckets[index].length;
i++) {
if (buckets[index][i][0] == key) {
int[][] newBuckets = new int[buckets[index].length - 1][];
System.arraycopy(buckets[index], 0, newBuckets, 0, i);
System.arraycopy(buckets[index], i + 1, newBuckets, i, buckets[index].length - i - 1);
buckets[index] = newBuckets;
return;
}
}
}
}Follow-up:
How would you optimize the solution for a large number of operations?
