Skip to content

706. Design HashMap 👍

  • Time: $O(1)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class MyHashMap {
 public:
  MyHashMap() : lists(kSize) {}

  void put(int key, int value) {
    auto& pairs = lists[key % kSize];
    for (auto& [k, v] : pairs)
      if (k == key) {
        v = value;
        return;
      }
    pairs.emplace_back(key, value);
  }

  int get(int key) {
    const list<pair<int, int>>& pairs = lists[key % kSize];
    for (const auto& [k, v] : pairs)
      if (k == key)
        return v;
    return -1;
  }

  void remove(int key) {
    auto& pairs = lists[key % kSize];
    for (auto it = pairs.begin(); it != pairs.end(); ++it)
      if (it->first == key) {
        pairs.erase(it);
        return;
      }
  }

 private:
  static constexpr int kSize = 10000;
  // Each slot stores the (key, value) list.
  vector<list<pair<int, int>>> lists;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class MyHashMap {
  public MyHashMap() {
    lists = new List[kSize];
    for (int i = 0; i < kSize; ++i)
      lists[i] = new ArrayList<>();
  }

  public void put(int key, int value) {
    for (int[] pair : lists[key % kSize])
      if (pair[0] == key) {
        pair[1] = value;
        return;
      }
    lists[key % kSize].add(new int[] {key, value});
  }

  public int get(int key) {
    for (int[] pair : lists[key % kSize])
      if (pair[0] == key)
        return pair[1];
    return -1;
  }

  public void remove(int key) {
    for (int i = 0; i < lists[key % kSize].size(); ++i)
      if (lists[key % kSize].get(i)[0] == key) {
        lists[key % kSize].remove(i);
        return;
      }
  }

  private static final int kSize = 10000;
  List<int[]>[] lists; // Each slot stores the (key, value) list.
}