Struct GOFunction 

pub struct GOFunction<GS: GroupSize = TwoToPowerBitsStatic<4>, SS: SeedSize = TwoToPowerBitsStatic<2>, S = BuildDefaultSeededHasher> { /* private fields */ }

Fingerprinting-based minimal perfect hash function with group optimization (FMPHGO).

See:

• P. Beling, Fingerprinting-based minimal perfect hashing revisited, ACM Journal of Experimental Algorithmics, 2023, https://doi.org/10.1145/3596453

Implementations

impl<GS: GroupSize, SS: SeedSize, S: BuildSeededHasher> GOFunction<GS, SS, 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: 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<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, hash_builder: S) -> Result<Self>

Reads Self from the input. Hash builder must be the same as the one used to write.

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

Returns sizes of the successive levels.

impl<GS: GroupSize + Sync, SS: SeedSize, S: BuildSeededHasher + Sync> GOFunction<GS, SS, S>

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

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

Constructs GOFunction 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 GOFunction 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, KS, BS>( keys: KS, conf: GOBuildConf<GS, SS, S>, stats: &mut BS, ) -> Option<Self>

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

Constructs GOFunction 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, KS, BS>( keys: KS, conf: GOBuildConf<GS, SS, S>, stats: &mut BS, ) -> Self

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

Builds GOFunction for given keys, using the build configuration conf and reporting statistics with stats.

Panics if the construction fails.

pub fn with_conf<K, KS>(keys: KS, conf: GOBuildConf<GS, SS, S>) -> Self

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

Builds GOFunction 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: GOBuildConf<GS, SS, S>, stats: &mut BS, ) -> Self

where K: Hash + Sync, BS: BuildStatsCollector,

Builds GOFunction 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: GOBuildConf<GS, SS, S>) -> Self

where K: Hash + Sync,

Builds GOFunction for given keys, using the 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: GOBuildConf<GS, SS, S>, stats: &mut BS, ) -> Self

where K: Hash + Sync, BS: BuildStatsCollector,

Builds GOFunction 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: GOBuildConf<GS, SS, S>, ) -> Self

where K: Hash + Sync,

Builds GOFunction 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<GS: GroupSize + Sync, SS: SeedSize> GOFunction<GS, SS>

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

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

impl GOFunction

pub fn from_slice_with_stats<K, BS>(keys: &[K], stats: &mut BS) -> Self

where K: Hash + Sync, BS: BuildStatsCollector,

Builds GOFunction for given keys, 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<K: Hash + Sync>(keys: &[K]) -> Self

Builds GOFunction for given keys.

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 new<K: Hash + Sync, KS: KeySet<K> + Sync>(keys: KS) -> Self

Builds GOFunction for given keys.

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<GS: GroupSize, SS: SeedSize, S> GOFunction<GS, SS, 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<K: Hash + Sync> From<&[K]> for GOFunction

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

Converts to this type from the input type.

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

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

Converts to this type from the input type.

impl<GS: GroupSize, SS: SeedSize, S: BuildSeededHasher> GetSize for GOFunction<GS, SS, S>

const USES_DYN_MEM: bool = true

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

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).

fn size_bytes(&self) -> usize

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