pub trait FuzzyHash: Hash + Sized {
// Required method
fn fuzzy_hash(&self) -> impl ExactSizeIterator<Item = u64>;
// Provided method
fn is_range_key(&self) -> bool { ... }
}Expand description
An extension to std::hash::Hash to support values which should be partitioned and hashed into
buckets, where nearby keys will have the same hash value. This is used for existence filtering
in layer files (see Layer::maybe_contains_key).
For point-based keys, this can be the same as std::hash::Hash, but for range-based keys, the
hash can collapse nearby ranges into the same hash value. Since a range-based key may span
several buckets, FuzzyHash::fuzzy_hash must be called to split the key up into each of the
possible values that it overlaps with.
Required Methods§
Sourcefn fuzzy_hash(&self) -> impl ExactSizeIterator<Item = u64>
fn fuzzy_hash(&self) -> impl ExactSizeIterator<Item = u64>
To support range-based keys, multiple hash values may need to be checked for a given key.
For example, an extent [0..1024) might return extents [0..512), [512..1024), each of which
will have a unique return value for Self::hash. For point-based keys, a single hash
suffices, in which case None is returned and the hash value of self should be checked.
Note that in general only a small number of partitions (e.g. 2) should be checked at once.
Queries checking too many partitions will fall back to returning true from bloom filter
checks to avoid degenerate performance.
Provided Methods§
Sourcefn is_range_key(&self) -> bool
fn is_range_key(&self) -> bool
Returns whether the type is a range-based key. Used to prevent use of range-based keys as
a point query (see crate::lsm_tree::merge::Query::Point).
Dyn Compatibility§
This trait is not dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety".