第二周 BitMap （未完成）

出另一个问题，大家看看怎么做：计算机内存是1个g，现在有10个g的手机号存在文件里，想要统计出这里边手机号重复次数最多的手机号，怎么做？大家想一想，提示：利用哈希的知识

Bitmap

位运算算法 
就是用一个bit位来标记某个元素对应的Value， 而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。

bitmap的应用
 1）可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下。
 2）去重数据而达到压缩数据

可以理解为
位数组就是用更少的内存来构建这个 "HashMap"。

讲解例子

BitMap应用：排序示例
假设我们要对0-7内的5个元素(4,7,2,5,3)排序（这里假设这些元素没有重复）。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数，我们就只需要8个Bit（1Bytes），首先我们开辟1Byte的空间，将这些空间的所有Bit位都置为0

[0 0 0 0 0 0 0 0]


然后遍历这5个元素，首先第一个元素是4，那么就把4对应的位置为1，因为是从零开始的，所以要把第五位置为一：

[0 0 0 0 1 0 0 0]


然后再处理第二个元素7，将第八位置为1,，接着再处理第三个元素，一直到最后处理完所有的元素，将相应的位置为1，这时候的内存的Bit位的状态如下：

[0 0 1 1 1 1 0 1]

遍历一遍Bit区域，将该位是一的位的编号输出（2，3，4，5，7），这样就达到了排序的目的。



BitMap算法评价
优点：
    1. 运算效率高，不进行比较和移位；
    2. 占用内存少，比如最大的数MAX=10000000；只需占用内存为MAX/8=1250000Byte=1.25M。
缺点：
    1. 所有的数据不能重复，即不可对重复的数据进行排序。（少量重复数据查找还是可以的，用2-bitmap）。
    2. 当数据类似（1，1000，10万）只有3个数据的时候，用bitmap时间复杂度和空间复杂度相当大，只有当数据比较密集时才有优势。

数据例子

在java语言下，对10亿个int类型数据排重。java中一个 int 类型在内存中占4 byte。那么10亿个int类型数据共需要开辟10 ^ 9次方 *4 byte ≈ 4GB 的连续内存空间。以 32 位操作系统电脑为例，最大支持内存为 4G， 可用内存更是小于4G。所以上述方法在处理大数据时根本行不通。


我们可以用1个 bit 来对应一个int 整数。假如对应的 int 类型的数据存在，就将其对应的 bit 赋值为1，否则，赋值为0（boolean类型）。
java中 int 范围为 -2^31  到  2^31-1. 那么所有可能的数值组成的长度为2^32. 对应的 bit 长度也为 2^32.  
那么可以用这样处理之后只需要开辟2^32 bit  = 2^29 byte = 512M 大小的 内存空间 。

代码实现

byte[] bits = new byte[getIndex(n) + 1];


 /**
     * num/8得到byte[]的index
     * @param num
     * @return
     */
public int getIndex(int num){
    //有符号右移
        return num >> 3;
}
    
 /**
     * num%8得到在byte[index]的位置
     * @param num
     * @return
     */
public int getPosition(int num){
        //数字和二进制的0111做与运算,相当于num%8
        return num & 0x07;
}
    
 /**
* 标记指定数字（num）在bitmap中的值，标记其已经出现过
* 将1左移position后，那个位置自然就是1，然后和以前的数据做或运算，这样，那个位置就替换成1了
* @param bits
* @param num
     */

public void add(byte[] bits, int num){
    //有符号右移
        bits[getIndex(num)] |= 1 << getPosition(num);
 }

JAVA类中的使用

true/false。

import java.util.BitSet;
public class Test{
    public static void main(String[] args) {
        int [] array = new int [] {1,2,3,22,0,3};
        BitSet bitSet  = new BitSet(6);
        //将数组内容组bitmap
        for(int i=0;i<array.length;i++)
        {
            bitSet.set(array[i], true);
        }
       System.out.println(bitSet.size());
        System.out.println(bitSet.get(3));
    }
}

get(int bitIndex) 返回具有指定索引的位的值。 
void set(int bitIndex) 将指定索引处的位设置为 true 。 
void set(int bitIndex, boolean value) 将指定索引处的位设置为指定值

最后编辑于：2020.06.06 09:07:40