Struct ArrayHash 

pub struct ArrayHash<H, K, V>
where
    H: Hasher + Clone,
    K: Hash + PartialEq,
{ /* private fields */ }

An implementation of ArrayHash in pure Rust.

ArrayHash is a data structure where the index is determined by hash and each entry in array is a Vec that store data and all it collision.

Oritinal paper can be found [here](Askitis, N. & Zobel, J. (2005), Cache-conscious collision resolution for string hash tables, in ‘Proc. SPIRE String Processing and Information Retrieval Symp.’, Springer-Verlag, pp. 92–104)

In this implementation, user can supplied their own choice of hasher but it need to implement Clone.

The data can be anything that implement Hash.

The default Hasher, if not provided, will be XxHash64.

Implementations

impl<H, K, V> ArrayHash<H, K, V>

where H: Hasher + Clone, K: Hash + PartialEq,

pub fn to_builder(&self) -> ArrayHashBuilder<H>

Make a builder with default specification equals to current specification of this array.

Note: The current specification of array may be different from the spec used to create the array. For example, if original max_load_factor is 2 but 3 elements were put into array, the max_load_factor will be 4 and the bucket_size will be double of the original bucket_size.

pub fn is_hasher_eq<K2, V2>(&self, rhs: &ArrayHash<H, K2, V2>) -> bool

where H: PartialEq, K2: Hash + PartialEq,

Check if two array use the same hasher with exactly same seed. This mean that value A == B on these two array will have exactly the same hash value.

pub fn put(&mut self, key: K, value: V) -> Option<(K, V)>

Add or replace entry into this HashMap. If entry is replaced, it will be return in Option. Otherwise, it return None

Parameter

• entry - A tuple to be add to this.

Return

Option that contains tuple of (key, value) that got replaced or None if it is new entry

pub fn try_put(&mut self, key: K, value: V) -> Result<&V, (K, V, &V)>

Try to put value into this ArrayHash. If the given key is already in used, leave old entry as is and return key/value along with current reference to value associated with the key. Otherwise, add entry to this ArrayHash and return reference to current value.

Parameter

• entry - A tuple of (key, value) to be add to this.

Return

It return Ok(&V) if key/value were put into this collection. Otherwise, it return Err((K, V, &V)) where K is given key, V is given value, and &V is reference to current value associated with given key

pub fn get<T>(&self, key: &T) -> Option<&V>

where T: Hash + PartialEq<K>,

Get a value of given key from this ArrayHash relying on contractual implementation of PartialEq and Hash where following contract applied:

• for any A == B then B == A then hash of A == hash of B
• for any A == B and B == C then A == C then hash of A == hash of B == hash of C

Parameter

• key - A key to look for.

Return

An Option contains a value or None if it is not found.

pub fn smart_get<T, Q>(&self, key: Q) -> Option<&V>

where Q: Deref<Target = T>, K: Deref<Target = T>, T: Hash + PartialEq,

Get a value using deref type.

This is usable only if the key is a type of smart pointer that can be deref into another type which implement Hash and PartialEq.

For example, if K is Box<[u8]>, you can use &[u8] to query for a value

Parameter

key - Any type that implement Deref where type after Deref is that same type as actual type of key beneath type K.

Return

Some(&V) if key exist in this table. Otherwise None.

pub fn coerce_get<T>(&self, key: &T) -> Option<&V>

where T: Hash + PartialEq + ?Sized, K: Borrow<T>,

Get a value of given key from this ArrayHash relying on contractual implementation of PartialEq and Hash where following contract applied:

• B can be borrowed as type A
• for any A == B then B == A then hash of A == hash of B
• for any A == B and B == C then A == C then hash of A == hash of B == hash of C
• for any &A == &B then A == B

It is useful for case where the stored key and query key is different type but the stored key can be borrow into the same type as query. For example, stored Vec<T> but query with &[T]. It isn’t possible to use get method as [T] isn’t implement PartialEq<Vec<T>>.

Parameter

• key - A key to look for.

Return

An Option contains a value or None if it is not found.

pub fn remove<T>(&mut self, key: &T) -> Option<(K, V)>

where T: Hash + PartialEq<K>,

Attempt to remove entry with given key from this ArrayHash relying on contractual implementation of PartialEq and Hash where following contract applied:

• for any A == B then B == A then hash of A == hash of B
• for any A == B and B == C then A == C then hash of A == hash of B == hash of C

Parameter

• key - A key of entry to be remove.

Return

Option that contain tuple of (key, value) or None of key is not found

pub fn smart_remove<Q, T>(&mut self, key: Q) -> Option<(K, V)>

where Q: Deref<Target = T>, K: Deref<Target = T>, T: Hash + PartialEq,

Attempt to remove entry with given key from this ArrayHash.

This is usable only if the key is a type of smart pointer that can be deref into another type which implement Hash and PartialEq.

For example, if K is Box<[u8]>, you can use &[u8] to remove it.

Parameter

• key - A key of entry to be remove.

Return

Option that contain tuple of (key, value) or None of key is not found

pub fn coerce_remove<T>(&mut self, key: &T) -> Option<(K, V)>

where T: Hash + PartialEq + ?Sized, K: Borrow<T>,

Attempt to remove entry with given key from this ArrayHash relying on contractual implementation of PartialEq and Hash where following contract applied:

• B can be borrowed as type A
• for any A == B then B == A then hash of A == hash of B
• for any A == B and B == C then A == C then hash of A == hash of B == hash of C
• for any &A == &B then A == B

It is useful for case where the stored key and query key is different type but the stored key can be borrow into the same type as query. For example, stored Vec<T> but query with &[T]. It isn’t possible to use remove method as [T] isn’t implement PartialEq<Vec<T>>.

