利用bitmap处理海量数据问题：43亿QQ号所占内存大小为什么是512M？40亿个QQ号如何去重？

​参考:

• 腾讯43亿QQ号码用完后怎么办？
• 腾讯三面：40亿个QQ号码如何去重

一、背景：

首先，明确两点：

• QQ号是 unsigned int 类型（4字节无符号整数，共32bit）, 也就是说 QQ号的取值范围是：$[0,2^{32}-1]$。
• QQ号是一个长度为10位的整数，大约是43亿，这也是QQ号码的理论最大值。
• QQ号码的最小值是 10001， 为什么tx要做这种限制呢？仅仅是早期的一个设定而已。
  

二、43亿QQ号所占内存大小计算：

其次，43亿QQ号所占内存大小是多少呢？512M！

• 一个 unsigned int 类型数据可以标识 0 ~ 31 这32个整数的存在与否（4Byte，0 ~ 31 ）
• 两个 unsigned int 类型数据可以标识 0 ~ 64 这64个整数的存在与否（8Byte，0 ~ 64 ）

又因为QQ号是 unsigned int 类型（无符号整数，4Byte，32位），也就是说 QQ号的取值范围是：$[0,2^{32}-1]$。
因此可对 2³² 次方范围内的QQ号所占大小进行推导：

1. 1Byte所能标识数的范围为0~7（1字节，8 位）
2. 4Byte所能标识数的范围为0~31（4字节，32 位）
3. …
4. 那么多少Byte才能够标识 数的范围为 0 ~ 2³²-1（2³² 位）呢？

综上，用 2³² / 32 来表示：0 ~ 2³²-1（2³² 位） 能包含多少个 0 ~ 31（32位） 范围的块。并且每个 0 ~ 31（32位） 的块儿大小为4字节，因此 2³² / 32 × 4字节 的结果就是 0 ~ 2³²-1 范围所占字节的总大小，也就是 43亿 QQ号所占字节总大小。
2³²位 / 32位 × 4字节 / 1024 / 1024 = $512M$（1M=1024KB，1KB=1024Byte）

由此可见，512M的内存大小，就可以用来标识所有QQ号的存在与否。

三、bitmap的具体实现：

• 把所有 bitMap 位数组依次拼接后可表示 0 ~ 2³² 范围内43亿的数，所以足够存储40亿不重复的账号了
• bitmap数组中的一个uint32类型元素，由4字节组成(每个字节占8位)：{[8位][8位][8位][8位]} {[8位][8位][8位][8位]} {[8位][8位][8位][8位]} {[8位][8位][8位][8位]} …
• 如：[0 1 2 3 4 5 6 7] [8 9 10 11 12 13 14 15] [16 17 18 19 20 21 22 23] [24 25 26 27 28 29 30 31] … [...] [...] [...] [... 40亿]
• 共需 40亿/8位 = 5亿字节，5亿字节/4字节 = 1.25亿 个uint32类型元素数组来串联拼接表示（uint32类型大小占4字节）,所占内存大小为：4000000000/8/1024/1024 ≈ $477M$
• 还原qq号（数组下标从0开始）：当前第block块数 * 每个uint32 block块的固定大小为32 + 当前block块内的偏移量余数 yushu

---

• 每次新增QQ号时，都只需要在 bitMap[block] 的结果基础上继续进行异或 ^ 运算即可 ~
• 比如原本"QQ号=9（二进制表示 1 0000 0000，位下标为 9）“是有值的，现在又新增了"qq号=10（二进制表示 10 0000 0000，位下标为 10）”
• 那么9和10相异或后得: 1 0000 0000 ^ 10 0000 0000 = 11 0000 0000，表示第 9 位和第 10 位的QQ号都有值了
• 0x1<<(yuShu-1)：比如原本"QQ号=9"时，那就把 0x1 左移8位，即：0x1 << 8，得到 100000000，最后从右至左第9位为1
• 关键代码：bitMap[block] = bitMap[block] ^ (0x1 << (yuShu - 1)) // 设置标记位：在之前bitMap已有结果的基础上，设置第block块上的第 “(0x1 << (yuShu - 1))” bit位为1

// 把所有位数组依次拼接后可表示 0~2³² 范围内的数，所以足够存储40亿不重复的账号了
// bitmap数组中的一个uint32类型元素，由4字节组成(每个字节占8位)：{[8位][8位][8位][8位]} {[8位][8位][8位][8位]} {[8位][8位][8位][8位]} {[8位][8位][8位][8位]} ...
// 如：[0 1 2 3 4 5 6 7][8 9 10 11 12 13 14 15][16 17 18 19 20 21 22 23][24 25 26 27 28 29 30 31] ... [...][...][...][... 40亿]
// 共需 40亿/8bit = 5亿byte，5亿byte/4byte = 1.25亿个uint32类型元素数组来串联表示（uint32类型大小占4字节）,所占内存大小为：4000000000/8/1024/1024≈477M
// 还原qq号（数组下标从0开始）：当前第block块数 * 每个block块的固定大小32 + 当前block块内的偏移量余数yushu

