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.
1using System;
2using System.Collections.Generic;
3
4public class MyHashMap {
5
6 private class Pair {
7 public int Key;
8 public int Value;
9 public Pair(int key, int value) {
10 Key = key;
11 Value = value;
12 }
13 }
14
15 private const int size = 1000;
16 private List<Pair>[] map;
17
18 public MyHashMap() {
19 map = new List<Pair>[size];
20 for (int i = 0; i < size; i++) {
21 map[i] = new List<Pair>();
22 }
23 }
24
25 private int Hash(int key) {
26 return key % size;
27 }
28
29 public void Put(int key, int value) {
30 int hashKey = Hash(key);
31 foreach (Pair pair in map[hashKey]) {
32 if (pair.Key == key) {
33 pair.Value = value;
34 return;
35 }
36 }
37 map[hashKey].Add(new Pair(key, value));
38 }
39
40 public int Get(int key) {
41 int hashKey = Hash(key);
42 foreach (Pair pair in map[hashKey]) {
43 if (pair.Key == key) {
44 return pair.Value;
45 }
46 }
47 return -1;
48 }
49
50 public void Remove(int key) {
51 int hashKey = Hash(key);
52 Pair toRemove = null;
53 foreach (Pair pair in map[hashKey]) {
54 if (pair.Key == key) {
55 toRemove = pair;
56 break;
57 }
58 }
59 if (toRemove != null) {
60 map[hashKey].Remove(toRemove);
61 }
62 }
63}The C# solution uses arrays of lists to implement the hash map. Each list handles collisions for a specific index of the map.
Pair class for storing key-value data is used.Put method looks for a key in its bucket and updates the value or adds a new pair if the key wasn't found.Get retrieves values by key, returning -1 if the key doesn't exist.Remove deletes the key-value pair.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.
1#include <vector>
2#include <utility>
using namespace std;
class MyHashMap {
private:
static const int size = 1000;
vector<pair<int, int>> map;
vector<bool> occupied;
int primaryHash(int key) {
return key % size;
}
int secondaryHash(int key) {
return 1 + (key % (size - 1));
}
public:
MyHashMap(): map(size, make_pair(-1, -1)), occupied(size, false) {}
void put(int key, int value) {
int primary = primaryHash(key);
int secondary = secondaryHash(key);
int index = primary;
for (int i = 0; i < size; ++i) {
if (!occupied[index] || map[index].first == key) {
map[index] = {key, value};
occupied[index] = true;
return;
}
index = (index + secondary) % size;
}
}
int get(int key) {
int primary = primaryHash(key);
int secondary = secondaryHash(key);
int index = primary;
for (int i = 0; i < size; ++i) {
if (!occupied[index]) {
return -1;
}
if (map[index].first == key) {
return map[index].second;
}
index = (index + secondary) % size;
}
return -1;
}
void remove(int key) {
int primary = primaryHash(key);
int secondary = secondaryHash(key);
int index = primary;
for (int i = 0; i < size; ++i) {
if (occupied[index] && map[index].first == key) {
occupied[index] = false;
return;
}
index = (index + secondary) % size;
}
}
};This C++ implementation uses double hashing by means of two hash functions to mitigate clustering in an open addressing context.