Bitmap Principles and Applications

A bitmap is an efficient data structure that uses a bit array to represent a set of data. It is particularly suitable for handling existence judgment and deduplication problems involving large-scale integers. I will start from the basic concepts and gradually explain its implementation principles and practical applications.

I. Basic Concepts of Bitmaps
The core idea of a bitmap is to use one bit to represent the existence state of a number. Each bit has two states: 0 indicates the number does not exist, and 1 indicates the number exists. For example, to represent the number set {2, 5, 8}, 9 bits (indexes 0-8) are needed:
Index: 0 1 2 3 4 5 6 7 8
Bit: 0 0 1 0 0 1 0 0 1

II. Bitwise Operation Basics
Implementing a bitmap requires mastery of three basic bitwise operations:

1. Locating a specific bit: The byte index for number n is n/8 (or n>>3), and the bit offset is n%8 (or n&0x07).
2. Setting a bit to 1: Use the bitwise OR operation |, e.g., byte |= (1 << offset).
3. Checking if a bit is 1: Use the bitwise AND operation &, e.g., (byte & (1 << offset)) != 0.

III. Specific Implementation Steps of a Bitmap
Assuming we want to represent numbers in the range 0 to 99999:

1. Memory Allocation Calculation

• Need 100,000 bits
• Total bytes = ceil(100000/8) = 12,500 bytes ≈ 12.2KB
• Compared to storing 100,000 ints (400KB), this saves 97% of space.

2. Key Operation Implementation

• Add number n:
  byteIndex = n / 8 // Determine byte position
  bitOffset = n % 8 // Determine bit offset
  bitmap[byteIndex] |= (1 << bitOffset) // Set corresponding bit to 1

• Check if number n exists:
  byteIndex = n / 8
  bitOffset = n % 8
  return (bitmap[byteIndex] & (1 << bitOffset)) != 0

IV. Practical Application Scenarios

1. Big Data Deduplication
   Case: Counting the deduplicated number of 1 billion IP addresses (IP converted to 32-bit integer)

• Traditional method: Using a HashSet requires about 4GB of memory.
• Bitmap method: Requires 2^32 bits = 512MB of memory.
• Saves 87.5% of memory space.

2. Database Index Optimization
   Creating bitmap indexes for low-cardinality columns (e.g., gender, status code) in databases:

• Each value corresponds to a bitmap.
• Multi-condition queries can be quickly merged via bitwise operations.
  Example: Querying "Gender = Male AND Status = Active"
  Perform a bitwise AND operation directly on the male bitmap and the active bitmap.

3. Foundation of Bloom Filters
   Bitmaps are the underlying storage structure of Bloom Filters. Bloom Filters use multiple hash functions to map elements to different positions in the bitmap.

V. Limitations of Bitmaps and Solutions

1. Sparse Data Problem
   When data is sparse (e.g., storing {1, 1000000}), the bitmap still requires 125KB of memory.
   Solution: Use compressed bitmaps (e.g., EWAH, Roaring Bitmap).

2. Dynamic Range Problem
   When the number range is uncertain, an expandable bitmap is needed.
   Solution: Use hierarchical bitmaps or dynamic arrays.

VI. Advanced Optimization Techniques

1. Bitwise Operation Optimization
   Use bit shifts instead of multiplication/division: n/8 becomes n>>3, n%8 becomes n&7.

2. Batch Operation Optimization
   Support batch setting and querying to reduce function call overhead.

3. Cache-Friendly Layout
   Place frequently accessed bitmap regions in contiguous memory.

Bitmaps achieve O(1) time complexity for existence judgment in specific scenarios through extreme space efficiency, making them an indispensable fundamental data structure in big data processing. Understanding how bitmaps work helps in making reasonable technical choices for memory-sensitive applications.