【大厂面试题】火山如何能实现位图数据bitmap处理文本？

weilai

abcfox

weilai 发表于 2025-10-3 00:33

谢谢分享，给打80分，因为没有用到bitmap数据结构

abcfox

Bitmap（位图）原理​
Bitmap 是一种用 “位（bit）” 标识数据存在性的高效数据结构，核心优势是极致的空间效率（用 1 个 bit 代表 1 个数据的 “存在 / 不存在” 状态），时间复杂度为 O (n)（遍历一次即可完成去重）。​

1. 位与数据的映射逻辑​
每个 “位” 仅需两种状态：0（数据不存在）、1（数据存在）。通过基础数据类型的 “多位数” 特性，可批量管理多个数据的状态：​
1 个 unsigned char（1 字节 = 8bit）：可标识 0~7 共 8 个整数的存在性；​
1 个 unsigned int（4 字节 = 32bit）：可标识 0~31 共 32 个整数的存在性；​
以此类推：k 个字节的空间，可标识 k×8 个整数的存在性。​

2. 关键计算：Bitmap 空间需求​
对于 QQ 号最大值 2^32 - 1（需覆盖 0~2^32-1 共 2^32 个数值），所需空间换算如下：​
总位数需求：2^32 bit（每个 QQ 号对应 1 位）；​
总字节需求：2^32 bit ÷ 8 bit/字节 = 512 MB；​
结论：仅需 512MB 空间，即可容纳所有 QQ 号的存在性标识。

3. 方案步骤
初始化 Bitmap 数组：
用 unsigned int 数组实现 Bitmap（每个元素 32bit），数组长度为 2^32 ÷ 32 = 2^28（即 268435456 个元素），总占用空间 512MB。
遍历 QQ 号，标记存在性：
对文件中每个 QQ 号 x，通过位运算定位其在 Bitmap 中的位置，并将对应位设为 1（重复 QQ 号会多次设 1，但结果不变，自动去重）：
计算数组索引：index = x ÷ 32（确定 x 落在哪个 unsigned int 元素上）；
计算位偏移：offset = x % 32（确定 x 在该元素的第几位）；
位运算设 1：bitmap[index] |= (1 << offset)（用 “或操作” 确保该位为 1）。
遍历 Bitmap，输出去重结果：
从小到大遍历 0~2^32-1 的所有数值，检查 Bitmap 中对应位是否为 1：
若为 1：该数值是去重后的 QQ 号，输出；
若为 0：该数值未出现，跳过。

weilai

abcfox 发表于 2025-10-3 09:38
谢谢分享，给打80分，因为没有用到bitmap数据结构

这样写效率不错还简单，处理大数据整数使用bit合理些，当然了这样写效率不算最高，稍微优化下（原理一样）100m估计毫秒级（10毫秒以内）

abcfox

weilai 发表于 2025-10-3 10:12
这样写效率不错还简单，处理大数据整数使用bit合理些，当然了这样写效率不算最高，稍微优化下（原理一样 ...

是的，目前算是最优解方案了

weilai

abcfox 发表于 2025-10-3 11:44
是的，目前算是最优解方案了

其实使用bitmap 和使用哈希表处理整数的话 写法上没有区别没测试对不对，不过应该差不多

秋天的童话

支持火山高质量算法代码分享，用户感谢大佬！

abcfox

weilai 发表于 2025-10-3 14:02
其实使用bitmap 和使用哈希表处理整数的话 写法上没有区别没测试对不对，不过应该差不多

再次感谢，能给提供多种参考思路，优秀，100分！
希望对其他人也有参考帮助。