706. Design HashMap

• Time: $O(1)$
• Space: $O(n)$

C++Java

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;
};

class MyHashMap {
  public MyHashMap() {
    lists = new List[SIZE];
    for (int i = 0; i < SIZE; ++i)
      lists[i] = new ArrayList<>();
  }

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

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

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

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