@webdeveric/ts-data-structures
    Preparing search index...

    Class BloomFilter<Type>

    Probabilistic set membership structure. Trades exactness for space: add is O(k), has is O(k) with no false negatives but a tunable false-positive rate, and storage is a fixed-size bit array regardless of how many elements are added.

    Uses the Kirsch-Mitzenmacher double-hashing technique to derive all numHashes indices from a single two-part hash, avoiding the need for k independent hash functions.

    const filter = new BloomFilter<string>({
      size: 1024,
      numHashes: 4,
      hash: stringHash,
    });
    filter.add('foo');
    filter.has('foo'); // true
    filter.has('bar'); // false (or true, at the configured false-positive rate)

    https://en.wikipedia.org/wiki/Bloom_filter

    Type Parameters

    • Type
    Index

    Accessors

    fillRatio

    Methods

    optimal add has reset

    Accessors

    • get fillRatio(): number

      Fraction of bits currently set (0-1); rises with false-positive rate as the filter fills.

      Returns number

    Methods

    • Derives the optimal size and numHashes for a given expected workload.

      Type Parameters

      • Type

      Parameters

      • expectedItems: number
      • falsePositiveRate: number
      • hash: (value: Type) => HashPair

      Returns BloomFilter<Type>

      const filter = BloomFilter.optimal(10_000, 0.05, yourHashFunction);

    • Adds value to the filter by setting its derived bits.

      Parameters

      Returns void

    • Tests whether value may be in the filter.

      • false is definitive (never in the set);
      • true is probabilistic (may be a false positive).

      Parameters

      Returns boolean

    • Clears the filter by resetting the underlying bit array.

      Returns void

    Settings

    Member Visibility

    On This Page

    Accessors
    Methods