数据结构之 — bitMap

面试官：有多达10亿无序整数，已知最大值为15亿，请对这个10亿个数进行排序,怎么实现？

1、先从一个一个简单的问题开始

已知有n整个整数，这些整数的范围是[0, 100]，请你设计一种数据结构，使用数组存储这些数据，并提供两种方法，分别是addMember 和 isExist，下面是这种数据结构的类的定义，请你实现它的两个方法

function FindClass(){
    var datas = [];    //存储数据

    // 加入一个整数 member
    this.addMember = function(member){
    };

    // 判断member是否存在
    this.isExist = function(member){
    };
}

var fc = new FindClass();
var arr = [0, 3, 5, 6, 9, 34, 23, 78, 99];
for(var i = 0;i < arr.length;i++){
    fc.addMember(arr[i]);
}

console.log(fc.isExist(3));
console.log(fc.isExist(7));
console.log(fc.isExist(78));

当你实现addMember和isExist之后，执行上面的代码，预期的输出结果是

true
false
true

1.1 毫无难度的实现

这种算法题，没有任何难度，只要会使用数组，就可以实现,先来看addMember的实现

        // 加入一个整数 member
        this.addMember = function(member){
            datas.push(member);
        };

接下来看isExist的实现，我这里提供两种方法

方法1

       // 判断member是否存在
        this.isExist = function(member){
            for(var i = 0;i < datas.length; i++){
                if(datas[i]==member){
                    return true;
                }
            }
            return false;
        };

方法2

        // 判断member是否存在
        this.isExist = function(member){
            if(datas.indexOf(member) >= 0){
                return true;
            }
            return false;
        };

1.2 更快的方法

现在，题目难度升级，前面的实现虽然满足要求，但是速度慢，不论使用for循环查找，还是使用indexOf方法，时间复杂度都是O(n)，加入的元素越多，isExist方法的速度越慢，我们需要一个时间复杂度是O(1)的算法，不论向里面增加了多少数据，isExist的执行速度都是常量时间。

通过索引操作数据，时间复杂度就是O(1)，题目说明这些数在0到100之间，那么就用每个数自身的值作为索引，比如对于3这个数，可以让data[3] = 1，就表示把3添加进来了，data[2] = 0，表示2没有添加进来，那么这样一来，isExist方法就可以利用索引来判断member是否存在。
实现代码如下:

function FindClass(){
    var datas = new Array(100); //存储数据
    // 先都初始化成0
    for(var i = 0;i < datas.length;i++){
        datas[i] = 0;
    }

    // 加入一个整数 member
    this.addMember = function(member){
        datas[member] = 1;
    };

    // 判断member是否存在
    this.isExist = function(member){
        if(datas[member] == 1){
            return true;
        }
        return false;
    };
}


var fc = new FindClass();
var arr = [0, 3, 5, 6, 9, 34, 23, 78, 99];
for(var i = 0;i < arr.length;i++){
    fc.addMember(arr[i]);
}

console.log(fc.isExist(3));
console.log(fc.isExist(7));
console.log(fc.isExist(78));

刚刚，我们实现了一个更加快速的算法，但这不是终点。

1.3 更节省空间的算法

1.2 中实现的算法，已经很快，但是却面临一个新的问题，如果数据非常多，多达1个亿，每个整数是4个字节，那么一亿个整数数就是4亿个字节，1024字节是1kb，1024kb是1M,4亿个字节就381M的内存空间。

如果没有这么多内存该怎么办？我们需要一种数据压缩的算法，用很少的空间来表示这一亿个数的存在与否。

2. 街边的路灯

街边有8栈路灯，编号分别是1 2 3 4 5 6 7 8 ，其中2号，5号，7号，8号路灯是亮着的，其余的都处于不亮的状态，请你设计一种简单的方法来表示这8栈路灯亮与不亮的状态。

一个非计算机专业的人看到这个问题，多半会嗤之以鼻，这算什么问题，答案是2578，表示这些编号的路灯是亮的，其余的都是不亮的。

而一个计算机专业的人看到这个问题，应该回答说75，因为75的二进制表示是0 1 0 0 1 0 1 1，恰好与路灯亮灭的状态相对应

1 2 3 4 5 6 7 8
0 1 0 0 1 0 1 1

仅仅是8个bit位就能表示8栈路灯的亮灭情况，那么一个整数有32个bit位，就可以表示32栈路灯的亮灭情况，回想我们在第一小节中遇到的问题，isExist方法要判断一个数是否存在，是不是也可以借助这种表达方式呢？

value是一个int类型的数据，初始化成0，当addMember传进来的参数是0的时候，就把value的二进制的第1位设置为1，二进制表示就是

00000000 00000000 00000000 00000001

此时，value = 1
如果又增加了一个3，就把value的二进制的第4为设置为1，二进制表示就是

00000000 00000000 00000000 00001001

