706.md

706. Design HashMap

Leetcode link

解题思路

本题跟 705 的思路基本相同，区别在于这题的 map 在添加已经存在的 key 的时候需要覆盖原来的值；而 705 的 set 是直接不处理。

在 JS 中，因为已经有天然的 map 了，我就直接用了。

C++ 的话我还是选择用多个桶，来降低空间的使用。

C++

class MyHashMap {
 private:
  const int BUCKET_SIZE = 100;
  vector<pair<int, int>> bucket[100];

 public:
  MyHashMap() {}

  void put(int key, int value) {
    for (auto& [k, v] : bucket[key % BUCKET_SIZE]) {
      if (key == k) {
        v = value;
        return;
      }
    }
    bucket[key % BUCKET_SIZE].push_back({key, value});
  }

  int get(int key) {
    for (auto& [k, v] : bucket[key % BUCKET_SIZE]) {
      if (key == k) {
        return v;
      }
    }
    return -1;
  }

  void remove(int key) {
    int i = 0;
    auto& target = bucket[key % BUCKET_SIZE];
    for (auto& [k, v] : target) {
      if (key == k) {
        target.erase(target.begin() + i);
      }
      i++;
    }
  }
};

Javascript

var MyHashSet = function() {
    this.set = {};
};

/** 
 * @param {number} key
 * @return {void}
 */
MyHashSet.prototype.add = function(key) {
    this.set[key] = key;
};

/** 
 * @param {number} key
 * @return {void}
 */
MyHashSet.prototype.remove = function(key) {
    delete this.set[key];
};

/** 
 * @param {number} key
 * @return {boolean}
 */
MyHashSet.prototype.contains = function(key) {
    return key in this.set
};