ThinkerQAQ

NOTE

2.11 BitMap

1. BitMap是什么 - 又叫位图 - 把数据存放在一个以bit为单位的数据结构里，每位都只有0和1两个值。为0的时候，证明值不存在；为1的时候说明存在。 1.1. 举例 这个时候假如我们要存放2 4 6 8 9 10 17 19 21这些数字到我们的BitMap里，我们只需把对应的位设置为1就

Data Structures & Algorithms创建于 更新于 historical

这是历史学习笔记，可能存在过时或不完整的理解。

1. BitMap是什么

  • 又叫位图
  • 把数据存放在一个以bit为单位的数据结构里，每位都只有0和1两个值。为0的时候，证明值不存在；为1的时候说明存在。

1.1. 举例

这个时候假如我们要存放2 4 6 8 9 10 17 19 21这些数字到我们的BitMap里，我们只需把对应的位设置为1就可以了。

[0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 1 1 0 1 0 1 0 1 0]

2. 为什么需要BitMap

假设我们有1千万个整数，整数的范围在1到1亿之间。如何快速查找某个整数是否在这1千万个整数中

  • 如果使用HashMap实现，那么需要占用至少40MB
  • 使用BitMap实现，那么只需要 1 亿个二进制位，也就是 12MB。因此相对于HashMap节省了空间

3. BitMap改进：BloomFilter

4. 参考