此时，value = 9, 9可以表示 0 和 3都存在，一个整数，其实可以表示 0-31 的存在与否，如果我创建一个大小为10的数组，数组里存储整数，那么这个数组就可以表示0~319的存在与否

datas[0]  表示0~31存在与否
datas[1]  表示32~63存在与否
....
datas[9]  表示288~319存在与否

通过这种方式，就可以把空间的使用降低到原来的32分之一，存储一亿个整数的存在与否，只需要12M的内存空间,那么该如何对整数的二进制位进行操作呢。

3. 位运算

内存中的数据，最终的存储方式都是二进制，位运算就是对整数在内存中的二进制位进行操作。

3.1 按位与 &

两个整数进行按位与运算，相同二进制位的数字如果都是1，则结果为1，有一个位为0，则结果为0， 下面是 3 & 7的计算过程

二进制    整数

0 1 1     3
1 1 1     7

0 1 1     3

3 & 7 = 3

3.2 按位或 |

两个整数进行按位或运算，相同二进制位的数字如果有一个为1，则结果为1，都为0，则结果为0， 下面是 5 | 8 的计算过程

二进制        整数

0 1 0 1       5
1 0 0 0       8

1 1 0 1       13

5 | 8 = 13

3.3 左移 <<

二进制向左移动 n 位，在后面添加 n 个0
下面是 3<<1 计算过程。

二进制       整数

 1 1 3 
  1 1 0      6

3<<1 = 6

3.4 小试牛刀

一组数，内容以为 3， 9， 19， 20，请用一个整数来表示这些四个数

var value = 0;
value = value | 1<<3;
value = value | 1<<9;
value = value | 1<<19;
value = value | 1<<20;
console.log(value);

程序输出结果为1573384

4. bitmap

4.1 新的实现方式

经过前面一系列的分析和位运算学习，现在，我们要重新设计一个类，实现addMember和isExist方法，用更快的速度，更少的内存。

• 数据范围是0到100，那么只需要4个整数就可以表示4*32个数的存在与否，创建一个大小为4的数组
• 执行addMember时，先用member/32，确定member在数组里的索引（arr_index），然后用member%32，确定在整数的哪个二进制位行操作(bit_index)，最后执行bit_arr[arr_index] = bit_arr[arr_index] | 1<<bit_index;
• 执行isExist时，先用member/32，确定member在数组里的索引（arr_index），然后用member%32，确定在整数的哪个二进制位行操作(bit_index)，最后执行bit_arr[arr_index] & 1<<bit_index，如果结果不为0，就说明memeber存在

新的实现方法

function BitMap(size){
    var bit_arr = new Array(size);
    for(var i=0;i<bit_arr.length;i++){
        bit_arr[i] = 0;
    }

    this.addMember = function(member){
        var arr_index = Math.floor(member / 32); // 决定在数组中的索引
        var bit_index = member % 32; // 决定在整数的32个bit位的哪一位上
        bit_arr[arr_index] = bit_arr[arr_index] | 1<<bit_index;
    };

    this.isExist = function(member){
        var arr_index = Math.floor(member / 32); // 决定在数组中的索引
        var bit_index = member % 32; // 决定在整数的32个bit位的哪一位上
        var value = bit_arr[arr_index] & 1<<bit_index;
        if(value != 0){
            return true;
        }
        return false;
    };
}

var bit_map = new BitMap(4);
var arr = [0, 3, 5, 6, 9, 34, 23, 78, 99];
for(var i = 0;i < arr.length;i++){
    bit_map.addMember(arr[i]);
}

console.log(bit_map.isExist(3));
console.log(bit_map.isExist(7));
console.log(bit_map.isExist(78));

程序运行结果为

true
false
true

4.2 概念

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

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

4.3 大数据排序

有多达10亿无序整数，已知最大值为15亿，请对这个10亿个数进行排序。
传统排序算法都不可能解决这个排序问题，即便内存允许，其计算时间也是漫长的，如果使用BitMap就极为简单。

BitMap存储最大值为15亿的集合，只需要180M的空间，空间使用完全可以接受，至于速度，存储和比较过程中的位运算速度都非常快，第一次遍历，将10亿个数都放入到BitMap中，第二次，从0到15亿进行遍历，如果在BitMap，则输出该数值，这样经过两次遍历，就可以将如此多的数据排序。

为了演示方便，只用一个很小的数组，[0, 6, 88, 7, 73, 34, 10, 99, 22]，已知数组最大值是99，利用BitMap排序的算法如下

var arr = [0, 6, 88, 7, 73, 34, 10, 99, 22];
var sort_arr = [];

var bit_map = new BitMap(4);
for(var i = 0;i < arr.length;i++){
    bit_map.addMember(arr[i]);
}

for(var i = 0;i <= 99;i++){
    if(bit_map.isExist(i)){
        sort_arr.push(i);
    }
}
console.log(sort_arr);

程序输出结果为

[ 0, 6, 7, 10, 22, 34, 73, 88, 99 ]

需要强调的一点，利用BitMap排序，待排序的集合中不能有重复数据。