一. 问题背景

之前我们提到了哈希集合的朴素实现。

你要知道哈希表的一个重要思想就是使用空间换时间。

他引入了一个用作桶的数组。所以我们可以通过O(1)的时间+哈希函数进行插入和检索。

不过这种做法空间的浪费太严重了，注意到我们C++中使用hash来实现的set，是不能存储重复元素的。

在这种背景下，我们使用一个int的空间只是为了存储0和1两个数组。

如果我们遇到大数据的情况，空间浪费就不容忽视了。

对于0和1两个数字我们完全可以用1个位来存储，这就是我们的bitmap思想。

二. bitmap的思想

一个int类型的元素，最多能存储32位的信息。这32位都可以用来存储我们的key。

不过这里32位最多也只能存储32个key。为此我们引入了数组。

一个拥有m个元素的数组，最多可以存储m * 32个元素的key。

我们可以通过以下两个部分来访问这个元素的键：

1.  确定这个键在那个范围：a[val / 32]
2.  确定这个键在那个位上：1 << (val % 32)

这样一来就和我们的朴素实现差不多了 。

三. 代码实现

class MyHashSet {
private:
  int a[31255];     // 桶；int有32位，这里每一位都用来存储相应数字
public:
    /** Initialize your data structure here. */
    MyHashSet() {
      // 注意如果要对数字的某一位进行操作的时候
      // 应该使用&或者|等位操作，而不应该直接使用=
      memset(a, 0, sizeof(a));
    }
    
    void add(int key) {
      int k = key / 32;   // k用来确定索引
      int m = key % 32;   // 确定是哪一位
      a[k] |= 1 << m;  // 第（m+1）位置1
    }
    
    void remove(int key) {
      int k = key / 32;
      int m = key % 32;
      a[k] &= ~(1 << m);    // 这里只要关注a[k]为1怎么清0就行了
    }
    
    /** Returns true if this set contains the specified element */
    bool contains(int key) {
      int k = key / 32;
      int m = key % 32;
      return a[k] & (1 << m);
    }
};

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet* obj = new MyHashSet();
 * obj->add(key);
 * obj->remove(key);
 * bool param_3 = obj->contains(key);
 */

四. 其他经验

这个基于bitmap的hashset实现还有纯位操作版本的，它使用了以下技巧：

1.  与除法等价的位操作——右移操作。
2.  与取余等价的位操作——使用MASK来获取数字的后面几位。