A Bloom filter is a space-efficient probabilistic data structure used to test whether an element is a member of a set. It can quickly indicate if an item is definitely not in the set or possibly in the set, but it may produce false positives. Blossom implements several Bloom filters. All use the FNV Hash function and the optimization described by Kirsch and Mitzenmacher.
- Source
Classes
Methods
(static) calculateSize(capacity, errorRate) → {number}
Determines the appropriate size attribute given a capacity and error rate.
| Name | Type | Description |
|---|---|---|
capacity | number | Capacity of a Bloom filter |
errorRate | number | Acceptable error ratio for filter |
- Source
- Type:
- number
(inner) calculateSlices(size, capacity) → {number}
Determines how many slices the filter should use for hashing.
| Name | Type | Description |
|---|---|---|
size | number | Size of the underlying module:blossom/bitfield~Bitfield |
capacity | number | Capacity of a Bloom filter |
- Source
- Type:
- number
(inner) calulateHashes(key, size, slices) → {Array.<number>}
Calculates the hashes for an item in a Bloom filter.
| Name | Type | Description |
|---|---|---|
key | string | | The item to hash |
size | number | The size of the resulting hash |
slices | number | Total slices to use for hashing |
- Source
- Type:
- Array.<number>