2.11 BitMap

1. What Is BitMap

• Also called a bitmap
• Store data in a bit-based data structure, where every bit has only two values: 0 and 1. A value of 0 means the value does not exist; 1 means it exists.

1.1. Example

Suppose we want to store the numbers 2, 4, 6, 8, 9, 10, 17, 19, and 21 in a BitMap. We only need to set the corresponding bits to 1.

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

2. Why BitMap Is Needed

Suppose we have 10 million integers whose values range from 1 to 100 million. How can we quickly determine whether an integer is among those 10 million integers?

• If HashMap is used, it takes at least 40 MB
• If BitMap is used, only 100 million bits are needed, which is about 12 MB. So it saves space compared with HashMap

3. BitMap Improvement: BloomFilter

• BloomFilter.md

4. References

• BitMap Principles and Implementation - CSDN
• Bitmap: How to Deduplicate URLs in a Web Crawler? - CSDN