package bloomf

  1. Overview
  2. Docs
package bloomf
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module BloomfSource

Bloom filters

bloomf is an implementation of Bloom filters in OCaml.

Bloom filters are memory and time efficient data structures allowing probabilistic membership queries in a set. A query negative result ensures that the element is not present in the set, while a positive result might be a false positive, i.e. the element might not be present and the BF membership query can return true anyway. Internal parameters of the BF allow to control its false positive rate depending on the expected number of elements in it.

Generic interface

Sourcetype 'a t

The type of the Bloom filter.

Sourceval create : ?error_rate:float -> int -> 'a t

create ~error_rate size creates a fresh BF for which expected false positive rate when filled with size elements is error_rate.

Sourceval add : 'a t -> 'a -> unit

add t e adds e to t.

Sourceval mem : 'a t -> 'a -> bool

mem t e is true if e is in t.

Sourceval clear : 'a t -> unit

clear t clears the contents of t.

Sourceval size_estimate : 'a t -> int

size_estimate t is an approximation of the number of elements stored in the bloom filter. Please note that this operation is costly (see benchmarks).

Functorial interface

The functorial interface allows you to specify your own hash function.

Sourcemodule type Hashable = sig ... end

The input interface for Bloomf.Make.

Sourcemodule Make (H : Hashable) : sig ... end

The output interface for Bloomf.Make.