【哈希表】哈希集合（bitmap）

一. 問題背景

之前我們提到了哈希集合的樸素實作。

你要知道哈希表的一個重要思想就是使用空間換時間。

他引入了一個用作桶的數組。是以我們可以通過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來擷取數字的後面幾位。