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:
- Xor8 from https://github.com/FastFilter/xorfilter, written in golang.
- Fuse8 and Fuse16 from https://github.com/FastFilter/xor_singleheader written in C.
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.