Solution For Design Hashmap
Problem Statement:
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.
Solution:
To solve this problem, we can use an array of a fixed size to store the key-value pairs. We can create an array of size 1000001, which is sufficiently large to store all the possible keys from 0 to 1000000. We can then use the key as the index in the array, and the corresponding value as the value stored at that index.
To handle collisions, we can use an array of linked lists. Each index in the array of key-value pairs will either be null or a reference to a linked list containing all the key-value pairs that hash to that index.
To insert a new key-value pair, we can first compute the hash code of the key by taking the modulus of the key with the size of the array. We can then add the key-value pair to the linked list at the corresponding index in the array of linked lists.
To get the value corresponding to a key, we can first compute the hash code of the key and then search for the key in the linked list at the corresponding index. If we find the key, we can return the corresponding value. Otherwise, we return -1.
To remove a key-value pair, we can first compute the hash code of the key and then search for the key in the linked list at the corresponding index. If we find the key, we can remove the corresponding key-value pair from the linked list. Otherwise, we do nothing.
Code:
“`
class MyHashMap {
private final int SIZE = 1000001;
private List<Node>[] map;
class Node {
int key;
int value;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
public MyHashMap() {
map = new ArrayList[SIZE];
}
public void put(int key, int value) {
int index = key % SIZE;
if (map[index] == null) {
map[index] = new ArrayList<Node>();
}
for (Node node : map[index]) {
if (node.key == key) {
node.value = value;
return;
}
}
map[index].add(new Node(key, value));
}
public int get(int key) {
int index = key % SIZE;
if (map[index] != null) {
for (Node node : map[index]) {
if (node.key == key) {
return node.value;
}
}
}
return -1;
}
public void remove(int key) {
int index = key % SIZE;
if (map[index] != null) {
for (Iterator<Node> it = map[index].iterator(); it.hasNext();) {
Node node = it.next();
if (node.key == key) {
it.remove();
return;
}
}
}
}
}
“`
Step by Step Implementation For Design Hashmap
class MyHashMap {
private List keys;
private List values;
/** Initialize your data structure here. */
public MyHashMap() {
keys = new ArrayList();
values = new ArrayList();
}
/** value will always be non-negative. */
public void put(int key, int value) {
for(int i = 0; i < keys.size(); i++) {
if(keys.get(i) == key) {
values.set(i, value);
return;
}
}
keys.add(key);
values.add(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) {
for(int i = 0; i < keys.size(); i++) {
if(keys.get(i) == key) {
return values.get(i);
}
}
return -1;
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
public void remove(int key) {
for(int i = 0; i < keys.size(); i++) {
if(keys.get(i) == key) {
keys.remove(i);
values.remove(i);
return;
}
}
}
}
/**
* 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);
*/ class MyHashMap:
def __init__(self):
"""
Initialize your data structure here.
"""
self.size = 1000
self.map = [[] for _ in range(self.size)]
def put(self, key: int, value: int) -> None:
"""
value will always be non-negative.
"""
hash_key = key % self.size
for i in range(len(self.map[hash_key])):
if self.map[hash_key][i][0] == key:
self.map[hash_key][i][1] = value
return
self.map[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 = key % self.size
for i in range(len(self.map[hash_key])):
if self.map[hash_key][i][0] == key:
return self.map[hash_key][i][1]
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 = key % self.size
for i in range(len(self.map[hash_key])):
if self.map[hash_key][i][0] == key:
del self.map[hash_key][i]
return/**
* Initialize your data structure here.
*/
var MyHashMap = function() {
this.map = {};
};
/**
* value will always be non-negative.
* @param {number} key
* @param {number} value
* @return {void}
*/
MyHashMap.prototype.put = function(key, value) {
this.map[key] = value;
};
/**
* Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
* @param {number} key
* @return {number}
*/
MyHashMap.prototype.get = function(key) {
if (this.map.hasOwnProperty(key)) {
return this.map[key];
} else {
return -1;
}
};
/**
* Removes the mapping of the specified value key if this map contains a mapping for the key
* @param {number} key
* @return {void}
*/
MyHashMap.prototype.remove = function(key) {
if (this.map.hasOwnProperty(key)) {
delete this.map[key];
}
};
/**
* Your MyHashMap object will be instantiated and called as such:
* var obj = new MyHashMap()
* obj.put(key,value)
* var param_2 = obj.get(key)
* obj.remove(key)
*/class MyHashMap {
public:
/** Initialize your data structure here. */
MyHashMap() {
}
/** value will always be non-negative. */
void put(int key, int value) {
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
int get(int key) {
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
void remove(int key) {
}
};
/**
* 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);
*/class MyHashMap {
/** Initialize your data structure here. */
public MyHashMap() {
}
/** value will always be non-negative. */
public void Put(int key, int 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) {
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
public void Remove(int key) {
}
}
/**
* 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);
*/