40亿个QQ号码去重

文件中有40亿个QQ号码，请设计算法对QQ号码去重，相同的QQ号码仅保留一个，内存限制1G。

bitmap(位图)

BitMap的原理
BitMap 的基本原理就是用一个bit 位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。

举例：在Java里面一个int类型占4个字节，假如要对于10亿个int数据进行处理呢？10亿*4/1024/1024/1024=4个G左右，需要4个G的内存。
如果能够采用bit储,一个bit是8位，就可以标识8个数字，那么512M = （512 * 1024 * 1024 * 8） 位 = 43亿, 那么在存储空间方面可以大大节省。1M -> 1024bit ->1024*8个bit位
在Java里面，BitMap已经有对应实现的数据结构类java.util.BitSet，BitSet的底层使用的是long类型的数组来存储元素。
我们来看看具体存储：

对于1，3，5，7这四个数，如果存在的话，则可以这样表示：

1代表这个数存在，0代表不存在。例如表中01010101代表1，3，5，7存在，0，2，4，6不存在。那如果8，10，14也存在怎么存呢？如图，8，10，14我们可以存在第二个字节里

以此类推。
然后从小到大遍历所有正整数(4字节)，当bitmapFlag值为1时，就表明该数是存在的

学习bitmap的代码 不是解决问题的代码

/*
 * Ant Group
 * Copyright (c) 2004-2022 All Rights Reserved.
 */
package com.wg.tooldemo.bin.suanfa;

import java.util.Arrays;
import java.util.BitSet;
import java.util.Random;

/**
 * @author 盼旺
 * @version BitMapTest.java, v 0.1 2022年01月05日 11:14 上午 盼旺
 */
public class BitMapTest {
    int ARRNUM = 800;
    /** 32位 */
    int LEN_INT = 32;
    int mmax = 9999;
    int mmin = 1000;
    int N = mmax - mmin + 1;

    public static void main(String args[]) {
        new BitMapTest().findDuplicate();
        new BitMapTest().findDup_jdk();
    }

    public void findDup_jdk() {
        System.out.println("*******调用JDK中的库方法--开始********");
        BitSet bitArray = new BitSet(N);
        int[] array = getArray(ARRNUM);
        for (int i = 0; i < ARRNUM; i++) {
            bitArray.set(array[i] - mmin);
        }
        int count = 0;
        for (int j = 0; j < bitArray.length(); j++) {
            if (bitArray.get(j)) {
                System.out.print(j + mmin + " ");
                count++;
            }
        }
        System.out.println();
        System.out.println("排序后的数组大小为：" + count );
        System.out.println("*******调用JDK中的库方法--结束********");
    }

    public void findDuplicate() {
        int[] array = getArray(ARRNUM);
        int[] bitArray = setBit(array);
        printBitArray(bitArray);
    }

    public void printBitArray(int[] bitArray) {
        int count = 0;
        for (int i = 0; i < N; i++) {
            if (getBit(bitArray, i) != 0) {
                count++;
                System.out.print(i + mmin + "\t");
            }
        }
        System.out.println();
        System.out.println("去重排序后的数组大小为：" + count);
    }

    public int getBit(int[] bitArray, int k) {// 1左移 k % 32位 与上 数组下标为 k/32 位置的值
        return bitArray[k / LEN_INT] & (1 << (k % LEN_INT));
    }

    public int[] setBit(int[] array) {// 首先取得数组位置下标 i/32, 然后 或上
        // 在该位置int类型数值的bit位：i % 32
        int m = array.length;
        int bit_arr_len = N / LEN_INT + 1;
        int[] bitArray = new int[bit_arr_len];
        for (int i = 0; i < m; i++) {
            int num = array[i] - mmin;
            bitArray[num / LEN_INT] |= (1 << (num % LEN_INT));
        }
        return bitArray;
    }

    public int[] getArray(int ARRNUM) {

        @SuppressWarnings("unused")
        int array1[] = { 1000, 1002, 1032, 1033, 6543, 9999, 1033, 1000 };

        int array[] = new int[ARRNUM];
        System.out.println("数组大小：" + ARRNUM);
        Random r = new Random();
        for (int i = 0; i < ARRNUM; i++) {
            array[i] = r.nextInt(N) + mmin;
        }

        System.out.println(Arrays.toString(array));
        return array;
    }
}