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.