关于 Bitmap 的疑惑

[nekolr]

看了好多博客，很多博客都举了类似这么一个例子：有 40 亿个不重复且无序的无符号整数，如何判断一个整数是否在这 40 亿个整数中，要求使用的内存不超过 2GB。

分析中指出：

要使用 Bitmap 算法，在 java 中一个 int 类型占用 4 个字节，因此需要申请一个 int 数组为长度为 1 + N/32 即可存储完这些数据，其中 N 代表数据的总量。

这里有一个疑惑就是，Bitmap 存储时，元素的本身应该就是 key，value 值为 1 或者 0。那么如果这 40 亿个数，在没有说明最大值的情况下，如何得出的所需容量呢？难道不是应该根据最大值来分配容量的么？

[nekolr]

哭了，憋得难受

[Mutoo]

一个无符号整型占 32bits （ 4bytes ），即可以表示 32 个数字是否存在，同理 N 个数只要 ceil(N/32) 个 int 来表示。

[Lime]

你理解的没错, 是要根据最大值. 别人 blog 可以借鉴, 但不一定都是正确的.

[nekolr]

@Mutoo 我知道一个字节可以表示 32 个数字是否存在，但是怎么确定映射关系呢？就是说怎么知道你每一位上存放的是哪个整数？

[misaka19000]

整数指的是 int 类型的数字，2 ^ 3 = 4294967296 > 40 亿

[misaka19000]

上面写错了，是 2 ^ 32

[nekolr]

@misaka19000 没明白您的意思，能麻烦说详细一点吗，谢谢啦

[EminemW]

用 hash 不就能确定位置了

[nekolr]

@Mutoo 难道不应该是根据下标确定是哪个整数吗？比如数字 4，则放在第 4 个 bit 位上，将值置为 1

[misaka19000]

不清楚你看的是什么介绍，我建议你看一下吴军的这篇博客，讲的很清晰

https://china.googleblog.com/2007/07/bloom-filter_7469.html

[nekolr]

@misaka19000 谢谢！

[Mutoo]

@nekolr 题目里有几个数字：40 亿 < 无符号整型(最大为 2^32) < 内存限制 2GB=2*1024*1024*1024*8bits=(2^34bits ）
其实就是考你怎么在 2GB 里放下最多 2^32 个数字。

[Mutoo]

@Mutoo 准确的说不是放下“数字”本身，而是标记这个数字是否存在。

[nekolr]

@Mutoo 有点明白了，我没从题意出发，只是老是从 bitmap 的角度出发了，谢谢！

[Mithril]

- 简单的说就是你得设计一个算法，将这 40 亿的数字唯一映射到 40 亿 bit 上。
- 也就是一个特化过的无冲突 hash 算法，给每个数字分配了一个 index。
- 实际上你这个算法在做的就是压缩数据
- 本质上是你先把数据集合做一遍压缩，并且把你的目标数据也压缩一下，然后在压缩过的数据集合里找你这个目标数据。
然而这个压缩过程必须是无损的，否则会有概率误判。除非你的数据集合特征非常良好，不然设计不出来无损压缩算法，也就没办法真正准确判断是否存在。
但是，你既然都能无损压缩了，最开始为啥非得存储这没压缩过的原始数据来着？一般来说这种情况下存储原始数据无非是用空间换时间，可你也根本没换出来。
这种东西看看扩展一下思路就可以了，多数都跟国内数学教材一样，为了解释一个概念编造几道例题。但这些例题都是特化过的，没必要纠结它们究竟有用没用。

[nekolr]

@Mithril 非常谢谢！解惑了！