XorFilter | bloom-filters

XOR-Filter for 8-bits and 16-bits fingerprint length.

To use for fixed sets of elements only Inspired from @see https://github.com/FastFilter/fastfilter_java

author

Arnaud GRALL

example

const xor8 = new XorFilter(1) // default fingerprint of 8 bits
xor8.add(['a'])
xor8.has('a') // true
xor8.has('b') // false
const xor16 = new XorFilter(1, 16)
xor16.add(['a'])
xor16.has('a') // true
xor16.has('b') // false

Hierarchy

BaseFilter
- XorFilter

Index

Properties

Methods

Constructors

constructor

Accessors

Properties

ALLOWED_FINGERPRINT_SIZES

ALLOWED_FINGERPRINT_SIZES: number[] = ...

FACTOR_TIMES_100

FACTOR_TIMES_100: number = 123

HASHES

HASHES: number = 3

OFFSET

OFFSET: number = 32

_bits

_bits: number = 8

Number of bits per fingerprint

_blockLength

_blockLength: number

Size of each block (filter size / HASHES)

_filter

_filter: <internal>.Buffer[]

Buffer array of fingerprints

_hashing

_hashing: Hashing

_rng

_rng: PRNG

_seed

_seed: number

_size

_size: number

Number of elements inserted in the filter

Methods

_create

_create(elements: XorHashableInput[], arrayLength: number): void

- Defined in src/bloom/xor-filter.ts:349
Create the filter representing the elements to store. We eliminate all duplicated entries before creating the array. Follow the algorithm 2 and 3 of the paper (@see https://arxiv.org/pdf/1912.08258.pdf) Inspired by Go impl from (@see https://github.com/FastFilter/xorfilter/blob/master/xorfilter.go)

Parameters
- elements: XorHashableInput[]
  
  array of elements to add in the filter
- arrayLength: number
Returns void

Private _fingerprint

_fingerprint(hash: Long): Long

- Defined in src/bloom/xor-filter.ts:276
internal
Parameters
- hash: Long
  
  hash of the element
Returns Long

_getHash

_getHash(element: Long, seed: number, index: number): number

- Defined in src/bloom/xor-filter.ts:332
Hash the element

Parameters
- element: Long
- seed: number
- index: number
Returns number

Private _getOptimalFilterSize

_getOptimalFilterSize(size: number): number

- Defined in src/bloom/xor-filter.ts:238
internal
Parameters
- size: number
Returns number

Private _hash64

_hash64(element: Long, seed: number): Long

- Defined in src/bloom/xor-filter.ts:299
internal
Parameters
- element: Long
- seed: number
Returns Long

Private _hashable_to_long

_hashable_to_long(element: <internal>.HashableInput, seed: number): Long

- Defined in src/bloom/xor-filter.ts:288
internal
Parameters
- element: <internal>.HashableInput
- seed: number
Returns Long

Private _readBuffer

_readBuffer(buffer: <internal>.Buffer): number

- Defined in src/bloom/xor-filter.ts:255
internal
Parameters
- buffer: <internal>.Buffer
Returns number

_reduce

_reduce(hash: Long, size: number): number

- Defined in src/bloom/xor-filter.ts:317
Perform a modulo reduction using an optimiaze technique

Parameters
- hash: Long
- size: number
Returns number

add

add(elements: XorHashableInput[]): void

- Defined in src/bloom/xor-filter.ts:172
Add elements to the filter, modify the filter in place. Warning: Another call will override the previously created filter.
example
```
const xor = new XorFilter(1, 8)
xor.add(['alice'])
xor.has('alice') // true
xor.has('bob') // false
```
Parameters
- elements: XorHashableInput[]
Returns void

Static create

create(elements: XorHashableInput[], bits_per_fingerprint?: 8 | 16): XorFilter

- Defined in src/bloom/xor-filter.ts:218
Return a XorFilter for a specified set of elements

Parameters
- elements: XorHashableInput[]
- Optional bits_per_fingerprint: 8 | 16
Returns XorFilter

equals

equals(filter: XorFilter): boolean

- Defined in src/bloom/xor-filter.ts:187
Return True if the other XorFilter is equal

Parameters
- filter: XorFilter
Returns boolean

Static fromJSON

fromJSON(json: JSON): any

Inherited from BaseFilter.fromJSON
- Defined in src/base-filter.ts:91
Load an Object from a provided JSON object

Parameters
- json: JSON
  
  the JSON object to load
Returns any
Return the Object loaded from the provided JSON object

has

has(element: XorHashableInput): boolean

- Defined in src/bloom/xor-filter.ts:138
Return False if the element is not in the filter, True if it might be in the set with certain probability.

Parameters
- element: XorHashableInput
Returns boolean

nextInt32

nextInt32(): number

Inherited from BaseFilter.nextInt32
- Defined in src/base-filter.ts:73
Return a next random seeded int32 integer

Returns number

saveAsJSON

saveAsJSON(): any

Inherited from BaseFilter.saveAsJSON
- Defined in src/base-filter.ts:81
Save the current structure as a JSON

Returns any

Constructors

constructor

new XorFilter(size: number, bits_per_fingerprint?: 8 | 16): XorFilter

Overrides BaseFilter.constructor
- Defined in src/bloom/xor-filter.ts:101
Create an empty XorFilter for a number of size elements. The fingerprint length can be choosen

Parameters
- size: number
- Optional bits_per_fingerprint: 8 | 16
Returns XorFilter

Accessors

random

get random(): PRNG

Inherited from BaseFilter.random
- Defined in src/base-filter.ts:65
Get a function used to draw random number

Returns PRNG
A factory function used to draw random integer

seed

get seed(): number
set seed(seed: number): void

Inherited from BaseFilter.seed
- Defined in src/base-filter.ts:48
Get the seed used in this structure

Returns number
Inherited from BaseFilter.seed
- Defined in src/base-filter.ts:56
Set the seed for this structure

Parameters
- seed: number
  
  the new seed that will be used in this structure
Returns void

Hierarchy

Index

Properties

Methods

Constructors

Accessors

Properties

ALLOWED_FINGERPRINT_SIZES

FACTOR_TIMES_100

HASHES

OFFSET

_bits

_blockLength

_filter

_hashing

_rng

_seed

_size

Methods

_create

Parameters

elements: XorHashableInput[]

arrayLength: number

Returns void

Private _fingerprint

Parameters

hash: Long

Returns Long

_getHash

Parameters

element: Long

seed: number

index: number

Returns number

Private _getOptimalFilterSize

Parameters

size: number

Returns number

Private _hash64

Parameters

element: Long

seed: number

Returns Long

Private _hashable_to_long

Parameters

element: <internal>.HashableInput

seed: number

Returns Long

Private _readBuffer

Parameters

buffer: <internal>.Buffer

Returns number

_reduce

Parameters

hash: Long

size: number

Returns number

add

Parameters

elements: XorHashableInput[]

Returns void

Static create

Parameters

elements: XorHashableInput[]

Optional bits_per_fingerprint: 8 | 16

Returns XorFilter

equals

Parameters

filter: XorFilter

Returns boolean

Static fromJSON

Parameters

json: JSON

Returns any

has

Parameters

element: XorHashableInput

Returns boolean

nextInt32

Returns number