Struct hash_arr_map::map::Ham

pub struct Ham<K, V> { /* fields omitted */ }

A hash map with an array part and a hash part, like Lua’s table structure.

This is most useful when you want to use the map like a sparse array, since the hash part can store most of the sparse items, while the array part offers better performance than HashMap for arrays that aren’t very sparse.

It is required that the keys implement the Eq and Hash traits, although this can frequently be achieved by using #[derive(PartialEq, Eq, Hash)]. If you implement these yourself, it is important that the following property holds:

k1 == k2 -> hash(k1) == hash(k2)

In other words, if two keys are equal, their hashes must be equal.

Additionally, keys are required to implement the IntoIndex and FromIndex traits that allow conversion to and from indices into the array part.

It is a logic error for a key to be modified in such a way that the key’s hash, as determined by the Hash trait, or its equality, as determined by the Eq trait, changes while it is in the map. This is normally only possible through Cell, RefCell, global state, I/O, or unsafe code.

Examples

use hash_arr_map::Ham;

// Type inference lets us omit an explicit type signature (which
// would be `Ham<i32, i32>` in this example).
let mut squares = Ham::new();

// Square some numbers.
squares.insert(1, 1);
squares.insert(2, 4);
squares.insert(3, 8);
squares.insert(5, 25);

// Check for a specific square.
if !squares.contains_key(&4) {
    println!(
        "We've got {} squares, but not the square of 4.",
        squares.len()
    );
}

// oops, this square is incorrect. Let's delete it
squares.remove(&3);

// Iterate over everything.
for (number, square) in &squares {
    println!("{}'s square is {}", number, square);
}

Ham also implements an Entry API, which allows for more complex methods of getting, setting, updating and removing keys and their values:

use hash_arr_map::Ham;

let text = "Rust's strings are utf-8 \u{2764}";

// Type inference lets us not say what type of map this is.
// (`Ham<char, usize>` in this example)
let mut map = Ham::new();

for c in text.chars() {
    map.entry(c).and_modify(|c| *c += 1).or_insert(1_usize);
}

assert_eq!(map[&'t'], 3);
assert_eq!(map[&'s'], 4);
assert_eq!(map[&'❤'], 1);

The easiest way to use Ham with a custom key type is to derive Eq and Hash, then implement IntoIndex and FromIndex for it. We must also derive PartialEq.

use hash_arr_map::{FromIndex, Ham, Idx, IntoIndex};

#[derive(Hash, Eq, PartialEq, Debug)]
struct Item {
    dollars: u8,
    cents: u8,
}

impl Item {
    /// Creates a new Item.
    fn new(dollars: u8, cents: u8) -> Self {
        Self { dollars, cents }
    }
}

impl IntoIndex for Item {
    fn into_index(&self) -> Option<Idx<Self>> {
        unsafe { Idx::from_usize(((self.cents as usize) << 8) + self.dollars as usize) }
    }
}

impl FromIndex for Item {
    fn from_index(idx: Idx<Self>) -> Self {
        Self {
            dollars: idx.get().get() as u8,
            cents: (idx.get().get() >> 8) as u8,
        }
    }
}

// Use a HashMap to store the item's quantity.
let mut items = Ham::new();

items.insert(Item::new(10, 0), 25);
items.insert(Item::new(5, 50), 24);
items.insert(Item::new(7, 75), 12);

let total: usize = items
    .iter()
    .map(|(item, qty)| {
        let dollars: usize = item.dollars as usize;
        let cents: usize = item.cents as usize;
        (dollars * 100 + cents) * qty // In cents
    })
    .sum();
println!("Total is {}c", total);

// Use derived implementation to print the status of the items.
for (item, qty) in &items {
    println!("{:?} has {} quantity", item, qty);
}

A HashMap with fixed list of elements can be initialized from an array:

use std::borrow::Cow;

use hash_arr_map::Ham;

let timber_resources: Ham<Cow<str>, u32> = [("Norway", 100), ("Denmark", 50), ("Iceland", 10)]
    .iter()
    .copied()
    .map(|(k, v)| (Cow::Borrowed(k), v))
    .collect();
// use the values stored in map

References cannot be used as keys, as they cannot be easily converted to indexes and back:

use hash_arr_map::Ham;

// This is inferred as `Ham<&str, i32>`.
let mut h = Ham::new();

h.insert("test", 101);

Implementations

impl<K, V> Ham<K, V>

pub fn new() -> Self

Creates a new Ham.

pub fn with_capacity(array_part: usize, hash_part: usize) -> Self

Creates a new Ham with a specific capacity.

impl<K, V> Ham<K, V>

pub const fn with_seed(seed: u64) -> Self

Creates a new Ham with a specific seed.

pub fn with_capacity_and_seed(
    array_part: usize,
    hash_part: usize,
    seed: u64
) -> Self

Creates a new Ham with a specific capacity and a specific seed.

pub const fn len(&self) -> usize

How many elements the Ham has eaten.

pub const fn is_empty(&self) -> bool

pub fn capacity(&self) -> (usize, usize)

Returns the number of elements in both sections the Ham can eat without having to allocate.

pub fn clear(&mut self)

Empties the Ham.

pub fn is_in_array<Q: ?Sized + IntoIndex>(&self, key: &Q) -> bool

Whether key would be stored in the array part.

Note: This method may be incorrect for some values once they are inserted

Example:

Initial layout:

array_part: [0, 1, 2],
hash_part: {5}

is_in_array(4) would return false, likewise is_in_array(3).

