【场景】大数据常考场景题 - Bitmap

  大数据开发面试通常会问场景题，主要考察大数据中常用的数据结构，比如 Bitmap、Bloom Filter 等等。今天就说一个工作中碰到的。

比如昨天说到的问题，用户要在自定义时间区间内查询，就需要快速响应，可能用到 ClickHouse。可以先看昨天的文章。欢迎关注公众号。

大数据开发全流程

那么为什么 ClickHouse 为什么快呢？这要归因于底层的数据结构。考虑这样一个场景：

场景1：

用户画像将消费者分为很多类，比如按购买力分为购买力低、购买力中、购买力高，按粉丝的忠实程度分为路人、普通粉丝、忠实粉丝等等，这里就不考虑举例意义了，就分为 A、B、C 三类好了。

• 问题 1：考虑 t1 和 t2 两个时间点，在 t1 是 A 类的人中，t2 还是 A 类的有多少？
  • 例如 t1 A 类成员是 [0, 1, 2, 3]，t2 A 类成员是 [2, 3, 4]，那么结果就是 2（即 [2, 3] 这两个人）。
• 问题2：考虑 t1 和 t2 两个时间点，在 t1 是 A 类的人中，t2 变成 B 类的有多少？
  • 例如 t1 A 类成员是 [0, 1, 2, 3]，t2 B 类成员是 [1, 5]，那么结果就是 1（即 [1] 这一个人）。

分析：

用户数据量很大，又需要快速计算，所以这里可以用 ClickHouse 实现的 Bitmap 来解决。

• 问题1：
  • t1 A 类成员编码为二进制数 num1 = 0000 1111，表示 [0, 1, 2, 3] 这 4 个人；
  • t2 A 类成员编码为二进制数 num2 = 0001 1100，表示 [2, 3, 4] 这 3 个人；
  • num1 & num2 = 0000 1100 ，所以答案是 2。
• 问题 2 同理。

场景 2 ：

20 亿个整数中找出不重复的整数的个数，内存不足以容纳这 20 亿个整数。

分析：

• 一个数字的状态只有三种，分别为不存在，只有一个，有重复。因此，我们只需要 2 bit 就可以对一个数字的状态进行存储了，假设我们设定一个数字不存在为 00，存在一次 01，存在两次及其以上为 11。那我们大概需要存储空间 2G 左右。

• 接下来的任务就是把这 20 亿个数字放进去（存储），如果对应的状态位为 00，则将其变为 01，表示存在一次；如果对应的状态位为 01，则将其变为 11，表示出现多次；如果为 11，则对应的状态位保持不变，仍表示出现多次。

• 最后，统计状态位为01的个数，就得到了不重复的数字个数，两次遍历，时间复杂度为O(n)。

附： Bitmap

基本原理及要点：

• 原理：Bitmap 的基本思想就是用一个 bit 位来标记某个元素对应的 Value，而 Key 即是该元素。由于采用了 Bit 为单位来存储数据，因此在存储空间方面，可以大大节省。

• 特点：节约空间。并且位运算速度快。假设有这样一个需求：在 20 亿个随机整数中找出某个数 m 是否存在其中，并假设 32 位操作系统，4G 内存，那么：

  • 在 Java 中，int 占 4 字节，1 字节 = 8 位（1 byte = 8 bit）

  • 如果每个数字用 int 存储，那就是 20 亿个 int，因而占用的空间约为 2000000000*4/1024/1024/1024 ≈ 7.45G

  • 如果按位存储，那么 20 亿个数就是 20 亿位，占用空间约为 2000000000/8/1024/1024/1024 ≈ 0.233G

• 实现：每一位表示一个数，0 表示不存在，1 表示存在，这正符合二进制。因此可以很容易用下图表示 {1,2,4,6} 这几个数：

• 例子：

  • 已知某个文件内包含一些电话号码，每个号码为 8 位数字，统计不同号码的个数。8 位最多 99 999 999，大概需要 99m 个 bit，大概 10 几 M 字节的内存即可。

  • 2.5 亿个整数中找出不重复的整数的个数，内存空间不足以容纳这 2.5 亿个整数。将 Bitmap扩展一下，用 2 bit 表示一个数即可，0 表示未出现，1 表示出现一次，2 表示出现 2 次及以上。或者不用 2 bit 来进行表示，用两个 Bitmap 实现这个。

适用范围：

• 快速查找

• 判重

• 删除