7 releases
0.2.0 | Aug 22, 2020 |
---|---|
0.1.5 | Aug 19, 2020 |
0.1.2 | Jun 14, 2020 |
#1341 in Data structures
Used in hat_trie
55KB
822 lines
ahtable
An array hash data structure where array is allocated up front with specific size and each element is assigned to each index based on hash function. Each element in an array is a Vec. Each collision of hash will be push into Vec. When number of added element reach certain size, it will scale the size of array by 2x and all old entry will be moved from old array to new one. All of this happen behind the scene. User will not effect by such operation.
How to use
- Use
ArrayHashBuilder::default()
- Config all required specification of array hash with the builder
- Use
build()
method on the instance to obtainArrayHash
- Use following method to operate on the array
put()
to put new data into array. This method always put or replace existing value.try_put()
to put new data into array if it is not already exist.get()
to retrieve a value that was put into it by a key of a type that is hashable and comparable to key.smart_get()
to retrieve a value whenkey
is of smart pointer type. This will help reduce time processor required to construct a smart pointer of the same type as key itself.coerce_get()
to retrieve a value whenkey
is of a type that can be borrowed as another type which isn't implementPartialEq<K>
to the original type.remove()
to remove a value out of this array by a key of a type that is hashable and comparable to key.smart_remove()
to retrieve a value whenkey
is of smart pointer type. This will help reduce time processor required to construct a smart pointer of the same type as key itself.coerce_remove()
to remove a value whenkey
is of a type that can be borrowed as another type which isn't implementPartialEq<K>
to the original type.contains_iter
to test whether current array have every entry that the iterator yield.to_builder
to obtainArrayHashBuilder
with current spec out of existing array.iter()
to iterate over the array entry.iter_mut()
to iterate and mutate the array entry. This iterator shall not be used to mutate the entry key.drain()
to obtain an iterator that keep draining all data from this array out.drain_with()
to obtain an iterator that drain some specific entry out when predicate return true.split_by()
which return another array and move all value that satisfy the predicate into new array.is_hasher_eq()
to check whether two array have equivalence hasher.
Breaking change from 0.1 to 0.2
ArrayHash::try_put
is now returnResult
. When it fail to put, it returnErr
with given key/value along with reference to current value associated with given key. When it succeed, it returnOk
with reference to value that was put into array.
Migration guide from 0.1 to 0.2
- for any
if let Some(v) = array_hash.try_put(key, value)
, it'd becomeif let Err((key, value, cur_val) = array_hash.try_put(key, value)
- for any
if array_hash.try_put(key, value).is_some()
, it'd becomeif array_hash.try_put(key, value).is_err()
- for any
if array_hash.try_put(key, value).is_none()
, it'd becomeif array_hash.try_put(key, value).is_ok()
- for any statement
array_hash.try_put(key, value);
, it'd becomearray_hash.try_put(key, value).unwrap()
- for any
let cur_v = array_hash.try_put(key, value).unwrap()
, it'd becomelet (_, _, cur_v) = array_hash.try_put(key, value).unwrap_err()
Important notes
PartialEq
ofArrayHash
need both comparator and comparatee to be exactly the same. This includingHasher
which must be seed by exactly the same number. The ideal usage is to fill largest array first then useArrayHash::to_builder
to build second array. If it is impossible, consider construct anArrayHash
that is large enough to stored everything without reachingmax_load_factor
then useArrayHash::to_builder
or clone thatArrayHashBuilder
to build every array.- There's method
ArrayHash::is_hasher_eq
to test whether two array can be compared. If two arrays are using different type of hasher, it will immediately yield compile error. If it use the same type of hasher but it use different seed, it will returnfalse
. Otherwise, it is comparable via==
operator. - Directly using
==
operator on two arrays are safe. It will compile error similar toArrayHash::is_hasher_eq
. In fact, inPartialEq
implementation, it useArrayHash::is_hasher_eq
to check first if it is comparable. However, it will always return false if two array use different seed even if both array have exactly the same elements in it. - It is much faster to use
==
operator to compare two arrays than usingArrayHash::contains_iter
ascontains_iter
will need to hash every key return by iter. Thecontains_iter
method is suitable in case where two arrays are using different hasher type or built from different ``ArrayHashBuilder`.
What's new
0.2.0
ArrayHash::try_put
moved givenkey
andvalue
but doesn't guarantee to put thekey
andvalue
in. It now returnResult
. If thekey
andvalue
is successfully put, it returnOk((&V))
where&V
is the reference to value that was put. If it fail to put, it returnErr((K, V))
whereK
is the givenkey
andV
is given value.
0.1.5
- Fix hash defect. When hashing on
ArrayHash
itself which may cause two hash to be different eventhough,==
of two array is true. This is becausePartialEq
doesn't comparemax_load_factor
but in0.1.4
hash takemax_load_factor
to calculate the hash.
0.1.4
ArrayHash
andArrayHashBuilder
are now implementsHash
andPartialEq
ArrayHash::is_hasher_eq
to check if two array use exactly the same hasher.ArrayHash::coerce_get
andArrayHash::coerce_remove
that accept a borrowed type that doesn't implementPartialEq<K>
with the stored entryArrayHash::smart_remove
which is counterpart ofArrayHash::smart_get
that is usable when both storedkey
and query can be deref into the same type.- impl
core::convert::From<ArrayHash>
forArrayHashBuilder
. ArrayHash::to_builder
to retrieve aArrayHashBuilder
that can build anArrayHash
with exactly same spec as currentArrayHash
.ArrayHash::contains_iter
that check if this array contain every entry that given iter yield.
0.1.3
ArrayHash::get
andArrayHash::remove
parameter is now generic instead of fixing it to be the same type as the one being key. Now any types that implementsPartialEq<K>
+Hash
can be used as parameter.ArrayHash
key and value no longer need to implement clone. The reason behind this is because there are two place where it need to clone key and value. Both of it is for purpose of allocatingVec
. However, in both place, it need no actual clone on key nor value. It allocate an emptyVec
. Therefore, cloning emptyVec
would have no different impact on performance comparing to looping to construct an emptyVec
. With this reason, it would be easier for library user to have lesser number of constraint on key/value.
Dependencies
~145KB