pub struct Function<S = BuildDefaultSeededHasher> { /* private fields */ }
Expand description
Fingerprinting-based minimal perfect hash function (FMPH).
See:
- P. Beling, Fingerprinting-based minimal perfect hashing revisited, ACM Journal of Experimental Algorithmics, 2023, https://doi.org/10.1145/3596453
- A. Limasset, G. Rizk, R. Chikhi, P. Peterlongo, Fast and Scalable Minimal Perfect Hashing for Massive Key Sets, SEA 2017
Implementations§
source§impl<S: BuildSeededHasher> Function<S>
impl<S: BuildSeededHasher> Function<S>
sourcepub fn get_stats<K: Hash + ?Sized, A: AccessStatsCollector>(
&self,
key: &K,
access_stats: &mut A
) -> Option<u64>
pub fn get_stats<K: Hash + ?Sized, A: AccessStatsCollector>( &self, key: &K, access_stats: &mut A ) -> Option<u64>
Gets the value associated with the given key
and reports statistics to access_stats
.
The returned value is in the range from 0
(inclusive) to the number of elements in the input key collection (exclusive).
If the key
was not in the input key collection given during construction,
either None
or an undetermined value from the specified range is returned.
sourcepub fn get<K: Hash + ?Sized>(&self, key: &K) -> Option<u64>
pub fn get<K: Hash + ?Sized>(&self, key: &K) -> Option<u64>
Gets the value associated with the given key
.
The returned value is in the range: 0
(inclusive), the number of elements in the input key collection (exclusive).
If the key
was not in the input key collection given during construction,
either None
or an undetermined value from the specified range is returned.
sourcepub fn get_stats_or_panic<K: Hash + ?Sized, A: AccessStatsCollector>(
&self,
key: &K,
access_stats: &mut A
) -> u64
pub fn get_stats_or_panic<K: Hash + ?Sized, A: AccessStatsCollector>( &self, key: &K, access_stats: &mut A ) -> u64
Gets the value associated with the given key
and reports statistics to access_stats
.
The returned value is in the range: 0
(inclusive), the number of elements in the input key collection (exclusive).
If the key
was not in the input key collection given during construction,
it either panics or returns an undetermined value from the specified range.
sourcepub fn get_or_panic<K: Hash + ?Sized>(&self, key: &K) -> u64
pub fn get_or_panic<K: Hash + ?Sized>(&self, key: &K) -> u64
Gets the value associated with the given key
and reports statistics to access_stats
.
The returned value is in the range: 0
(inclusive), the number of elements in the input key collection (exclusive).
If the key
was not in the input key collection given during construction,
it either panics or returns an undetermined value from the specified range.
sourcepub fn write_bytes(&self) -> usize
pub fn write_bytes(&self) -> usize
Returns number of bytes which write
will write.
sourcepub fn read_with_hasher(input: &mut dyn Read, hasher: S) -> Result<Self>
pub fn read_with_hasher(input: &mut dyn Read, hasher: S) -> Result<Self>
Reads Self
from the input
. Hasher must be the same as the one used to write.
sourcepub fn level_sizes(&self) -> &[u64]
pub fn level_sizes(&self) -> &[u64]
Returns sizes of the successive levels.
source§impl<S: BuildSeededHasher + Sync> Function<S>
impl<S: BuildSeededHasher + Sync> Function<S>
sourcepub fn try_with_conf_stats_or_partial<K, BS, KS>(
keys: KS,
conf: BuildConf<S>,
stats: &mut BS
) -> Result<Self, (Self, KS, usize)>
pub fn try_with_conf_stats_or_partial<K, BS, KS>( keys: KS, conf: BuildConf<S>, stats: &mut BS ) -> Result<Self, (Self, KS, usize)>
Constructs Function
for given input keys
,
using the build configuration conf
and reporting statistics with stats
.
If the construction fails, it returns Err
with a triple (f, k, s), where:
- f is a
Function
handling only part of the keys (that returns numbers in the interval [0, s-k.keys_len())); - k is a set of the remaining keys,
- s is the initial number of keys. If needed, the keys from k can be placed in another data structure to handle all the keys.
If the construction fails, it is almost certain that the input contains either duplicate keys or keys indistinguishable by any hash function from the family used. The duplicate keys will be included in the k set.
sourcepub fn try_with_conf_stats<K, BS, KS>(
keys: KS,
conf: BuildConf<S>,
stats: &mut BS
) -> Option<Self>
pub fn try_with_conf_stats<K, BS, KS>( keys: KS, conf: BuildConf<S>, stats: &mut BS ) -> Option<Self>
sourcepub fn with_conf_stats<K, BS>(
keys: impl KeySet<K>,
conf: BuildConf<S>,
stats: &mut BS
) -> Self
pub fn with_conf_stats<K, BS>( keys: impl KeySet<K>, conf: BuildConf<S>, stats: &mut BS ) -> Self
Constructs Function
for given keys
, using the build configuration conf
and reporting statistics with stats
.
Panics if the construction fails. Then it is almost certain that the input contains either duplicate keys or keys indistinguishable by any hash function from the family used.
sourcepub fn with_conf<K>(keys: impl KeySet<K>, conf: BuildConf<S>) -> Self
pub fn with_conf<K>(keys: impl KeySet<K>, conf: BuildConf<S>) -> Self
Constructs Function for given keys
, using the build configuration conf
.
Panics if the construction fails. Then it is almost certain that the input contains either duplicate keys or keys indistinguishable by any hash function from the family used.
sourcepub fn from_slice_with_conf_stats<K, BS>(
keys: &[K],
conf: BuildConf<S>,
stats: &mut BS
) -> Self
pub fn from_slice_with_conf_stats<K, BS>( keys: &[K], conf: BuildConf<S>, stats: &mut BS ) -> Self
Constructs Function
for given keys
, using the build configuration conf
and reporting statistics with stats
.
Panics if the construction fails. Then it is almost certain that the input contains either duplicate keys or keys indistinguishable by any hash function from the family used.
sourcepub fn from_slice_with_conf<K>(keys: &[K], conf: BuildConf<S>) -> Self
pub fn from_slice_with_conf<K>(keys: &[K], conf: BuildConf<S>) -> Self
Constructs Function
for given keys
, using the build configuration conf
.
Panics if the construction fails. Then it is almost certain that the input contains either duplicate keys or keys indistinguishable by any hash function from the family used.
sourcepub fn from_slice_mut_with_conf_stats<K, BS>(
keys: &mut [K],
conf: BuildConf<S>,
stats: &mut BS
) -> Self
pub fn from_slice_mut_with_conf_stats<K, BS>( keys: &mut [K], conf: BuildConf<S>, stats: &mut BS ) -> Self
Constructs Function
for given keys
, using the build configuration conf
and reporting statistics with stats
.
Note that keys
can be reordered during construction.
Panics if the construction fails. Then it is almost certain that the input contains either duplicate keys or keys indistinguishable by any hash function from the family used.
sourcepub fn from_slice_mut_with_conf<K>(keys: &mut [K], conf: BuildConf<S>) -> Self
pub fn from_slice_mut_with_conf<K>(keys: &mut [K], conf: BuildConf<S>) -> Self
Constructs Function
for given keys
, using the build configuration conf
.
Note that keys
can be reordered during construction.
Panics if the construction fails. Then it is almost certain that the input contains either duplicate keys or keys indistinguishable by any hash function from the family used.
Trait Implementations§
source§impl<S: BuildSeededHasher> GetSize for Function<S>
impl<S: BuildSeededHasher> GetSize for Function<S>
source§fn size_bytes_dyn(&self) -> usize
fn size_bytes_dyn(&self) -> usize
self
.
Same as self.size_bytes() - std::mem::size_of_val(self)
.source§fn size_bytes_content_dyn(&self) -> usize
fn size_bytes_content_dyn(&self) -> usize
self
content.
It usually equals to size_bytes_dyn()
.
However, sometimes it is smaller by the amount of memory reserved but not yet used
(e.g., size_bytes_content_dyn()
only takes into account the length of the vector and not its capacity).source§const USES_DYN_MEM: bool = true
const USES_DYN_MEM: bool = true
true
if and only if the variables of this type can use dynamic (heap) memory.source§fn size_bytes(&self) -> usize
fn size_bytes(&self) -> usize
self
.