If 4 or 3 were now inserted, the layout would then likely be

array_part: [0, 1, 2, _, 4, 5], // _ is none
hash_part: {}

where 3 and 4 are now in the array.

pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where
    K: Borrow<Q>,
    Q: IntoIndex + Hash + Eq, 

pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where
    K: Borrow<Q>,
    Q: IntoIndex + Hash + Eq, 

pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where
    K: Borrow<Q>,
    Q: IntoIndex + Hash + Eq, 

pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where
    K: Borrow<Q>,
    Q: IntoIndex + Hash + Eq, 

impl<K: FromIndex, V> Ham<K, V>

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

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

pub fn keys(&self) -> Keys<'_, K, V>

pub fn values(&self) -> Values<'_, K, V>

pub fn values_mut(&mut self) -> ValuesMut<'_, K, V>

impl<K: FromIndex + Hash + Eq, V> Ham<K, V>

pub fn get_key_value<Q: ?Sized>(&self, key: &Q) -> Option<(Key<'_, K>, &V)> where
    K: Borrow<Q>,
    Q: IntoIndex + Hash + Eq, 

pub fn remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)> where
    K: Borrow<Q>,
    Q: IntoIndex + Hash + Eq, 

Removes a key from the map, returning the stored key and value if the key was previously in the map.

The key may be any borrowed form of the map’s key type, but Hash and Eq on the borrowed form must match those for the key type.

Examples

use hash_arr_map::Ham;

let mut map = Ham::new();
map.insert(1, "a");
assert_eq!(map.remove_entry(&1), Some((1, "a")));
assert_eq!(map.remove(&1), None);

impl<K: NewIndex + Hash + Eq, V> Ham<K, V>

pub fn get_n(&self) -> Option<usize>

This function finds a boundary in the table, such that table.get(n) is Some(_), and table.get(n + 1) is None.

impl<K: IntoIndex + FromIndex + Hash + Eq, V> Ham<K, V>

pub fn entry(&mut self, k: K) -> Entry<'_, K, V>

Gets the given key’s corresponding entry in the map for in-place manipulation.

Examples

use hash_arr_map::Ham;

let mut letters = Ham::new();

for ch in "a short treatise on fungi".chars() {
    let counter = letters.entry(ch).or_insert(0);
    *counter += 1;
}

assert_eq!(letters[&'s'], 2);
assert_eq!(letters[&'t'], 3);
assert_eq!(letters[&'u'], 1);
assert_eq!(letters.get(&'y'), None);

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

Feed the Ham with a key-value pair.

If the map did not have this key present, None is returned.

If the map did have this key present, the value is updated, and the old value is returned.

Examples

use hash_arr_map::Ham;

let mut map = Ham::new();
assert_eq!(map.insert(37, "a"), None);
assert_eq!(map.is_empty(), false);

map.insert(37, "b");
assert_eq!(map.insert(37, "c"), Some("b"));
assert_eq!(map[&37], "c");

pub fn shrink_to_fit(&mut self)

Shrinks the capacity of the map as much as possible.

Both the hash part and the array part will be at least half full.

Note that this does not mean there will not be extra capacity. Due to internal requirements, the length of the array part and the length of the hash part are required to be powers of two.

pub fn force_rehash(&mut self)

Rehashes the whole table, meaning that some entries might get moved to the array part, or vice-versa.

Trait Implementations

impl<K: Clone, V: Clone> Clone for Ham<K, V>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K: FromIndex + Debug, V: Debug> Debug for Ham<K, V>

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

Formats the value using the given formatter.

impl<K, V> Default for Ham<K, V>

fn default() -> Self

Returns the “default value” for a type.

impl<K, V> Extend<(K, V)> for Ham<K, V> where
    K: IntoIndex + FromIndex + Hash + Eq, 

fn extend<I>(&mut self, iter: I) where
    I: IntoIterator<Item = (K, V)>, 

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬 This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<K, V> FromIterator<(K, V)> for Ham<K, V> where
    K: IntoIndex + FromIndex + Hash + Eq, 

fn from_iter<I>(iter: I) -> Self where
    I: IntoIterator<Item = (K, V)>, 

Creates a value from an iterator.

impl<K, Q: ?Sized, V> Index<&'_ Q> for Ham<K, V> where
    K: Hash + Eq + Borrow<Q>,
    Q: IntoIndex + Hash + Eq, 

type Output = V

The returned type after indexing.

fn index(&self, key: &Q) -> &V

Performs the indexing (container[index]) operation.

impl<K, Q: ?Sized, V> IndexMut<&'_ Q> for Ham<K, V> where
    K: Hash + Eq + Borrow<Q>,
    Q: IntoIndex + Hash + Eq, 

fn index_mut(&mut self, key: &Q) -> &mut V

Performs the mutable indexing (container[index]) operation.

impl<'a, K: FromIndex, V> IntoIterator for &'a Ham<K, V>

type Item = (Key<'a, K>, &'a V)

The type of the elements being iterated over.

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

Which kind of iterator are we turning this into?

fn into_iter(self) -> Iter<'a, K, V>

Creates an iterator from a value.

impl<'a, K: FromIndex, V> IntoIterator for &'a mut Ham<K, V>

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

The type of the elements being iterated over.

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

Which kind of iterator are we turning this into?

fn into_iter(self) -> IterMut<'a, K, V>

Creates an iterator from a value.

impl<K: FromIndex, V> IntoIterator for Ham<K, V>

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> IntoIter<K, V>

Creates an iterator from a value.