初识BitMap

故事从这里开始～～～

先看一个简单的问题：有n个不小于0的整数，现在要设计一个类，用数组存储数据，并提供两个方法add和isExist，用来添加数据和判断数据是否存在

相信我们不用思考就写出来了

function Test () {
  const data = [];

  this.add = (num) => {
    data.push(num);
  }

  this.isExist = (num) => {
    return data.indexOf(num) >= 0;
  }
}

这个实现虽然满足要求，但是速度慢啊，时间复杂度是O(n), 随着加入数据的增多，查找时间也会越来越长。

有什么办法可以降低查找时间的呢？我们是判断这个数据存不存在，如果把加入的数据作为数组下标，对应的值设置为1，这样查找的时候
只需要判断data[num]是不是等于1就行了，这样的话不管有多少数据，只需一次就可以判断出该数据是否存在了。

function Test (size) {
  const data = [];

  for(let i = 0; i < size; i++) {
    data[i] = 0;
  }

  this.add = (num) => {
    data[num] = 1;
  }

  this.isExist = (num) => {
    return data[num] === 1;
  }
}

上面这个方法虽然查找时间快了，但是如果有上亿个数据，那得占多少内存啊。js中一个Number类型的整数占8个字节，1024字节是1kb，
1024kb是1M, 假设一亿个整数就占762M的内存空间。没有这么多内存咋办呢，bitmap就登场了～

bitmap是一种数据压缩的算法，用二进制位来存储数据。

在正式进入bitmap之前先看几个位运算

位运算

按位与 &

参加运算的两个运算数按二进制位进行“与”运算。如果相同二进制位的数字都是1，则结果为1， 否则是0.

二进制   整数
010      2
011      3

010      2

即2 & 3 = 2

按位或 |

参加运算的两个运算数按二进制位进行“或”运算。如果相同二进制位的数字有一个是1，则结果为1，否则是0.

二进制   整数
010      2
011      3

011      3

即2 | 3 = 3

左移 <<

将一个运算对象的二进制向左移动n位，左边的二进制位丢弃，右边补0

2<<2:
二进制   整数
10      2
1000    8

异或 ^

参加运算的两个运算数，按二进制进行“异或”运算。相应二进制位不同，结果为1，否则为0.

0^0=0; 0^1=1; 1^0=1; 1^1=0;

二进制   整数
010      2
011      3

001      1

即2^3 = 1;

BitMap

现在我们以一种新的方式实现前面的功能。

前面我们用数据做下标，用0和1来区分该值是否存在。0和1正好是二进制数，现在我们仍用0和1来表示数据存在与否，但是存入的数据不作为数组的下标了，
而是二进制数的第几位。

比如我们新加了个0，就把二进制的第一位设置为1:

00000000 00000001

再次添加了3，就把二进制的第三位设置为1:

00000000 00000101

又添加了8，就把二进制的第八位设置为1:

00000000 10000101

判断该值是否存在的时候，就判断该二进制位上是不是1.

由于JS中一个Number类型的数是64bit，那么
data[0] 可以表示0～63是否存在
data[1] 可以表示64～127是否存在
...

这样的话占用空间将大大降低。

首先我们先明确两个值：

const arrIndex = Math.floor(num / 64); // 确定num在数组中的索引
const bitIndex = num % 64; // 确定在哪个二进制位上

实现方法:

function BitMap(size) {
  const data = [];
  for(let i = 0; i < size; i++) {
    data[i] = 0;
  }

  this.add = (num) => {
    const arrIndex = Math.floor(num / 64); // 确定num在数组中的索引
    const bitIndex = num % 64; // 确定在哪个二进制位上

    data[arrIndex] = data[arrIndex] | 1<<bitIndex // 把相应位置上的二进制数置为1
  }

  this.isExist = (num) => {
    const arrIndex = Math.floor(num / 64); // 确定num在数组中的索引
    const bitIndex = num % 64; // 确定在哪个二进制位上

    return !!(data[arrIndex] & 1<<bitIndex) // 相应位置上的二进制数是否为1，为1则表示该数存在
  }
}

现在这种数据结构基于位做映射，能够用很少的内存存储数据，和数组不同，它只能存储表示某个数是否存在，可以用于大数据去重、大数据排序、两个集合取交集等。

