# `Talan.BloomFilter`
[🔗](https://github.com/preciz/talan/blob/v1.0.0/lib/talan/bloom_filter.ex#L1)

Bloom filter implementation with **safe concurrent access**,
powered by the [:atomics](http://erlang.org/doc/man/atomics.html) module.

"A Bloom filter is a space-efficient probabilistic data structure,
conceived by Burton Howard Bloom in 1970,
that is used to test whether an element is a member of a set"

[Bloom filter on Wikipedia](https://en.wikipedia.org/wiki/Bloom_filter#CITEREFZhiwangJungangJian2010)

## Credit

Partly inspired by [Blex](https://github.com/gyson/blex)

## Features

  * Fixed-size Bloom filter
  * Concurrent reads and writes
  * Custom and default hash functions
  * Merge multiple Bloom filters into one
  * Intersect multiple Bloom filters into one
  * Estimate number of unique elements
  * Estimate current false positive probability

## Examples

    iex> b = Talan.BloomFilter.new(1000)
    iex> b |> Talan.BloomFilter.put("Barna")
    iex> b |> Talan.BloomFilter.member?("Barna")
    true
    iex> b |> Talan.BloomFilter.member?("Kovacs")
    false

# `bits_info`

```elixir
@type bits_info() :: %{
  total_bits: pos_integer(),
  set_bits_count: non_neg_integer(),
  set_ratio: float()
}
```

# `option`

```elixir
@type option() ::
  {:false_positive_probability, float()}
  | {:hash_functions, [Talan.hash_function()]}
```

# `options`

```elixir
@type options() :: [option()]
```

# `t`

```elixir
@type t() :: %Talan.BloomFilter{
  atomics_ref: reference(),
  filter_length: pos_integer(),
  hash_functions: [Talan.hash_function(), ...]
}
```

# `bits_info`

```elixir
@spec bits_info(t()) :: bits_info()
```

Returns a map representing the bit state of the `atomics_ref`.

Use this for debugging purposes.

## Examples

    iex> b = Talan.BloomFilter.new(1000)
    iex> b |> Talan.BloomFilter.bits_info()
    %{total_bits: 9600, set_bits_count: 0, set_ratio: 0.0}

# `cardinality`

```elixir
@spec cardinality(t()) :: non_neg_integer()
```

Returns a non-negative integer representing the estimated number of unique
elements in the filter.

A saturated filter has no unset bits, so its cardinality cannot be estimated
reliably; in that case this function returns a finite fallback value.

## Examples

    iex> b = Talan.BloomFilter.new(1000)
    iex> b |> Talan.BloomFilter.cardinality()
    0
    iex> b |> Talan.BloomFilter.put("Barna")
    iex> b |> Talan.BloomFilter.cardinality()
    1
    iex> b |> Talan.BloomFilter.put("Barna")
    iex> b |> Talan.BloomFilter.cardinality()
    1
    iex> b |> Talan.BloomFilter.put("Kovacs")
    iex> b |> Talan.BloomFilter.cardinality()
    2

# `clear`

```elixir
@spec clear(t()) :: t()
```

Clears every bit in `bloom_filter` and returns the same filter.

The filter is reset in place without reallocating its atomics reference.
Clearing individual atomic words is safe during concurrent access, but the
filter is not cleared as one atomic operation. Concurrent reads may observe a
partially cleared filter, and concurrent writes may be cleared or remain set
depending on their timing.

## Examples

    iex> b = Talan.BloomFilter.new(1000)
    iex> Talan.BloomFilter.put(b, "Barna")
    iex> Talan.BloomFilter.clear(b) == b
    true
    iex> Talan.BloomFilter.member?(b, "Barna")
    false

# `deserialize`
*since 0.1.3* 

```elixir
@spec deserialize(binary()) :: t()
```

Deserializes a binary into a Bloom filter.

This function takes a binary that was previously created by `serialize/1`
and reconstructs the Bloom filter structure.

The modules and code versions defining the serialized hash functions must be
available and compatible.

## Examples

    iex> bloom_filter = Talan.BloomFilter.new(1000)
    iex> serialized = Talan.BloomFilter.serialize(bloom_filter)
    iex> deserialized = Talan.BloomFilter.deserialize(serialized)
    iex> is_struct(deserialized, Talan.BloomFilter)
    true

# `false_positive_probability`

```elixir
@spec false_positive_probability(t()) :: float()
```

Returns a float representing the current estimated
false-positive probability.

## Examples

    iex> b = Talan.BloomFilter.new(1000)
    iex> b |> Talan.BloomFilter.false_positive_probability()
    0.0 # fpp zero when bloom filter is empty
    iex> b |> Talan.BloomFilter.put("Barna") # fpp increases
    iex> b |> Talan.BloomFilter.put("Kovacs")
    iex> fpp = b |> Talan.BloomFilter.false_positive_probability()
    iex> fpp > 0 && fpp < 1
    true

# `hash_term`

```elixir
@spec hash_term(t(), term()) :: [non_neg_integer(), ...]
```

Hashes `term` with all `hash_functions` of `%Talan.BloomFilter{}`. Custom hash
functions must return non-negative integers.

Returns a list of hashed values.

## Examples

    iex> b = Talan.BloomFilter.new(1000, hash_functions: [fn _term -> 42 end])
    iex> Talan.BloomFilter.hash_term(b, :any_term_can_be_hashed)
    [42]

# `intersection`

```elixir
@spec intersection([t(), ...]) :: t()
```

Intersects the atomics of multiple `%Talan.BloomFilter{}` structs into one new struct.

All filters must have the same size and use the same hash functions.

Returns a new `%BloomFilter{}` struct whose set bits are the intersection of
the Bloom filters in the `list`.

## Examples

    iex> hash_functions = [fn term -> :erlang.phash2(term) end]
    iex> b1 = Talan.BloomFilter.new(1000, hash_functions: hash_functions)
    iex> b1 |> Talan.BloomFilter.put("GitHub")
    iex> b2 = Talan.BloomFilter.new(1000, hash_functions: hash_functions)
    iex> b2 |> Talan.BloomFilter.put("GitHub")
    iex> b2 |> Talan.BloomFilter.put("Octocat")
    :ok
    iex> b3 = Talan.BloomFilter.intersection([b1, b2])
    iex> b3 |> Talan.BloomFilter.member?("GitHub")
    true
    iex> b3 |> Talan.BloomFilter.member?("Octocat")
    false

# `member?`

```elixir
@spec member?(t(), any()) :: boolean()
```

Checks for membership of `term` in `bloom_filter`.

Returns `false` if the term is definitely absent.
Returns `true` if the term may be present.

## Examples

    iex> b = Talan.BloomFilter.new(1000)
    iex> b |> Talan.BloomFilter.member?("Barna Kovacs")
    false
    iex> b |> Talan.BloomFilter.put("Barna Kovacs")
    iex> b |> Talan.BloomFilter.member?("Barna Kovacs")
    true

# `merge`

```elixir
@spec merge([t(), ...]) :: t()
```

Merges the atomics of multiple `%Talan.BloomFilter{}` structs into one new struct.

All filters must have the same size and use the same hash functions.

Returns a new `%Talan.BloomFilter{}` struct whose set bits are the merged set bits of
the bloom filters in the `list`.

## Examples

    iex> hash_functions = [fn term -> :erlang.phash2(term) end]
    iex> b1 = Talan.BloomFilter.new(1000, hash_functions: hash_functions)
    iex> b1 |> Talan.BloomFilter.put("GitHub")
    iex> b2 = Talan.BloomFilter.new(1000, hash_functions: hash_functions)
    iex> b2 |> Talan.BloomFilter.put("Octocat")
    :ok
    iex> b3 = Talan.BloomFilter.merge([b1, b2])
    iex> b3 |> Talan.BloomFilter.member?("GitHub")
    true
    iex> b3 |> Talan.BloomFilter.member?("Octocat")
    true

# `new`

```elixir
@spec new(pos_integer(), options()) :: t()
```

Returns a new `%Talan.BloomFilter{}` for the desired `cardinality`.

`cardinality` is the expected number of unique items. Duplicate items do not
count toward the expected cardinality.

Raises `ArgumentError` if `cardinality` or any option is invalid.

## Options
  * `:false_positive_probability` - a float, defaults to 0.01
  * `:hash_functions` - a list of functions that each accept a term and return a
    non-negative integer, defaults to randomly seeded Murmur

## Examples

    iex> bloom_filter = Talan.BloomFilter.new(1_000_000)
    iex> bloom_filter |> Talan.BloomFilter.put("Barna Kovacs")
    :ok

# `put`

```elixir
@spec put(t(), any()) :: :ok
```

Puts `term` into `bloom_filter`, a `%Talan.BloomFilter{}` struct.

After insertion, `member?/2` will always return `true` for this `term`.

Returns `:ok`.

## Examples

    iex> b = Talan.BloomFilter.new(1000)
    iex> b |> Talan.BloomFilter.put("Chris McCord")
    :ok
    iex> b |> Talan.BloomFilter.put("Jose Valim")
    :ok

# `required_filter_length`

```elixir
@spec required_filter_length(pos_integer(), float()) :: pos_integer()
```

Returns the required bit count given

* `cardinality` - Number of unique elements that will be inserted
* `false_positive_probability` - Desired false positive probability of membership

[Wikipedia - Bloom filter - Optimal number of hash functions](https://en.wikipedia.org/wiki/Bloom_filter#Optimal_number_of_hash_functions)

## Examples

    iex> Talan.BloomFilter.required_filter_length(10_000, 0.01)
    95851

# `required_hash_function_count`

```elixir
@spec required_hash_function_count(float()) :: pos_integer()
```

Returns the required number of hash functions for the
given `false_positive_probability`.

[Wikipedia - Bloom filter - Optimal number of hash functions](https://en.wikipedia.org/wiki/Bloom_filter#Optimal_number_of_hash_functions)

## Examples

    iex> Talan.BloomFilter.required_hash_function_count(0.01)
    7
    iex> Talan.BloomFilter.required_hash_function_count(0.001)
    10
    iex> Talan.BloomFilter.required_hash_function_count(0.0001)
    14

# `serialize`
*since 0.1.3* 

```elixir
@spec serialize(t()) :: binary()
```

Serializes the Bloom filter into a binary.

This function converts the Bloom filter structure into a binary format,
which can be used for storage or transmission.

The binary embeds the filter's hash functions and is only portable to
environments running compatible code. It is not a stable interchange format
across code upgrades.

## Examples

    iex> bloom_filter = Talan.BloomFilter.new(1000)
    iex> serialized = Talan.BloomFilter.serialize(bloom_filter)
    iex> is_binary(serialized)
    true

---

*Consult [api-reference.md](api-reference.md) for complete listing*