- 正确答案：Bitmap（位图）是一种利用位来表示数据状态的数据结构，常用于高效地进行集合操作、去重、排序以及大规模数据的统计。典型应用场景包括用户签到系统、布隆过滤器、内存数据库中的索引优化、IP地址占用检测、广告曝光去重等。 - 解答思路：首先明确什么是Bitmap——它本质上是一个bit数组，每个bit代表一个整数是否存在（1表示存在，0表示不存在）。然后结合其空间效率高、操作速度快的特点，列举出适合使用Bitmap的实际业务场景。最后可以进一步引申到其局限性（如只适用于整数、稀疏数据效率低），并介绍升级版结构如Roaring Bitmap。 - 深度知识讲解： 1. **底层原理**： Bitmap基于位运算实现，假设我们要表示从0到n-1的所有整数是否出现过，可以用一个长度为⌈n/8⌉字节的字节数组来存储，每个bit对应一个整数。例如，第i个整数的状态由 byte[i / 8] 的第 (i % 8) 位决定。常见的位操作包括： - 设置第i位为1：byte_array[i >> 3] |= (1 << (i & 7)) - 判断第i位是否为1：(byte_array[i >> 3] & (1 << (i & 7))) != 0 - 清除第i位：byte_array[i >> 3] &= ~(1 << (i & 7)) 这些操作都是O(1)时间复杂度，非常高效。 2. **空间优势**：存储1亿个布尔值，若用Java中的boolean数组，大约需要100MB（每个boolean实际占1字节）；而用Bitmap只需要约12.5MB（1e8 bits ≈ 12.5 * 10^6 bytes）。 3. **典型应用场景区分**： a. **用户签到系统**：如某App每天记录用户签到情况，用户ID为整数（或可映射为连续整数），可用一个Bitmap记录某天所有用户的签到状态。支持快速查询、累计签到天数统计（通过多个Bitmap做AND）、漏签分析（OR后找0）等。 b. **布隆过滤器（Bloom Filter）的基础组件**： Bloom Filter使用多个哈希函数将元素映射到位数组的不同位置，所有位置都为1才认为可能存在。这里的核心就是Bitmap。虽然有误判率，但空间极省，适合缓存穿透防护、爬虫URL去重等。 c. **广告/推荐系统的曝光去重**：在实时推荐中，同一个用户短时间内不应重复看到同一广告。可以用用户ID+广告ID生成唯一整数标识（如hash后取模或long转int），写入分布式Bitmap（如Redis的setbit），实现快速判断是否已曝光。 d. **权限控制系统**：比如用每一位表示一种权限（读、写、执行……），一个32位或64位整数即可表示一组权限，通过位与、位或进行权限校验和合并。 e. **大数据去重与交并差计算**：当处理海量用户行为日志时，比如求“今天访问A页面和B页面的共同用户”，如果每个页面访问用户ID构建一个Bitmap，则求交集就是两个Bitmap按位与，速度极快。 4. **局限性与改进方案**： - 只能处理非负整数，且最好是范围不太大的整数（否则内存浪费严重） - 对于稀疏数据（如只有几个数被设置），传统Bitmap仍需分配大片内存 - 改进方案：Roaring Bitmap 将大范围整数划分为若干块（如每2^16为一块），每块内根据密度选择不同存储方式（数组、位图、运行编码等），兼顾密集和稀疏场景，在Elasticsearch、Druid、ClickHouse中广泛应用。 - 代码示例（简易Bitmap实现）： ``` public class SimpleBitmap { private byte[] bits; private int size; public SimpleBitmap(int n) { this.size = n; this.bits = new byte[(n + 7) / 8]; // 向上取整除以8 } public void set(int i) { if (i < 0 || i >= size) throw new IndexOutOfBoundsException(); bits[i >> 3] |= (1 << (i & 7)); } public boolean get(int i) { if (i < 0 || i >= size) return false; return (bits[i >> 3] & (1 << (i & 7))) != 0; } public void clear(int i) { bits[i >> 3] &= ~(1 << (i & 7)); } } ``` 使用示例： ``` SimpleBitmap bm = new SimpleBitmap(1000); bm.set(10); bm.set(100); System.out.println(bm.get(10)); // true System.out.println(bm.get(11)); // false ``` - 扩展知识点： - Redis中的Bitmap命令：setbit, getbit, bitcount（统计1的数量，可用于日活统计）, bitop（支持and/or/xor/not操作）示例：用bitcount统计某天有多少用户登录，用bitop and统计连续两天活跃用户数。 - Java中的内置Bitmap工具类：java.util.BitSet，提供动态扩容、flip、and/or等方法，无需手动管理内存。 - 分布式环境下可用HBase、Redis Cluster或专门的位图数据库（如BitFunnel）来支持超大规模Bitmap。总结：Bitmap是典型的“以空间换效率”的经典数据结构，特别适合整数集合的存储与运算。在校园招聘面试中，考察点不仅在于是否知道这个结构，更在于能否结合实际场景说明其优缺点，并能手写核心操作代码。

虾皮后端一面

全站热榜

创作者周榜