Efficient Integer Existence Checking Using Bitmap, Bloom Filter, and Redis

When needing to determine whether an integer exists among ten million numbers whose values range from 1 to 100 million, several approaches can be considered, including hash tables, boolean arrays, and bitmaps.

1. Hash Table

Using a hash table can store the numbers, but each entry requires both the integer (≈4 bytes) and a pointer, roughly doubling memory consumption to about 80 MB for ten million entries.

2. Boolean Array

A boolean array of length ten million can mark presence with true/false, but each boolean occupies a full byte in Java, still consuming about 40 MB.

3. Bitmap

By representing each possible value with a single bit, a bitmap reduces memory dramatically: for a range of 1‑100 million the bitmap needs only 100 million bits (~12 MB). The article explains how to compute the byte index and bit position using bit‑wise operations and provides Java code for setting and checking bits.

public void set(int number) {
    int index = number >> 3;
    int position = number & 0x07;
    bytes[index] |= 1 << position;
}
public boolean contain(int number) {
    int index = number >> 3;
    int position = number & 0x07;
    return (bytes[index] & (1 << position)) != 0;
}

A complete MyBitMap class is also shown, illustrating initialization, setting, and querying.

4. Bloom Filter

When the value range expands to 1‑1 billion, a bitmap would require ~120 MB, so a Bloom filter is introduced. By applying multiple hash functions and a bit array, it offers space‑efficient probabilistic membership testing with a controllable false‑positive rate. The article presents the standard formulas for optimal bit array size m , number of hash functions k , and false‑positive probability.

5. Redis Bitmap

Redis provides native bitmap commands ( SETBIT, GETBIT, BITCOUNT, BITOP) that can be used for real‑time analytics such as user sign‑in tracking, daily active users, and online member counting. Example CLI snippets demonstrate setting bits for user IDs, counting set bits, and combining bitmaps with logical operations.

SETBIT user18 1 1
SETBIT user18 2 1
BITCOUNT user18   # returns 4
BITOP OR active_user 20201021 20201022
BITCOUNT active_user   # returns 2

Finally, the article shows how to use Guava’s BloomFilter in Java, including Maven dependency and a short example that creates a filter for 100 integers with a 1 % false‑positive rate.

BloomFilter<Integer> bloomFilter = BloomFilter.create(
    Funnels.integerFunnel(),
    100,
    0.01);
bloomFilter.put(1);
bloomFilter.mightContain(1); // true

The overall conclusion is that bitmaps and Bloom filters provide high‑performance, low‑memory solutions for large‑scale membership queries, especially when exact accuracy can tolerate a small false‑positive probability.