Struct ph::fmph::Function

pub struct Function<S = BuildDefaultSeededHasher> { /* private fields */ }

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

impl<S: BuildSeededHasher> Function<S>

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.

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.

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.

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.

pub fn write_bytes(&self) -> usize

Returns number of bytes which write will write.

pub fn write(&self, output: &mut dyn Write) -> Result<()>

Writes self to the output.

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.

pub fn level_sizes(&self) -> &[u64]

Returns sizes of the successive levels.

impl<S: BuildSeededHasher + Sync> Function<S>

pub fn try_with_conf_stats_or_partial<K, BS, KS>( keys: KS, conf: BuildConf<S>, stats: &mut BS ) -> Result<Self, (Self, KS, usize)>

where K: Hash + Sync, KS: KeySet<K>, BS: BuildStatsCollector,

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.

pub fn try_with_conf_stats<K, BS, KS>( keys: KS, conf: BuildConf<S>, stats: &mut BS ) -> Option<Self>

where K: Hash + Sync, KS: KeySet<K>, BS: BuildStatsCollector,

Constructs Function for given keys, using the build configuration conf and reporting statistics with stats.

None is returned 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.

pub fn with_conf_stats<K, BS>( keys: impl KeySet<K>, conf: BuildConf<S>, stats: &mut BS ) -> Self

where K: Hash + Sync, BS: BuildStatsCollector,

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.

pub fn with_conf<K>(keys: impl KeySet<K>, conf: BuildConf<S>) -> Self

where K: Hash + Sync,

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.

pub fn from_slice_with_conf_stats<K, BS>( keys: &[K], conf: BuildConf<S>, stats: &mut BS ) -> Self

where K: Hash + Sync, BS: BuildStatsCollector,

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.

pub fn from_slice_with_conf<K>(keys: &[K], conf: BuildConf<S>) -> Self

where K: Hash + Sync,

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.

pub fn from_slice_mut_with_conf_stats<K, BS>( keys: &mut [K], conf: BuildConf<S>, stats: &mut BS ) -> Self

where K: Hash + Sync, BS: BuildStatsCollector,

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.

pub fn from_slice_mut_with_conf<K>(keys: &mut [K], conf: BuildConf<S>) -> Self

where K: Hash + Sync,

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.

impl Function

pub fn read(input: &mut dyn Read) -> Result<Self>

Reads Self from the input. Only Functions that use default hasher can be read by this method.

pub fn with_stats<K, BS>(keys: impl KeySet<K>, stats: &mut BS) -> Self

where K: Hash + Sync, BS: BuildStatsCollector,

Builds Function for given keys, reporting statistics with stats.

Panics if constructing Function fails. Then it is almost certain that the input contains either duplicate keys or keys indistinguishable by any hash function from the family used.

pub fn new<K: Hash + Sync>(keys: impl KeySet<K>) -> Self

Builds Function for given keys.

Panics if constructing Function fails. Then it is almost certain that the input contains either duplicate keys or keys indistinguishable by any hash function from the family used.

impl<S> Function<S>

pub fn len(&self) -> usize

Returns the number of keys in the input collection given during construction.

The time complexity is proportional to the number returned.

Trait Implementations

impl<S: Clone> Clone for Function<S>

fn clone(&self) -> Function<S>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K: Hash + Sync> From<&[K]> for Function

fn from(keys: &[K]) -> Self

Converts to this type from the input type.

impl<K: Hash + Sync + Send> From<Vec<K>> for Function

fn from(keys: Vec<K>) -> Self

Converts to this type from the input type.

impl<S: BuildSeededHasher> GetSize for Function<S>

fn size_bytes_dyn(&self) -> usize

Returns approximate number of bytes occupied by dynamic (heap) part of self. Same as self.size_bytes() - std::mem::size_of_val(self).

fn size_bytes_content_dyn(&self) -> usize

Returns approximate number of bytes occupied by dynamic (heap) part of 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).

const USES_DYN_MEM: bool = true

true if and only if the variables of this type can use dynamic (heap) memory.

fn size_bytes(&self) -> usize

Returns approximate, total (including heap memory) number of bytes occupied by self.