Sponsored
Sponsored
This method employs an array of linked lists (chaining) to handle collisions. Each index represents a hash code, and if multiple keys hash to the same index, we store them in a linked list at that index. This helps us efficiently manage key collisions.
Time Complexity: For each operation (put, get, remove), it is O(n) in the worst case, where n is the number of keys stored at a particular index.
Space Complexity: O(N) where N is the number of distinct keys inserted into the hash map.
1#include <vector>
2#include <list>
3using namespace std;
4
5class MyHashMap {
6private:
7 static const int size = 1000;
8 vector<list<pair<int, int>>> map;
9
10 int hash(int key) {
11 return key % size;
12 }
13
14public:
15 MyHashMap() {
16 map.resize(size);
17 }
18
19 void put(int key, int value) {
20 int idx = hash(key);
21 for (auto &it : map[idx]) {
22 if (it.first == key) {
23 it.second = value;
24 return;
25 }
26 }
27 map[idx].emplace_back(key, value);
28 }
29
30 int get(int key) {
31 int idx = hash(key);
32 for (const auto &it : map[idx]) {
33 if (it.first == key) {
34 return it.second;
35 }
36 }
37 return -1;
38 }
39
40 void remove(int key) {
41 int idx = hash(key);
42 map[idx].remove_if([key](const pair<int, int> &it) { return it.first == key; });
43 }
44};This C++ solution uses a vector of linked lists to implement a hash map with separate chaining. The linked lists are implemented as lists of key-value pairs (using the STL list).
hash function computes the index for a given key.put, we update the value if the key exists; otherwise, we insert it.get, we check each element at the computed index for the desired key.remove, we utilize remove_if to delete the key-value pair if found.Double hashing avoids the clustering problem by calculating two hash functions. If a collision occurs, a second hash determines the step size for probing.
Time Complexity: O(1) on average for put, get, and remove due to effective hashing; O(n) in worst-case.
Space Complexity: O(N) for storing entries with keys and values.
1using System;
public class MyHashMap {
private int[][] map;
private bool[] occupied;
private const int size = 1000;
public MyHashMap() {
map = new int[size][];
occupied = new bool[size];
for (int i = 0; i < size; i++) {
map[i] = new int[] { -1, -1 };
}
}
private int PrimaryHash(int key) {
return key % size;
}
private int SecondaryHash(int key) {
return 1 + (key % (size - 1));
}
public void Put(int key, int value) {
int index = PrimaryHash(key);
int step = SecondaryHash(key);
while (true) {
if (!occupied[index] || map[index][0] == key) {
map[index][0] = key;
map[index][1] = value;
occupied[index] = true;
return;
}
index = (index + step) % size;
}
}
public int Get(int key) {
int index = PrimaryHash(key);
int step = SecondaryHash(key);
while (true) {
if (!occupied[index]) return -1;
if (map[index][0] == key) return map[index][1];
index = (index + step) % size;
}
}
public void Remove(int key) {
int index = PrimaryHash(key);
int step = SecondaryHash(key);
while (true) {
if (occupied[index] && map[index][0] == key) {
occupied[index] = false;
map[index][0] = -1;
return;
}
index = (index + step) % size;
}
}
}Throughout this C# double hashing model, dual hashes streamline practicality across core MyHashMap operations, mandatory for double duty within clustered settings.