这是一个创建于 1915 天前的主题，其中的信息可能已经有所发展或是发生改变。
看了好多博客，很多博客都举了类似这么一个例子：有 40 亿个不重复且无序的无符号整数，如何判断一个整数是否在这 40 亿个整数中，要求使用的内存不超过 2GB。
分析中指出：
要使用 Bitmap 算法，在 java 中一个 int 类型占用 4 个字节，因此需要申请一个 int 数组为长度为 1 + N/32 即可存储完这些数据，其中 N 代表数据的总量。
这里有一个疑惑就是，Bitmap 存储时，元素的本身应该就是 key，value 值为 1 或者 0。那么如果这 40 亿个数，在没有说明最大值的情况下，如何得出的所需容量呢？难道不是应该根据最大值来分配容量的么？
 |
1
nekolr OP 哭了，憋得难受
|
 |
2
Mutoo 2019-08-28 11:19:03 +08:00
一个无符号整型占 32bits （ 4bytes ），即可以表示 32 个数字是否存在，同理 N 个数只要 ceil(N/32) 个 int 来表示。
|
 |
3
Lime 2019-08-28 11:20:00 +08:00
你理解的没错, 是要根据最大值. 别人 blog 可以借鉴, 但不一定都是正确的.
|
|
4
nekolr OP @Mutoo 我知道一个字节可以表示 32 个数字是否存在，但是怎么确定映射关系呢？就是说怎么知道你每一位上存放的是哪个整数？
|
 |
5
misaka19000 2019-08-28 11:24:19 +08:00
整数指的是 int 类型的数字，2 ^ 3 = 4294967296 > 40 亿
|
|
6
misaka19000 2019-08-28 11:24:40 +08:00
上面写错了，是 2 ^ 32
|
|
7
nekolr OP @misaka19000 没明白您的意思，能麻烦说详细一点吗，谢谢啦
|
 |
8
EminemW 2019-08-28 11:27:43 +08:00 via iPhone
用 hash 不就能确定位置了
|
|
10
misaka19000 2019-08-28 11:28:45 +08:00
|
|
11
nekolr OP @misaka19000 谢谢！
|
|
12
Mutoo 2019-08-28 11:36:41 +08:00
@nekolr 题目里有几个数字：40 亿 < 无符号整型(最大为 2^32) < 内存限制 2GB=2*1024*1024*1024*8bits=(2^34bits ）
其实就是考你怎么在 2GB 里放下最多 2^32 个数字。 |
 |
15
Mithril 2019-08-28 11:54:52 +08:00  2
- 简单的说就是你得设计一个算法，将这 40 亿的数字唯一映射到 40 亿 bit 上。
- 也就是一个特化过的无冲突 hash 算法，给每个数字分配了一个 index。 - 实际上你这个算法在做的就是压缩数据 - 本质上是你先把数据集合做一遍压缩，并且把你的目标数据也压缩一下，然后在压缩过的数据集合里找你这个目标数据。 然而这个压缩过程必须是无损的，否则会有概率误判。除非你的数据集合特征非常良好，不然设计不出来无损压缩算法，也就没办法真正准确判断是否存在。 但是，你既然都能无损压缩了，最开始为啥非得存储这没压缩过的原始数据来着？一般来说这种情况下存储原始数据无非是用空间换时间，可你也根本没换出来。 这种东西看看扩展一下思路就可以了，多数都跟国内数学教材一样，为了解释一个概念编造几道例题。但这些例题都是特化过的，没必要纠结它们究竟有用没用。 |
Select Language