Crate xorfilter[][src]

Expand description

Library implements xor-filter.

Provides hasher types:

  • NoHash, to be used when hash feature is not needed on Xor8, Fuse8 and Fuse16 types. Note that type methods that accept parametrized key cannot be used.
  • BuildHasherDefault is the default hasher when H is not supplied. Note that DefaultHasher uses an unspecified internal algorithm and so its hashes should not be relied upon over releases.

Refer to original implementation under github.com/FastFilter to learn the differences between Xor8, Fuse8 and Fuse16 filters. Otherwise, all the types provides similar methods.

Handling duplicates

  • Fuse16 and Xor8 implementation uses BTreeMap to make sure all the digests generated from keys are unique, this avoids duplicates but decreases the build performance significantly.
  • Fuse8 implementation computes duplicates on the fly leading to significantly better build performance. On the other hand, Fuse8 cannot handle more than few duplicates.

This is ported from its original implementation:

Structs

Wrapper type for std::hash::BuildHasherDefault, that uses DefaultHasher as the hasher.

Type Fuse8 is probabilistic data-structure to test membership of an element in a set.

Type Fuse16 is probabilistic data-structure to test membership of an element in a set.

NoHash type skips hashing altogether.

Type Xor8 is probabilistic data-structure to test membership of an element in a set.

Enums

Error variants that are returned by this package’s API.

Type Definitions

Type alias for Result return type, used by this package.