Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

706. Design HashMap

Time: $O(1)$

Space: $O(n)$

			


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 = begin(pairs); it != end(pairs); ++it)
      if (it->first == key) {
        pairs.erase(it);
        return;
      }
  }

 private:
  static const int kSize = 10000;
  vector<list<pair<int, int>>> lists;  // Each slot store (key, value) list
};




			


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
}