BitMap在处理大数据时才有优势，而且要求数据集紧凑，如果要处理的数只有三个，1，1000，100000，那空间利用率就太低了，最大的值决定了BitMap要用多少内存。

练习题

练习一 、大数据排序

有多达10亿无序整数，已知最大值为15亿，请对这10亿个数进行排序

思路分析：

通过两次遍历，第一次先把所有数据存到BitMap中，第二次从0到最大值进行遍历，如果在BitMap中，则输出该值。

为了方便，使用一个小数组进行编码, 最大值99：

const arr = [0, 6, 88, 7, 73, 34, 10, 99, 22];
const sortArr = [];
const bitmap = new BitMap(2);

for(const num of arr) {
  bitmap.add(num);
}
for(let i = 0; i <= 99; i++) {
  if (bitmap.isExist(i)) {
    sortArr.push(i);
  }
}
console.log(sortArr);

练习二、 两个集合取交集

两个数组，内容分别为[1, 4, 6, 8, 9, 10, 15], [6, 14, 9, 2, 0, 7]，用BitMap计算他们的交集

思路分析：

先把其中一个数组存入BitMap中，然后遍历另一个数组，如果存在于BitMap中，则说明这个数是重复的

const arr1 = [1, 4, 6, 8, 9, 10, 15];
const arr2 = [6, 14, 9, 2, 0, 7];
const intersectionArr = [];

const bitmap = new BitMap(1);

for(const num of arr1) {
  bitmap.add(num);
}
for(const num of arr2) {
  if (bitmap.isExist(num)) {
    intersectionArr.push(num);
  }
}
console.log(intersectionArr);

练习三、 支持负数

前面的BitMap类只能存储大于等于0的整数，现在要改造BitMap类，不论正数还是负数，都可以存储并判断是否存在

思路分析：

可以用两个数组来存储，一个存储大于等于0的整数，一个存储小于0的整数

function SuperBitMap(size) {
  const positiveBitMap = new BitMap(size); // 存储大于等于0的整数
  const negativeBitMap = new BitMap(size); // 存储小于0的整数

  this.add = (num) => {
    if (num >= 0) {
      positiveBitMap.add(num);
    } else {
      negativeBitMap.add(num);
    }
  }

  this.isExist = (num) => {
    if (num >= 0) {
      return positiveBitMap.isExist(num);
    }
    return negativeBitMap.isExist(num);
  }
}

练习四、 查找不重复的数

有一个数组，内容为[1, 3, 4, 5, 7, 4, 8, 9, 2, 9]，有些数值是重复出现的，请你改造BitMap类，增加一个isRepeat(member)方法，判断member是否重复出现，并利用该方法找出数组中不重复的数

思路分析：

一个bit位有两个状态，表示一个数是否存在。现在我们可以用相邻的两个bit位来表示一个数是否存在以及是否重复。这样64个bit位可以表示32个数的存在以及重复状态。

比如，一开始添加一个0，把第一个位置置为1，表示0存在了。
00000000 00000001
然后又添加了一个0，就把第二个位置置为1，表示0是重复的。
00000000 00000011

这样，判断0是否存在的时候，判断第一个位置是否为1；判断0是否重复的时候，判断第二个位置是否为1.

function BitMap(size) {
  const data = [];
  for(let i = 0; i < size; i++) {
    data[i] = 0;
  }

  this.add = (num) => {
    const arrIndex = Math.floor(num / 32);
    const bitIndex = num % 32;

    if (!this.isExist(num)) {
      data[arrIndex] = data[arrIndex] | 1 << (bitIndex * 2);
    } else {
      data[arrIndex] = data[arrIndex] | 1 << (bitIndex * 2 + 1);
    }    
  }

  this.isExist = (num) => {
    const arrIndex = Math.floor(num / 32);
    const bitIndex = num % 32;

    return !!(data[arrIndex] & 1 << (bitIndex * 2));
  }

  this.isRepeat = (num) => {
    const arrIndex = Math.floor(num / 32);
    const bitIndex = num % 32;

    return !!(data[arrIndex] & 1 << (bitIndex * 2 + 1));
  }
}