Leetcode 706. Design HashMap
Problem Explanation
The problem requires us to implement a hashmap without using any built-in hash table libraries. Specifically, we need to implement three methods put, get and remove. The put method should insert a key-value pair into the hashmap, if the value already exists, it should update the value. The get method should return the value corresponding to a given key, if it's not found return -1. The remove function removes the mapping of the specified value key if the hash map contains a mapping for the key.
For example, we start with an empty hash map, and we can add some values:
1 2 3hashMap.put(1, 100); 4hashMap.put(2, 200);
now the hashmap will have a map of {1:100, 2: 200}
if we call hashMap.get(1)
it would return 100, as there is a key 1 with value 100 in the hash map. If we call hashMap.get(3)
, it would return -1 as there are no values mapped to key 3 in the hashmap.
we then update the value of key 2:
1 2 3hashMap.put(2, 300);
now the hashmap will have a map of {1:100, 2: 300}, because the put method replaces the existing value for a key if the key already exists in the hash map.
We then do hashMap.remove(2)
, removing the original mapping of 2:300. Now the hashmap contains only {1: 100}.
Approach
The simplest approach is to store the key-value pairs in a list, where each element of the list is a pair of the key and value. When we do a put operation, we add the key-value pair to the end of the list. When we do a get or remove operation, we check each element in the list until we find the matching key. This approach has a time complexity of O(n) for all operations, because in the worst case we have to check every element in the list.
To optimize, we use a list of lists to store the keys and values, where each slot in the list is mapped to a specific key using its hash code (i.e., use a fixed-size array of linked lists). When we put an element, we append it to the end of the corresponding linked list. When we get or remove an element, we only need to check the elements in the corresponding linked list, reducing the amount of data to be processed. This approach improves the average time complexity for each operation to O(1), assuming that the hash function does a good job of distributing the keys evenly across the array.
Solution
Python Solution
1 2python 3class MyHashMap: 4 5 def __init__(self) -> None: 6 self.size = 10000 7 self.buckets = [[] for _ in range(self.size)] 8 9 def put(self, key: int, value: int) -> None: 10 index = key % self.size 11 for pair in self.buckets[index]: 12 if pair[0] == key: 13 pair[1] = value 14 return 15 self.buckets[index].append([key, value]) 16 17 def get(self, key: int) -> int: 18 index = key % self.size 19 for pair in self.buckets[index]: 20 if pair[0] == key: 21 return pair[1] 22 return -1 23 24 def remove(self, key: int) -> None: 25 index = key % self.size 26 for pair in self.buckets[index]: 27 if pair[0] == key: 28 self.buckets[index].remove(pair)
Java Solution
1
2java
3class MyHashMap {
4
5 private int size = 10000;
6 private List<List<int[]>> buckets;
7
8 public MyHashMap() {
9 this.buckets = new ArrayList<>(size);
10 for (int i = 0; i < size; i++) {
11 buckets.add(new ArrayList<>());
12 }
13 }
14
15 public void put(int key, int value) {
16 int index = key % size;
17 for (int[] pair : buckets.get(index)) {
18 if (pair[0] == key) {
19 pair[1] = value;
20 return;
21 }
22 }
23 buckets.get(index).add(new int[] {key, value});
24 }
25
26 public int get(int key) {
27 int index = key % size;
28 for (int[] pair : buckets.get(index)) {
29 if (pair[0] == key) {
30 return pair[1];
31 }
32 }
33 return -1;
34 }
35
36 public void remove(int key) {
37 int index = key % size;
38 List<int[]> bucket = buckets.get(index);
39 for (int i = 0; i < bucket.size(); i++) {
40 if (bucket.get(i)[0] == key) {
41 bucket.remove(i);
42 return;
43 }
44 }
45 }
46}
JavaScript Solution
1
2js
3class MyHashMap {
4
5 constructor() {
6 this.size = 10000;
7 this.buckets = [...Array(this.size)].map(i => new LinkedList());
8 }
9
10 put(key, value) {
11 const index = key % this.size;
12 this.buckets[index].add(key, value);
13 }
14
15 get(key) {
16 const index = key % this.size;
17 return this.buckets[index].get(key);
18 }
19
20 remove(key) {
21 const index = key % this.size;
22 this.buckets[index].remove(key);
23 }
24}
C++ Solution
1
2cpp
3class MyHashMap {
4 private:
5 static constexpr int size = 10000;
6 vector<list<pair<int, int>>> buckets;
7
8 public:
9 MyHashMap() : buckets(size) {}
10
11 void put(int key, int value) {
12 auto &pairs = buckets[key % size];
13 for (auto &pair : pairs) {
14 if (pair.first == key) {
15 pair.second = value;
16 return;
17 }
18 }
19 pairs.push_back({key, value});
20 }
21
22 int get(int key) {
23 const auto &pairs = buckets[key % size];
24 for (const auto &pair : pairs) {
25 if (pair.first == key) {
26 return pair.second;
27 }
28 }
29 return -1;
30 }
31
32 void remove(int key) {
33 auto &pairs = buckets[key % size];
34 for (auto iterator = pairs.begin(); iterator != pairs.end(); iterator++) {
35 if (iterator->first == key) {
36 pairs.erase(iterator);
37 return;
38 }
39 }
40 }
41};
C# Solution
1
2csharp
3public class MyHashMap {
4
5 private int size = 10000;
6 private List<List<KeyValuePair<int, int>>> buckets;
7
8 public MyHashMap() {
9 this.buckets = new List<List<KeyValuePair<int, int>>>(this.size);
10 for (int i = 0; i < this.size; i++) {
11 buckets.Add(new List<KeyValuePair<int, int>>());
12 }
13 }
14
15 public void Put(int key, int value) {
16 int index = key % size;
17 foreach (var pair in buckets[index]) {
18 if (pair.Key == key) {
19 pair.Value = value;
20 return;
21 }
22 }
23 buckets[index].Add(new KeyValuePair<int, int>(key, value));
24 }
25
26 public int Get(int key) {
27 int index = key % size;
28 foreach (var pair in buckets[index]) {
29 if (pair.Key == key) {
30 return pair.Value;
31 }
32 }
33 return -1;
34 }
35
36 public void Remove(int key) {
37 int index = key % size;
38 foreach (var pair in buckets[index]) {
39 if (pair.Key == key) {
40 buckets[index].Remove(pair);
41 return;
42 }
43 }
44 }
45}
Ruby Solution
In Ruby, the solution is similar to our approaches in other languages. We will use an array of arrays (a built-in Ruby data structure) to store the key-value pairs, mapping each key to its corresponding bucket using a hash function.
1 2ruby 3class MyHashMap 4 5 def initialize() 6 @size = 10000 7 @buckets = Array.new(@size) { Array.new } 8 end 9 10 def put(key, value) 11 index = key % @size 12 @buckets[index].each do |pair| 13 if pair[0] == key 14 pair[1] = value 15 return 16 end 17 end 18 @buckets[index] << [key, value] 19 end 20 21 def get(key) 22 index = key % @size 23 @buckets[index].each do |pair| 24 return pair[1] if pair[0] == key 25 end 26 return -1 27 end 28 29 def remove(key) 30 index = key % @size 31 @buckets[index].delete_if { |pair| pair[0] == key } 32 end 33 34end
In this Ruby solution, we initialize an array of 10,000 arrays. Each "bucket" in the top-level array corresponds to keys that produce the same hash value. Inside the put, get, and remove methods, we use Ruby's built-in array methods to process the key-value pairs within each bucket.
Conclusion
These solutions, presented in several programming languages, illustrate how to implement a simple HashMap using lists of lists as underlying data structures. This approach leverages hashing to quickly access the memory positions of keys and their corresponding values. By doing so, it provides constant-time complexity for the adding, fetching, and removal of data.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.