故事從這里開始～～～
先看一個簡單的問題：有n個不小于0的整數(shù)，現(xiàn)在要設(shè)計一個類腿椎，用數(shù)組存儲數(shù)據(jù)优烧，并提供兩個方法add和isExist，用來添加數(shù)據(jù)和判斷數(shù)據(jù)是否存在
相信我們不用思考就寫出來了
function Test () {
const data = [];
this.add = (num) => {
data.push(num);
}
this.isExist = (num) => {
return data.indexOf(num) >= 0;
}
}
這個實現(xiàn)雖然滿足要求庸娱，但是速度慢啊着绊，時間復(fù)雜度是O(n), 隨著加入數(shù)據(jù)的增多，查找時間也會越來越長熟尉。
有什么辦法可以降低查找時間的呢归露？我們是判斷這個數(shù)據(jù)存不存在框仔，如果把加入的數(shù)據(jù)作為數(shù)組下標(biāo)岩齿，對應(yīng)的值設(shè)置為1，這樣查找的時候
只需要判斷data[num]是不是等于1就行了，這樣的話不管有多少數(shù)據(jù)诚欠，只需一次就可以判斷出該數(shù)據(jù)是否存在了磷雇。
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;
}
}
上面這個方法雖然查找時間快了雳窟，但是如果有上億個數(shù)據(jù)表窘，那得占多少內(nèi)存啊。js中一個Number類型的整數(shù)占8個字節(jié)堕油，1024字節(jié)是1kb潘飘，
1024kb是1M, 假設(shè)一億個整數(shù)就占762M的內(nèi)存空間。沒有這么多內(nèi)存咋辦呢掉缺，bitmap就登場了～
bitmap是一種數(shù)據(jù)壓縮的算法卜录，用二進(jìn)制位來存儲數(shù)據(jù)。
在正式進(jìn)入bitmap之前先看幾個位運算
位運算
按位與 &
參加運算的兩個運算數(shù)按二進(jìn)制位進(jìn)行“與”運算攀圈。如果相同二進(jìn)制位的數(shù)字都是1暴凑，則結(jié)果為1， 否則是0.
二進(jìn)制 整數(shù)
010 2
011 3
010 2
即2 & 3 = 2
按位或 |
參加運算的兩個運算數(shù)按二進(jìn)制位進(jìn)行“或”運算赘来。如果相同二進(jìn)制位的數(shù)字有一個是1现喳，則結(jié)果為1，否則是0.
二進(jìn)制 整數(shù)
010 2
011 3
011 3
即2 | 3 = 3
左移 <<
將一個運算對象的二進(jìn)制向左移動n位犬辰，左邊的二進(jìn)制位丟棄嗦篱，右邊補(bǔ)0
2<<2:
二進(jìn)制 整數(shù)
10 2
1000 8
異或 ^
參加運算的兩個運算數(shù)，按二進(jìn)制進(jìn)行“異或”運算幌缝。相應(yīng)二進(jìn)制位不同灸促，結(jié)果為1，否則為0.
0^0=0; 0^1=1; 1^0=1; 1^1=0;
二進(jìn)制 整數(shù)
010 2
011 3
001 1
即2^3 = 1;
BitMap
現(xiàn)在我們以一種新的方式實現(xiàn)前面的功能涵卵。
前面我們用數(shù)據(jù)做下標(biāo)浴栽，用0和1來區(qū)分該值是否存在。0和1正好是二進(jìn)制數(shù)轿偎，現(xiàn)在我們?nèi)杂?和1來表示數(shù)據(jù)存在與否典鸡，但是存入的數(shù)據(jù)不作為數(shù)組的下標(biāo)了，
而是二進(jìn)制數(shù)的第幾位坏晦。
比如我們新加了個0萝玷，就把二進(jìn)制的第一位設(shè)置為1:
00000000 00000001
再次添加了3，就把二進(jìn)制的第三位設(shè)置為1:
00000000 00000101
又添加了8昆婿，就把二進(jìn)制的第八位設(shè)置為1:
00000000 10000101
判斷該值是否存在的時候球碉，就判斷該二進(jìn)制位上是不是1.
由于JS中一個Number類型的數(shù)是64bit，那么
data[0] 可以表示0～63是否存在
data[1] 可以表示64～127是否存在
...
這樣的話占用空間將大大降低仓蛆。
首先我們先明確兩個值：
const arrIndex = Math.floor(num / 64); // 確定num在數(shù)組中的索引
const bitIndex = num % 64; // 確定在哪個二進(jìn)制位上
實現(xiàn)方法:
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在數(shù)組中的索引
const bitIndex = num % 64; // 確定在哪個二進(jìn)制位上
data[arrIndex] = data[arrIndex] | 1<<bitIndex // 把相應(yīng)位置上的二進(jìn)制數(shù)置為1
}
this.isExist = (num) => {
const arrIndex = Math.floor(num / 64); // 確定num在數(shù)組中的索引
const bitIndex = num % 64; // 確定在哪個二進(jìn)制位上
return !!(data[arrIndex] & 1<<bitIndex) // 相應(yīng)位置上的二進(jìn)制數(shù)是否為1睁冬，為1則表示該數(shù)存在
}
}
現(xiàn)在這種數(shù)據(jù)結(jié)構(gòu)基于位做映射，能夠用很少的內(nèi)存存儲數(shù)據(jù)多律，和數(shù)組不同痴突，它只能存儲表示某個數(shù)是否存在搂蜓，可以用于大數(shù)據(jù)去重狼荞、大數(shù)據(jù)排序辽装、兩個集合取交集等。
BitMap在處理大數(shù)據(jù)時才有優(yōu)勢相味，而且要求數(shù)據(jù)集緊湊拾积，如果要處理的數(shù)只有三個，1丰涉，1000拓巧，100000，那空間利用率就太低了一死，最大的值決定了BitMap要用多少內(nèi)存肛度。
練習(xí)題
練習(xí)一 、大數(shù)據(jù)排序
有多達(dá)10億無序整數(shù)投慈，已知最大值為15億承耿，請對這10億個數(shù)進(jìn)行排序
思路分析：
通過兩次遍歷，第一次先把所有數(shù)據(jù)存到BitMap中伪煤，第二次從0到最大值進(jìn)行遍歷加袋，如果在BitMap中，則輸出該值抱既。
為了方便职烧，使用一個小數(shù)組進(jìn)行編碼, 最大值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);
練習(xí)二、 兩個集合取交集
兩個數(shù)組防泵，內(nèi)容分別為[1, 4, 6, 8, 9, 10, 15], [6, 14, 9, 2, 0, 7]蚀之，用BitMap計算他們的交集
思路分析：
先把其中一個數(shù)組存入BitMap中，然后遍歷另一個數(shù)組捷泞，如果存在于BitMap中足删，則說明這個數(shù)是重復(fù)的
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);
練習(xí)三、 支持負(fù)數(shù)
前面的BitMap類只能存儲大于等于0的整數(shù)肚邢，現(xiàn)在要改造BitMap類壹堰，不論正數(shù)還是負(fù)數(shù)，都可以存儲并判斷是否存在
思路分析：
可以用兩個數(shù)組來存儲骡湖，一個存儲大于等于0的整數(shù)贱纠，一個存儲小于0的整數(shù)
function SuperBitMap(size) {
const positiveBitMap = new BitMap(size); // 存儲大于等于0的整數(shù)
const negativeBitMap = new BitMap(size); // 存儲小于0的整數(shù)
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);
}
}
練習(xí)四、 查找不重復(fù)的數(shù)
有一個數(shù)組响蕴，內(nèi)容為[1, 3, 4, 5, 7, 4, 8, 9, 2, 9]谆焊，有些數(shù)值是重復(fù)出現(xiàn)的，請你改造BitMap類浦夷，增加一個isRepeat(member)方法辖试，判斷member是否重復(fù)出現(xiàn)辜王，并利用該方法找出數(shù)組中不重復(fù)的數(shù)
思路分析：
一個bit位有兩個狀態(tài)，表示一個數(shù)是否存在」扌ⅲ現(xiàn)在我們可以用相鄰的兩個bit位來表示一個數(shù)是否存在以及是否重復(fù)呐馆。這樣64個bit位可以表示32個數(shù)的存在以及重復(fù)狀態(tài)。
比如莲兢，一開始添加一個0汹来，把第一個位置置為1，表示0存在了改艇。
00000000 00000001
然后又添加了一個0收班，就把第二個位置置為1，表示0是重復(fù)的谒兄。
00000000 00000011
這樣摔桦，判斷0是否存在的時候，判斷第一個位置是否為1承疲；判斷0是否重復(fù)的時候邻耕，判斷第二個位置是否為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));
}
}
