bit array
An array of single bits, each 0 or 1, used to record yes-or-no facts very compactly.
In more detail
A Bloom filter of m bits is a bit array plus k hash functions. More bits for the same number of items mean fewer false positives. The course models the bits with a Python list of booleans for clarity; a real filter packs eight bits per byte.
Related terms
- Bloom filter — A compact, probabilistic set that can say "definitely not present" or "probably present", using a bit array and several hash functions.
- bit — The smallest unit of data: a single binary digit that is either 0 or 1.
Taught in
- Bloom Filters: Membership Without The Data — Algorithms & Data Structures for Working Engineers