写在前面

面试经常会被问到：如何从海量数据中判断某个数据是否存在。

搞大数据的工作者一般也经常遇到判断海量记录中是否存在某个记录，或者统计某个记录出现了多少次。

大家很容易想到布隆过滤器，但是布隆过滤器有一定的错误率。今天讲一讲如何用Bitmap和Roaringmap从海量数据中判断某个数据是否存在

Bitmap

bitmap比较简单，就是用一个 bit 来标记某个元素对应的 Value，而 Key 即是该元素，每个用户只占用一个bit

例如1000w条数据，就用一个大小为1000w个bit的数组表示，数组的下标就是元素，值是0表示不存在，1表示存在。总共需要内存：10000000/8/1024/1024 约等于 1.2MB左右。这点内存几乎可以忽略不计。

看到这里读者可能会觉得，用1.2MB的内存就能从1000w条数据中判断某条数据是否存在，太划算了，太厉害了。

但是这里有一个前提，就是数据大小是[0,1000w]，如果有一个数据集，只有一个元素6740413579666840，用这种方法的话需要的内存是：6740413579666840/8/1024/1024 约等于 803519914MB，这么小的数据集就占用这么大的内存，你还会觉得划算吗？

但是如果不用这么大的内存，就无法实现需求了。

很明显，Bitmap是受最大值的影响的，最大值觉得了占用多少内存。对于上面6740413579666840这种情况，Bitmap已经无法满足需求了，下面该Roaringmap出场了。

Roaringmap

大概思路

将 32bit int（无符号的）类型数据划分为 2^16 个桶，即最多可能有216=65536个桶，论文内称为container。用container来存放一个数值的低16位
在存储和查询数值时，将数值 k 划分为高 16 位和低 16 位，取高 16 位值找到对应的桶，然后在将低 16 位值存放在相应的 Container 中（存储时如果找不到就会新建一个）

比如要将31这个数放进roarigbitmap中，它的16进制为：0000001F,前16位为0000，后16为001F。
所以先需要根据前16位的值：0，找到它对应的通的编号为0，然后根据后16位的值：31，确定这个值应该放到桶中的哪一个位置，如下图所示。

Roaringmap主要特性：

Roaring bitmaps：Roaringmap 的基础是 Roaring bitmaps。Roaring bitmaps 是一种压缩数据结构，用于表示大型无重复整数集合。它将整数范围分成不同的段，每个段都经过压缩以节省空间。Roaring bitmaps 还支持快速的位操作，如并集、交集和差集，这使得在大规模数据集上执行这些操作变得高效。
分段存储：Roaringmap 将整数范围分成多个段，每个段被称为一个桶。每个桶存储一段连续的整数范围。这种分段存储的方式有助于提高压缩效率，因为可以根据整数范围的密度来选择合适的压缩算法。
区间编码：在 Roaring bitmaps 中，整数范围被编码成区间。例如，一个连续的整数范围 [100, 200] 可能会被编码成一个区间 (100, 200)。这种区间编码可以节省空间，因为连续的整数范围可以使用更少的位数来表示。
位操作：Roaringmap 支持在整个数据集合上执行各种位操作，如并集、交集和差集。这些操作可以在不同的 Roaring bitmaps 之间执行，以实现对整个数据集合的操作。

Roaringmap主要用于高效的存储大规模稀疏数据集合。

container（小桶）的类型

在roaringbitmap中共有4种小桶：

ArrayContainer（数组容器）：
特点：ArrayContainer 是 Roaringmap 中最基本的 container。它使用一个数组来存储整数，通常用于表示小范围的整数集合。
作用：适用于稀疏数据集合或者整数范围比较小的情况。由于 ArrayContainer 存储的数据量较少，因此可以快速执行插入、删除和查找操作。
BitmapContainer（位图容器）：
- 特点：BitmapContainer 使用位图来表示整数集合。位图中的每一位对应一个整数，若该位为 1，则表示整数集合中包含该整数；若该位为 0，则表示整数集合中不包含该整数。
- 作用：适用于表示大范围的整数集合。BitmapContainer 可以高效地执行位操作，如并集、交集和差集，因此在 Roaringmap 中起着重要的作用。
RunContainer（运行容器）：
- 特点：RunContainer 使用运行（run）的方式来表示整数集合。运行是指一段连续的整数范围，例如 [100, 200]。RunContainer 存储连续的整数范围，而不是单个整数。
- 作用：适用于表示连续的整数范围或者存在大量连续整数的情况。RunContainer 可以通过存储连续的整数范围来减少存储空间，因此在某些情况下可以提供更好的压缩效果。
Bitmap和Run混合容器（HybridContainer）：
- 特点：HybridContainer 是一种混合容器，结合了 BitmapContainer 和 RunContainer 的优点。它根据数据的特性动态选择 BitmapContainer 或 RunContainer 来存储整数集合，以实现更好的压缩效果和查询性能。
- 作用：适用于包含各种类型整数集合的情况。HybridContainer 可以根据数据的特性动态选择合适的容器类型，从而兼顾存储空间和性能。