Struct agb_hashmap::HashMap

pub struct HashMap<K, V, ALLOCATOR: Allocator = Global> { /* private fields */ }

A hash map implemented very simply using robin hood hashing.

HashMap uses FxHasher internally, which is a very fast hashing algorithm used by rustc and firefox in non-adversarial places. It is incredibly fast, and good enough for most cases.

It is required that the keys implement the Eq and Hash traits, although this can be frequently 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)

It is a logic error for the 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. The behaviour for such a logic error is not specified, but will not result in undefined behaviour. This could include panics, incorrect results, aborts, memory leaks and non-termination.

The API surface provided is incredibly similar to the std::collections::HashMap implementation with fewer guarantees, and better optimised for the GameBoy Advance.

Example

use agb_hashmap::HashMap;

// Type inference lets you omit the type signature (which would be HashMap<String, String> in this example)
let mut game_reviews = HashMap::new();

// Review some games
game_reviews.insert(
    "Pokemon Emerald".to_string(),
    "Best post-game battle experience of any generation.".to_string(),
);
game_reviews.insert(
    "Golden Sun".to_string(),
    "Some of the best music on the console".to_string(),
);
game_reviews.insert(
    "Super Dodge Ball Advance".to_string(),
    "Really great launch title".to_string(),
);

// Check for a specific entry
if !game_reviews.contains_key("Legend of Zelda: The Minish Cap") {
    println!("We've got {} reviews, but The Minish Cap ain't one", game_reviews.len());
}

// Iterate over everything
for (game, review) in &game_reviews {
    println!("{game}: \"{review}\"");
}

Implementations

impl<K, V> HashMap<K, V>

pub fn new() -> Self

Creates a HashMap

pub fn with_size(size: usize) -> Self

Creates an empty HashMap with specified internal size. The size must be a power of 2

pub fn with_capacity(capacity: usize) -> Self

Creates an empty HashMap which can hold at least capacity elements before resizing. The actual internal size may be larger as it must be a power of 2

impl<K, V, ALLOCATOR: ClonableAllocator> HashMap<K, V, ALLOCATOR>

pub fn with_size_in(size: usize, alloc: ALLOCATOR) -> Self

Creates an empty HashMap with specified internal size using the specified allocator. The size must be a power of 2

pub fn new_in(alloc: ALLOCATOR) -> Self

Creates a HashMap with a specified allocator

pub fn allocator(&self) -> &ALLOCATOR

Returns a reference to the underlying allocator

pub fn with_capacity_in(capacity: usize, alloc: ALLOCATOR) -> Self

Creates an empty HashMap which can hold at least capacity elements before resizing. The actual internal size may be larger as it must be a power of 2

Panics

Panics if capacity is larger than 2^32 * .85

pub fn len(&self) -> usize

Returns the number of elements in the map

pub fn capacity(&self) -> usize

Returns the number of elements the map can hold

pub fn keys(&self) -> impl Iterator<Item = &K>

An iterator visiting all keys in an arbitrary order

pub fn values(&self) -> impl Iterator<Item = &V>

An iterator visiting all values in an arbitrary order

pub fn values_mut(&mut self) -> impl Iterator<Item = &mut V>

An iterator visiting all values in an arbitrary order allowing for mutation

pub fn clear(&mut self)

Removes all elements from the map

pub fn iter(&self) -> impl Iterator<Item = (&K, &V)>

An iterator visiting all key-value pairs in an arbitrary order

pub fn iter_mut(&mut self) -> impl Iterator<Item = (&K, &mut V)>

An iterator visiting all key-value pairs in an arbitrary order, with mutable references to the values

pub fn retain<F>(&mut self, f: F)

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

Retains only the elements specified by the predicate f.

pub fn is_empty(&self) -> bool

Returns true if the map contains no elements

impl<K, V, ALLOCATOR: ClonableAllocator> HashMap<K, V, ALLOCATOR>

where K: Eq + Hash,

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

Inserts a key-value pair into the map.

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. The key is not updated, which matters for types that can be == without being identical.

pub fn contains_key<Q>(&self, k: &Q) -> bool

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns true if the map contains a value for the specified key.

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

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns the key-value pair corresponding to the supplied key

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

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns a reference to the value corresponding to the key. Returns None if there is no element in the map with the given key.

Example

use agb_hashmap::HashMap;

let mut map = HashMap::new();
map.insert("a".to_string(), "A");
assert_eq!(map.get("a"), Some(&"A"));
assert_eq!(map.get("b"), None);

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

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns a mutable reference to the value corresponding to the key. Return None if there is no element in the map with the given key.

Example

use agb_hashmap::HashMap;

let mut map = HashMap::new();
map.insert("a".to_string(), "A");

if let Some(x) = map.get_mut("a") {
    *x = "b";
}

assert_eq!(map["a"], "b");

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

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Removes the given key from the map. Returns the current value if it existed, or None if it did not.

Example

use agb_hashmap::HashMap;

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

impl<K, V, ALLOCATOR: ClonableAllocator> HashMap<K, V, ALLOCATOR>

where K: Hash + Eq,

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

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

Trait Implementations

impl<K: Clone, V: Clone, ALLOCATOR: Clone + Allocator> Clone for HashMap<K, V, ALLOCATOR>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K, V, ALLOCATOR: ClonableAllocator> Debug for HashMap<K, V, ALLOCATOR>

where K: Debug, V: Debug,

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

Formats the value using the given formatter.

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

fn default() -> Self

Returns the “default value” for a type.

impl<K, V> Extend<(K, V)> for HashMap<K, V>

where K: Eq + Hash,

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

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 HashMap<K, V>

where K: Eq + Hash,

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

Creates a value from an iterator.

impl<K, V, Q, ALLOCATOR: ClonableAllocator> Index<&Q> for HashMap<K, V, ALLOCATOR>

where K: Eq + Hash + Borrow<Q>, Q: Eq + Hash + ?Sized,

type Output = V

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

impl<'a, K, V, ALLOCATOR: ClonableAllocator> IntoIterator for &'a HashMap<K, V, ALLOCATOR>

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

The type of the elements being iterated over.

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

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, V, ALLOCATOR: ClonableAllocator> IntoIterator for HashMap<K, V, ALLOCATOR>

An iterator over entries of a HashMap

This struct is created using the into_iter() method on HashMap as part of its implementation of the IntoIterator trait.

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = IterOwned<K, V, ALLOCATOR>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, V, ALLOCATOR: ClonableAllocator> PartialEq for HashMap<K, V, ALLOCATOR>

where K: Eq + Hash, V: PartialEq,

fn eq(&self, other: &HashMap<K, V, ALLOCATOR>) -> bool

This method tests for self and other values to be equal, and is used by ==.

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

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<K, V, ALLOCATOR: ClonableAllocator> Eq for HashMap<K, V, ALLOCATOR>

where K: Eq + Hash, V: PartialEq,