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 thekey
already exists in the map, update the correspondingvalue
.int get(int key)
returns thevalue
to which the specifiedkey
is mapped, or-1
if this map contains no mapping for thekey
.void remove(key)
removes thekey
and its correspondingvalue
if 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
104
calls will be made toput
,get
, andremove
.
class Pair<U,V>{
public U first;
public V second;
public Pair(U first, V second){
this.first = first;
this.second = second;
}
}
class Bucket{
private List<Pair<Integer,Integer>> bucket;
public Bucket(){
this.bucket = new LinkedList<Pair<Integer,Integer>>();
}
public Integer get(Integer key){
for(Pair<Integer,Integer> pair:this.bucket){
if(pair.first.equals(key)){
return pair.second;
}
}
return -1;
}
public void update(Integer key,Integer value){
boolean isFound = false;
for(Pair<Integer,Integer> pair:this.bucket){
if(pair.first.equals(key)){
isFound = true;
pair.second = value;
}
}
if(!isFound){
this.bucket.add(new Pair<Integer,Integer>(key,value));
}
}
public void remove(Integer key){
for(Pair<Integer,Integer> pair : this.bucket){
if(pair.first.equals(key)){
this.bucket.remove(pair);
break;
}
}
}
}
class MyHashMap {
private int key_space;
private List<Bucket> hash_table;
public MyHashMap() {
this.key_space = 2069;
this.hash_table = new ArrayList<Bucket>();
for(int i =0;i<key_space;i++){
this.hash_table.add(new Bucket());
}
}
public void put(int key, int value) {
int hash_key = key % this.key_space;
this.hash_table.get(hash_key).update(key,value);
}
public int get(int key) {
int hash_key = key % this.key_space;
return this.hash_table.get(hash_key).get(key);
}
public void remove(int key) {
int hash_key = key % this.key_space;
this.hash_table.get(hash_key).remove(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);
*/
Complexity Analysis
Time Complexity: for each of the methods, the time complexity is where is the number of all possible keys and is the number of predefined buckets in the hashmap, which is
2069
in our case.In the ideal case, the keys are evenly distributed in all buckets. As a result, on average, we could consider the size of the bucket is .
Since in the worst case we need to iterate through a bucket to find the desire value, the time complexity of each method is .
Space Complexity: where is the number of predefined buckets in the hashmap and is the number of unique keys that have been inserted into the hashmap.
No comments:
Post a Comment