故事从这里开始～～～
先看一个简单的问题：有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));
}
}