Parameter

• key - A key of entry to be remove.

Return

Option that contain tuple of (key, value) or None of key is not found

pub fn len(&self) -> usize

Current number of entry in this ArrayHash

pub fn contains_iter<'a, I>(&self, other: I) -> bool

where I: IntoIterator<Item = &'a (K, V)>, K: 'a, V: 'a + PartialEq,

Check if this array hash contains every entry found in given other iterator that yield &(K, V) and V implements PartialEq.

Parameter

• other - A type that implement IntoIterator<Item=&(K, V)>

Return

true if this array hash contains every entry that other iterator yield. Otherwise, false.

pub fn iter(&self) -> ArrayHashIterator<'_, K, V>

Get an iterator over this ArrayHash.

Return

ArrayHashIterator that return reference to each entry in this ArrayHash

pub fn iter_mut(&mut self) -> ArrayHashIterMut<'_, K, V>

Get a mutable iterator over this ArrayHash.

Warning, you shall not modify the key part of entry. If you do, it might end up accessible only by iterator but not with get.

Return

ArrayHashIterMut that return mutably reference to each entry in this ArrayHash

pub fn drain(&mut self) -> DrainIter<'_, K, V>

Return an iterator that drain all entry out of this ArrayHash.

After the iterator is done, this ArrayHash will become empty.

This method will immediately set size to 0.

Return

DrainIter - An iterator that will drain all element out of this ArrayHash.

pub fn drain_with<F>(&mut self, pred: F) -> DrainWithIter<'_, F, K, V>

where F: Fn(&(K, V)) -> bool,

Return an iterator that drain some entry out of this ArrayHash.

After the iterator is done, this ArrayHash size will be shrink.

This method will return an iterator where each element it drain will cause a size deduction on this ArrayHash.

Return

DrainWithIter - An iterator that will drain all element out of this ArrayHash.

pub fn split_by<F>(&mut self, pred: F) -> ArrayHash<H, K, V>

where F: Fn(&(K, V)) -> bool,

Split this ArrayHash by given predicate closure. Every element that closure evaluate to true will be remove from this ArrayHash and return in new instance of ArrayHash.

This is different from using drain_with to drain some element into another ArrayHash by this method will return ArrayHash with exactly identical property, i.e. Hasher, buckets_size, and max_load_factor, whereas drain_with let caller instantiate ArrayHash yourself.

Since the instant it returns, use the same Hasher. It is safe to assume that all elements shall reside in the same bucket number thus this method speed up the split by ignore hashing altogether and store the entry directly into the same bucket number as in this ArrayHash

Parameter

pred - A closure that evaluate an entry. If it return true, the entry shall be moved into a new ArrayHash.

Return

An ArrayHash that contains all entry that pred evaluate to true.

Trait Implementations

impl<H, K, V: Clone> Clone for ArrayHash<H, K, V>

where H: Hasher + Clone + Clone, K: Hash + PartialEq + Clone,

fn clone(&self) -> ArrayHash<H, K, V>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<H, K, V: Debug> Debug for ArrayHash<H, K, V>

where H: Hasher + Clone + Debug, K: Hash + PartialEq + Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'a, H, K, V> From<&'a ArrayHash<H, K, V>> for ArrayHashBuilder<H>

where H: Clone + Hasher, K: Hash + PartialEq,

Make ArrayHashBuilder with spec from existing ArrayHash.

This is useful for creating an object of array hash that may be later compare to baseline array for equality.

fn from(ah: &'a ArrayHash<H, K, V>) -> ArrayHashBuilder<H>

Converts to this type from the input type.

impl<H, K, V> Hash for ArrayHash<H, K, V>

where H: Hasher + Clone, K: Hash + PartialEq, V: Hash,

Implement hash by using only K and V pair to calculate hash. It will still conform to following contract: For any AH1 == AH2, hash(AH1) == hash(AH2).

This is because the PartialEq implementation check if both side have the same size, same hasher, same number of items, and exactly the same key and value pair returned by each yield of both AH1’s and AH2’s iterator. However, hasher contract need no symmetric property. It mean that hash(AH1) == hash(AH2) doesn’t imply that AH1 == AH2. Thus, we will have the same hash if we iterate through array and hash both key and value for each yield on both AH1 and AH2.

fn hash<H2: Hasher>(&self, hasher: &mut H2)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<H, K, V> IntoIterator for ArrayHash<H, K, V>

where H: Hasher + Clone, K: Hash + PartialEq,

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = ArrayHashIntoIter<K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, H, K, V> IntoIterator for &'a ArrayHash<H, K, V>

where H: Hasher + Clone, K: Hash + PartialEq,

type Item = &'a (K, V)

The type of the elements being iterated over.

type IntoIter = ArrayHashIterator<'a, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, H, K, V> IntoIterator for &'a mut ArrayHash<H, K, V>

where H: Hasher + Clone, K: Hash + PartialEq,

type Item = &'a mut (K, V)

The type of the elements being iterated over.

type IntoIter = ArrayHashIterMut<'a, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<H, K1, V1, K2, V2> PartialEq<ArrayHash<H, K1, V1>> for ArrayHash<H, K2, V2>

where H: Clone + Hasher + PartialEq, K1: Hash + PartialEq + PartialEq<K2>, V1: PartialEq<V2>, K2: Hash + PartialEq,

Generalize implementation that let two array hash of different type of key and value to be comparable. It requires that both side must use the same hasher with exactly same seed. It rely on a contract that if any K1 == K2 then it mean those two hash is also equals.

fn eq(&self, rhs: &ArrayHash<H, K1, V1>) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.