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
37
38
39
40
41
class MyHashMap {
 public:
  /** Initialize your data structure here. */
  MyHashMap() : lists(kSize) {}

  /** value will always be non-negative. */
  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);
  }

  /** Returns the value to which the specified key is mapped, or -1 if this map
   * contains no mapping for the key */
  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;
  }

  /** Removes the mapping of the specified value key if this map contains a
   * mapping for the key */
  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;
  vector<list<pair<int, int>>> lists;  // Each slot store (key, value) list
};

 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
37
38
39
40
41
42
43
44
45
class MyHashMap {
  /** Initialize your data structure here. */
  public MyHashMap() {
    lists = new List[kSize];

    for (int i = 0; i < kSize; ++i)
      lists[i] = new ArrayList<>();
  }

  /** value will always be non-negative. */
  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});
  }

  /**
   * Returns the value to which the specified key is mapped, or -1 if this map
   * contains no mapping for the key
   */
  public int get(int key) {
    for (int[] pair : lists[key % kSize])
      if (pair[0] == key)
        return pair[1];
    return -1;
  }

  /**
   * Removes the mapping of the specified value key if this map contains a mapping
   * for the key
   */
  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 store (key, value) list
}