// 每次新增QQ号时，都只需要在bitMap[block]的结果上继续进行异或^运算即可~
// 比如原本"QQ号=9（二进制表示 1 0000 0000，位下标为9）"是有值的，现在又新增了"qq号=10（二进制表示 10 0000 0000，位下标为10）"
// 那么相异或后得: 1 0000 0000 ^ 10 0000 0000 = 11 0000 0000，表示第9位和第10位的QQ号都有值了
// 0x1<<(yuShu-1)：比如原本"QQ号=9"时，那就把0x1左移8位，即：0x1 << 8，得到 100000000，从右至左第9位为1

// 根据QQ号来设置其在bitMap中bit位
func BitCalculation(bitMap []uint32, everyBlockSize, qq uint32) {
	// 判断是属于第几块的第几个bit位
	block := qq / everyBlockSize // 块数：第block块（bitmap数组从第0块开始，无需根据yuShu是否为0来判断block是否+1）
	yuShu := qq % everyBlockSize // 余数：第block块中的具体第几个bit位
	// fmt.Printf("block=%v, yuShu=%v \n", block, yuShu)

	fmt.Printf("在对%v(%b)位运算设置标记位1之前，bitMap的第%v块上二进制表示: %b\n", qq, 0x1<<(yuShu-1), block, bitMap[block])
	bitMap[block] = bitMap[block] ^ (0x1 << (yuShu - 1)) // 设置标记位：在之前bitMap已有结果的基础上，设置第block块上的第 "(0x1 << (yuShu - 1))" bit位为1
	fmt.Printf("在对%v(%b)位运算设置标记位1之后，bitMap的第%v块上二进制表示: %b，还原qq号为: %v\n\n", qq, 0x1<<(yuShu-1), block, bitMap[block], block*everyBlockSize+yuShu)
}

// 初始化相关参数
func TestBit(qqCnt uint32, qqArr []uint32) {
	var everyBlockSize uint32 = 4 * 8  // uint32类型占32位：一个uint32能标记0~31范围内32个QQ号
	blockCnt := qqCnt / everyBlockSize // 40亿QQ号所需uint32类型的块数
	bitMap := make([]uint32, blockCnt) // 存储40亿QQ号的bitmap，统一初始化为0
	// fmt.Println("blockCnt 40亿QQ号所需uint32类型的块数: ", blockCnt) // 1.25亿块

	for i := 0; i < len(qqArr); i++ {
		// 设置每个测试QQ到bitMap中
		BitCalculation(bitMap, everyBlockSize, qqArr[i])
	}
}

func main() {
	// 以下均默认在64位操作系统下执行：
	// i := int(1)                   // int在64位系统下默认大小为8，即：int64
	// fmt.Println(unsafe.Sizeof(i)) // 8
	//
	// j := int32(1)
	// fmt.Println(unsafe.Sizeof(j)) // 4
	//
	// k := int64(1)
	// fmt.Println(unsafe.Sizeof(k)) // 8 相当于long/double类型，占8字节(64位) 最大能表示范围为：2⁶⁴
	//
	// ll := float64(1)
	// fmt.Println(unsafe.Sizeof(ll))

	// int32 表示范围: -2147483648 ~ 2147483647，因为账号数有40亿个，所以采用无符号类型 uint32 类型，表示范围: 0 ~ 4294967295

	var qqAccountCnt uint32 = 4000000000
	testNumArr := []uint32{9, 399999999, 1234567890} // test data
	TestBit(qqAccountCnt, testNumArr)

	return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

示例结果展示：

四、扩展

练习一：文件中有40亿个互不相同的QQ号码，请设计算法对QQ号码进行$排序$，内存限制1G。
很显然，直接用bitmap,
标记这40亿个QQ号码的存在性，然后从小到大遍历正整数，当bitmapFlag的值为1时，就输出该值，输出后的正整数序列就是排序后的结果。
请注意，这里必须限制40亿个QQ号码互不相同。通过bitmap记录，客观上就自动完成了排序功能。

练习二：文件中有40亿个互不相同的QQ号码，求这些QQ号码的$中位数$，内存限制1G。
一些刷题经验丰富的人，最开始想到的肯定是用堆或者文件切割，这明显是犯了本本主义错误。直接用bitmap排序，当场搞定中位数。

练习三：文件中有40亿个互不相同的QQ号码，求这些QQ号码的$topK$，内存限制1G。
很多人背诵过topK问题，信心满满，想到用小顶堆或者文件切割，这明显又是犯了本本主义错误。直接用bitmap排序，当场搞定topK问题。

练习四：文件中有80亿个QQ号码，试判断其中是否存在$相同$的QQ号码，内存限制1G。
一些吸取了经验教训的人肯定说，直接bitmap啊。然而，又一次错了。根据容斥原理可知：
因为QQ号码的个数是43亿左右(理论值2^32 - 1)，所以80亿个QQ号码必然存在相同的QQ号码。

五、总结：

• QQ号理论上的范围为：10001 - 43亿（2³²），其类型为 unsigned int
• 43亿QQ号所占内存大小，经计算后大约占 512M （满足小于1G的要求）
• 40亿QQ号所占内存大小，经计算后大约占 477M （满足小于1G的要求）
• bitMap实现方案 及 异或 ^ 等位运算
• 利用 bitMap 来处理海量数据问题，内存占用低，满足要求且可以取得不错的效果。包括：排序、中位数、topK、去重 等等…