Roaring Bitmap

A compressed bitmap for large sets of integers, with fast union, intersection, and difference. Unlike every other structure on this site, Roaring Bitmap is exact, not probabilistic: it never has false positives or negatives. It's included as a deliberate, one-off scope exception because it shares the same "bit array at scale" component family and audience as Bloom Filter and HyperLogLog above.

How it works

Every 32-bit integer is split into a 16-bit key (its high bits, selecting one of up to 65,536 chunks) and a 16-bit low value (its position within that chunk, 0–65,535). Each chunk stores its members in whichever of three container formats is cheapest for what it actually holds:

  • array: a sorted list of 16-bit values, 2 bytes each. Cheapest when the chunk is sparse.
  • bitmap: a fixed 65,536-bit (8 KB) bitmap. Cheapest once the chunk gets dense, regardless of exactly how dense.
  • run: a sorted list of (start, length) ranges, 4 bytes each. Cheapest when members form long contiguous runs, e.g. after adding a whole numeric range.

array ↔ bitmap conversion happens automatically the moment a chunk's cardinality crosses the threshold below (real implementations default this to 4,096: the point where a 2-byte-per-value array outgrows the fixed 8 KB bitmap). run containers are different: real Roaring never guesses at run-encoding on every insert, since that costs a scan for very little benefit as a set grows one item at a time. Instead an explicit optimize() pass (runOptimize() in most libraries) re-checks every chunk and switches it to whichever format is smallest right now. Try addRange below, then hit "Optimize" to see a dense range collapse into a single run.

Interactive demo

Cardinality0
Chunks0
Encoded size0 B
vs. plain int32 array—
Empty. Add a value below to create the first chunk.
No operations yet. Try adding an item above.

Set operations

Union, intersection, and difference are where Roaring earns its keep at scale: production implementations align containers by key and combine them pairwise (array-vs-array, bitmap-vs-bitmap, ...) without ever materializing the full integer list. This demo computes the same results via a simple value-set combine for clarity: correct, but not representative of the container-aligned performance trick.

A ∪ B (6)1, 2, 3, 4, 70000, 200000
A ∩ B (3)2, 3, 70000
A − B (1)1

API surface

OperationDescriptionComplexity
new RoaringBitmap(arrayMaxSize?)Empty bitmap; arrayMaxSize sets the array↔bitmap conversion threshold (default 4096).O(1)
add(value): voidInsert a 32-bit integer, converting its chunk's container if the threshold is crossed.O(log n) array / O(1) bitmap / O(runs) run
has(value): booleanExact membership test, never a false positive or negative.O(log n) array / O(1) bitmap / O(log runs) run
remove(value): voidRemove a value; drops the chunk entirely once it becomes empty.O(n) array / O(1) bitmap / O(runs) run
addRange(start, end): voidBulk-insert every integer in an inclusive range, across chunk boundaries if needed.O(end − start)
optimize(): voidRe-picks the cheapest container (array/bitmap/run) per chunk given its current contents.O(n) per chunk
union/intersection/difference(a, b): RoaringBitmapSet operations; production Roaring aligns and combines matching containers directly.O(containers) in production; O(n) here
cardinality(): numberTotal number of values across all chunks.O(chunks)

References

Original papers

Library implementations

Real-world use cases