Designing a simple HashMap
Question on Leetcode: https://leetcode.com/problems/design-hashmap/description/
Example:
Note:
I have highlighted above the key statement in this question: the keys to be used will be in the range 0 to 1M. In such a case, just have a simple array to be used as the hash map, and if you want you can even have another array of bool indicating whether the specified key has been used or not (in case you want to store "0" thus having a flag to indicate whether a key has been used or not). Mem is cheap, only 1M integers and 1M booleans. Code is below, thanks, Marcelo.
Design a HashMap without using any built-in hash table libraries.
To be specific, your design should include these functions:
put(key, value): Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value.get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.remove(key): Remove the mapping for the value key if this map contains the mapping for the key.
Example:
MyHashMap hashMap = new MyHashMap(); hashMap.put(1, 1); hashMap.put(2, 2); hashMap.get(1); // returns 1 hashMap.get(3); // returns -1 (not found) hashMap.put(2, 1); // update the existing value hashMap.get(2); // returns 1 hashMap.remove(2); // remove the mapping for 2 hashMap.get(2); // returns -1 (not found)
Note:
- All keys and values will be in the range of
[0, 1000000]. - The number of operations will be in the range of
[1, 10000]. - Please do not use the built-in HashMap library.
I have highlighted above the key statement in this question: the keys to be used will be in the range 0 to 1M. In such a case, just have a simple array to be used as the hash map, and if you want you can even have another array of bool indicating whether the specified key has been used or not (in case you want to store "0" thus having a flag to indicate whether a key has been used or not). Mem is cheap, only 1M integers and 1M booleans. Code is below, thanks, Marcelo.
public class MyHashMap
{
int N = 1000000;
int[] hashMap = null;
bool[] used = null;
/** Initialize your data structure here. */
public MyHashMap()
{
hashMap = new int[N];
used = new bool[N];
}
/** value will always be non-negative. */
public void Put(int key, int value)
{
if (key >= 0 && key < N)
{
hashMap[key] = value;
used[key] = true;
}
}
/** 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)
{
if (key >= 0 && key < N && used[key])
{
return hashMap[key];
}
else
{
return -1;
}
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
public void Remove(int key)
{
if (key >= 0 && key < N && used[key])
{
used[key] = false;
}
}
}
Comments
Great insight about a limited number range, since it makes the backing store super trivial, but it's possible to further simplify this by initializing all of its elements to -1 which takes care of a case when querying elements that were not set. This makes implementation completely trivial:
Reply Deleteclass MyHashMap {
private:
vector values;
public:
/** Initialize your data structure here. */
MyHashMap(): values(1000001, -1) {}
/** value will always be non-negative. */
void put(int key, int value) {
values[key] = 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) {
return values[key];
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
void remove(int key) {
values[key] = -1;
}
};
Post a Comment
[γγ¬γΌγ ]