# LeetCode Easy 706. Design HashMap

tags: leetcode

問題

• Explore
• Problems

アイデア

HashMapを実装せよという問題．この手の問題ってHash関数を決めるのが面倒だし，この手の問題はコードで実装するというより口頭で説明出来れば良い気がする．

だから，実装は適当です．

• put(key, value): HashMapに(key, value)を挿入する．すでに，HashMapに存在していれば，valueを更新する．
• get(key): keyによって指定された値を返す．もし，なければ-1を返す．
• remove(key): もしあれば，keyによって指定される値を削除する．

解法

std::vectorの要素にstd::listを使い，std::pairを入れたり出したりします．

計算量

HashMapの大きさが\(M\)で挿入する要素の数が$N$がです．

• 時間計算量
  • コンストラクタは$O(M)$
  • put(key, value)は$O(1)$, get(key)は平均$O(1)$で最悪$O(N)$でremove(key)も同様
• 空間計算量
  • コンストラクタは$O(M)$
  • 他は全て$O(1)$

C++

class MyHashMap {
private:
  vector<list<pair<int, int>>> hashMap;
  size_t mapSize = 10000;
public:
    /** Initialize your data structure here. */
    MyHashMap() {
      hashMap.resize(mapSize);
    }
    
    /** value will always be non-negative. */
    void put(int key, int value) {
      auto &list = hashMap[key % mapSize];
      for (auto& pair : list) {
        if (pair.first == key) {
          pair.second = value;
          return;
        }
      }
      list.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 auto &list = hashMap[key % mapSize];
      if (list.empty())
        return -1;
      
      for (const auto& pair : list) {
        if (pair.first == key) {
          return pair.second;
        }
      }
      return -1;
    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key) {
      auto &list = hashMap[key % mapSize];
      for (auto pair = list.begin(); pair != list.end(); ++pair) 
        if (pair->first == key) {
          list.erase(pair);
          return;
        }
    }
};

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap* obj = new MyHashMap();
 * obj->put(key,value);
 * int param_2 = obj->get(key);
 * obj->remove(key);
 */