BitMap

BitMap

大数据问题解决

海量数据处理

package com.zhang.reflection.面试.大数据处理;
import java.util.Random;
/**
 * 10亿int整型数，以及一台可用内存为1GB的机器，时间复杂度要求O(n)，统计只出现一次的数？
 * url:  https://itimetraveler.github.io/2017/07/13/%E3%80%90%E7%AE%97%E6%B3%95%E3%80%9110%E4%BA%BFint%E5%9E%8B%E6%95%B0%EF%BC%8C%E7%BB%9F%E8%AE%A1%E5%8F%AA%E5%87%BA%E7%8E%B0%E4%B8%80%E6%AC%A1%E7%9A%84%E6%95%B0/
 */
public class BitMap {
    private static final int CAPACITY = 1000000000;//数据容量
    // 定义一个byte数组缓存所有的数据
    private byte[] dataBytes = new byte[1 << 29];
    public static void main(String[] args) {
        BitMap ms = new BitMap();
        byte[] bytes = null;
        Random random = new Random();
        for (int i = 0; i < CAPACITY; i++) {
            int num = random.nextInt();
            System.out.println("读取了第 " + (i + 1) + "\t个数: " + num);
            bytes = ms.splitBigData(num);
        }
        System.out.println("");
        ms.output(bytes);
    }
    /**
     * 读取数据，并将对应数数据的 到对应的bit中，并返回byte数组
     * @param num 读取的数据
     * @return byte数组  dataBytes
     */
    private byte[] splitBigData(int num) {
        long bitIndex = num + (1l << 31);         //获取num数据对应bit数组（虚拟）的索引
        int index = (int) (bitIndex / 8);         //bit数组（虚拟）在byte数组中的索引
        int innerIndex = (int) (bitIndex % 8);    //bitIndex 在byte[]数组索引index 中的具***置
        System.out.println("byte[" + index + "] 中的索引：" + innerIndex);
        dataBytes[index] = (byte) (dataBytes[index] | (1 << innerIndex));
        return dataBytes;
    }
    /**
     * 输出数组中的数据
     * @param bytes byte数组
     */
    private void output(byte[] bytes) {
        int count = 0;
        for (int i = 0; i < bytes.length; i++) {
            for (int j = 0; j < 8; j++) {
                if (!(((bytes[i]) & (1 << j)) == 0)) {
                    count++;
                    int number = (int) ((((long) i * 8 + j) - (1l << 31)));
                    System.out.println("取出的第  " + count + "\t个数: " +  number);
                }
            }
        }
    }
}