文件中有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;
}
}
