Skip to main content
Version: dev

HashMap

HashMap<Key, Value, MaxLen, Hasher> is used to efficiently store and look up key-value pairs.

HashMap is a bounded type which can store anywhere from zero to MaxLen total elements. Note that due to hash collisions, the actual maximum number of elements stored by any particular hashmap is likely lower than MaxLen. This is true even with cryptographic hash functions since every hash value will be performed modulo MaxLen.

When creating HashMaps, the MaxLen generic should always be specified if it is not already known. Otherwise, the compiler may infer a different value for MaxLen (such as zero), which will likely change the result of the program. This behavior is set to become an error in future versions instead.

Example:

// Create a mapping from Fields to u32s with a maximum length of 12
// using a poseidon2 hasher
use std::hash::poseidon2::Poseidon2Hasher;
let mut map: HashMap<Field, u32, 12, BuildHasherDefault<Poseidon2Hasher>> = HashMap::default();

map.insert(1, 2);
map.insert(3, 4);

let two = map.get(1).unwrap();

Methods

default

default
impl<K, V, N, B, H> Default for HashMap<K, V, N, B>
where
B: BuildHasher<H> + Default,
H: Hasher + Default
{
fn default() -> Self {

Source code: noir_stdlib/src/collections/map.nr#L462-L469

Creates a fresh, empty HashMap.

When using this function, always make sure to specify the maximum size of the hash map.

This is the same default from the Default implementation given further below. It is repeated here for convenience since it is the recommended way to create a hashmap.

Example:

default_example
let hashmap: HashMap<u8, u32, 10, BuildHasherDefault<Poseidon2Hasher>> = HashMap::default();
assert(hashmap.is_empty());

Source code: test_programs/execution_success/hashmap/src/main.nr#L202-L205

Because HashMap has so many generic arguments that are likely to be the same throughout your program, it may be helpful to create a type alias:

type_alias
type MyMap = HashMap<u8, u32, 10, BuildHasherDefault<Poseidon2Hasher>>;

Source code: test_programs/execution_success/hashmap/src/main.nr#L196-L198

with_hasher

with_hasher
pub fn with_hasher(_build_hasher: B) -> Self
where
B: BuildHasher<H> {

Source code: noir_stdlib/src/collections/map.nr#L82-L86

Creates a hashmap with an existing BuildHasher. This can be used to ensure multiple hashmaps are created with the same hasher instance.

Example:

with_hasher_example
let my_hasher: BuildHasherDefault<Poseidon2Hasher> = Default::default();
let hashmap: HashMap<u8, u32, 10, BuildHasherDefault<Poseidon2Hasher>> = HashMap::with_hasher(my_hasher);
assert(hashmap.is_empty());

Source code: test_programs/execution_success/hashmap/src/main.nr#L207-L211

get

get
pub fn get(
self,
key: K
) -> Option<V>
where
K: Eq + Hash,
B: BuildHasher<H>,
H: Hasher {

Source code: noir_stdlib/src/collections/map.nr#L278-L287

Retrieves a value from the hashmap, returning Option::none() if it was not found.

Example:

get_example
fn get_example(map: HashMap<Field, Field, 5, BuildHasherDefault<Poseidon2Hasher>>) {
let x = map.get(12);

if x.is_some() {
assert(x.unwrap() == 42);
}
}

Source code: test_programs/execution_success/hashmap/src/main.nr#L299-L307

insert

insert
pub fn insert(
&mut self,
key: K,
value: V
)
where
K: Eq + Hash,
B: BuildHasher<H>,
H: Hasher {

Source code: noir_stdlib/src/collections/map.nr#L313-L323

Inserts a new key-value pair into the map. If the key was already in the map, its previous value will be overridden with the newly provided one.

Example:

insert_example
let mut map: HashMap<Field, Field, 5, BuildHasherDefault<Poseidon2Hasher>> = HashMap::default();
map.insert(12, 42);
assert(map.len() == 1);

Source code: test_programs/execution_success/hashmap/src/main.nr#L213-L217

remove

remove
pub fn remove(
&mut self,
key: K
)
where
K: Eq + Hash,
B: BuildHasher<H>,
H: Hasher {

Source code: noir_stdlib/src/collections/map.nr#L356-L365

Removes the given key-value pair from the map. If the key was not already present in the map, this does nothing.

Example:

remove_example
map.remove(12);
assert(map.is_empty());

// If a key was not present in the map, remove does nothing
map.remove(12);
assert(map.is_empty());

Source code: test_programs/execution_success/hashmap/src/main.nr#L221-L228

is_empty

is_empty
pub fn is_empty(self) -> bool {

Source code: noir_stdlib/src/collections/map.nr#L115-L117

True if the length of the hash map is empty.

Example:

is_empty_example
assert(map.is_empty());

map.insert(1, 2);
assert(!map.is_empty());

map.remove(1);
assert(map.is_empty());

Source code: test_programs/execution_success/hashmap/src/main.nr#L230-L238

len

len
pub fn len(self) -> u32 {

Source code: noir_stdlib/src/collections/map.nr#L264-L266

Returns the current length of this hash map.

Example:

len_example
// This is equivalent to checking map.is_empty()
assert(map.len() == 0);

map.insert(1, 2);
map.insert(3, 4);
map.insert(5, 6);
assert(map.len() == 3);

// 3 was already present as a key in the hash map, so the length is unchanged
map.insert(3, 7);
assert(map.len() == 3);

map.remove(1);
assert(map.len() == 2);

Source code: test_programs/execution_success/hashmap/src/main.nr#L240-L255

capacity

capacity
pub fn capacity(_self: Self) -> u32 {

Source code: noir_stdlib/src/collections/map.nr#L271-L273

Returns the maximum capacity of this hashmap. This is always equal to the capacity specified in the hashmap's type.

Unlike hashmaps in general purpose programming languages, hashmaps in Noir have a static capacity that does not increase as the map grows larger. Thus, this capacity is also the maximum possible element count that can be inserted into the hashmap. Due to hash collisions (modulo the hashmap length), it is likely the actual maximum element count will be lower than the full capacity.

Example:

capacity_example
let empty_map: HashMap<Field, Field, 42, BuildHasherDefault<Poseidon2Hasher>> = HashMap::default();
assert(empty_map.len() == 0);
assert(empty_map.capacity() == 42);

Source code: test_programs/execution_success/hashmap/src/main.nr#L257-L261

clear

clear
pub fn clear(&mut self) {

Source code: noir_stdlib/src/collections/map.nr#L93-L95

Clears the hashmap, removing all key-value pairs from it.

Example:

clear_example
assert(!map.is_empty());
map.clear();
assert(map.is_empty());

Source code: test_programs/execution_success/hashmap/src/main.nr#L263-L267

contains_key

contains_key
pub fn contains_key(
self,
key: K
) -> bool
where
K: Hash + Eq,
B: BuildHasher<H>,
H: Hasher {

Source code: noir_stdlib/src/collections/map.nr#L101-L110

True if the hashmap contains the given key. Unlike get, this will not also return the value associated with the key.

Example:

contains_key_example
if map.contains_key(7) {
let value = map.get(7);
assert(value.is_some());
} else {
println("No value for key 7!");
}

Source code: test_programs/execution_success/hashmap/src/main.nr#L269-L276

entries

entries
pub fn entries(self) -> BoundedVec<(K, V), N> {

Source code: noir_stdlib/src/collections/map.nr#L123-L125

Returns a vector of each key-value pair present in the hashmap.

The length of the returned vector is always equal to the length of the hashmap.

Example:

entries_example
let entries = map.entries();

// The length of a hashmap may not be compile-time known, so we
// need to loop over its capacity instead
for i in 0..map.capacity() {
if i < entries.len() {
let (key, value) = entries.get(i);
println(f"{key} -> {value}");
}
}

Source code: test_programs/execution_success/hashmap/src/main.nr#L310-L321

keys

keys
pub fn keys(self) -> BoundedVec<K, N> {

Source code: noir_stdlib/src/collections/map.nr#L144-L146

Returns a vector of each key present in the hashmap.

The length of the returned vector is always equal to the length of the hashmap.

Example:

keys_example
let keys = map.keys();

for i in 0..keys.max_len() {
if i < keys.len() {
let key = keys.get_unchecked(i);
let value = map.get(key).unwrap_unchecked();
println(f"{key} -> {value}");
}
}

Source code: test_programs/execution_success/hashmap/src/main.nr#L323-L333

values

values
pub fn values(self) -> BoundedVec<V, N> {

Source code: noir_stdlib/src/collections/map.nr#L164-L166

Returns a vector of each value present in the hashmap.

The length of the returned vector is always equal to the length of the hashmap.

Example:

values_example
let values = map.values();

for i in 0..values.max_len() {
if i < values.len() {
let value = values.get_unchecked(i);
println(f"Found value {value}");
}
}

Source code: test_programs/execution_success/hashmap/src/main.nr#L335-L344

iter_mut

iter_mut
pub fn iter_mut(
&mut self,
f: fn(K, V) -> (K, V)
)
where
K: Eq + Hash,
B: BuildHasher<H>,
H: Hasher {

Source code: noir_stdlib/src/collections/map.nr#L183-L192

Iterates through each key-value pair of the HashMap, setting each key-value pair to the result returned from the given function.

Note that since keys can be mutated, the HashMap needs to be rebuilt as it is iterated through. If this is not desired, use iter_values_mut if only values need to be mutated, or entries if neither keys nor values need to be mutated.

The iteration order is left unspecified. As a result, if two keys are mutated to become equal, which of the two values that will be present for the key in the resulting map is also unspecified.

Example:

iter_mut_example
// Add 1 to each key in the map, and double the value associated with that key.
map.iter_mut(|k, v| (k + 1, v * 2));

Source code: test_programs/execution_success/hashmap/src/main.nr#L348-L351

iter_keys_mut

iter_keys_mut
pub fn iter_keys_mut(
&mut self,
f: fn(K) -> K
)
where
K: Eq + Hash,
B: BuildHasher<H>,
H: Hasher {

Source code: noir_stdlib/src/collections/map.nr#L208-L217

Iterates through the HashMap, mutating each key to the result returned from the given function.

Note that since keys can be mutated, the HashMap needs to be rebuilt as it is iterated through. If only iteration is desired and the keys are not intended to be mutated, prefer using entries instead.

The iteration order is left unspecified. As a result, if two keys are mutated to become equal, which of the two values that will be present for the key in the resulting map is also unspecified.

Example:

iter_keys_mut_example
// Double each key, leaving the value associated with that key untouched
map.iter_keys_mut(|k| k * 2);

Source code: test_programs/execution_success/hashmap/src/main.nr#L353-L356

iter_values_mut

iter_values_mut
pub fn iter_values_mut(&mut self, f: fn(V) -> V) {

Source code: noir_stdlib/src/collections/map.nr#L233-L235

Iterates through the HashMap, applying the given function to each value and mutating the value to equal the result. This function is more efficient than iter_mut and iter_keys_mut because the keys are untouched and the underlying hashmap thus does not need to be reordered.

Example:

iter_values_mut_example
// Halve each value
map.iter_values_mut(|v| v / 2);

Source code: test_programs/execution_success/hashmap/src/main.nr#L358-L361

retain

retain
pub fn retain(&mut self, f: fn(K, V) -> bool) {

Source code: noir_stdlib/src/collections/map.nr#L247-L249

Retains only the key-value pairs for which the given function returns true. Any key-value pairs for which the function returns false will be removed from the map.

Example:

retain_example
map.retain(|k, v| (k != 0) & (v != 0));

Source code: test_programs/execution_success/hashmap/src/main.nr#L281-L283

Trait Implementations

default

default
impl<K, V, N, B, H> Default for HashMap<K, V, N, B>
where
B: BuildHasher<H> + Default,
H: Hasher + Default
{
fn default() -> Self {

Source code: noir_stdlib/src/collections/map.nr#L462-L469

Constructs an empty HashMap.

Example:

default_example
let hashmap: HashMap<u8, u32, 10, BuildHasherDefault<Poseidon2Hasher>> = HashMap::default();
assert(hashmap.is_empty());

Source code: test_programs/execution_success/hashmap/src/main.nr#L202-L205

eq

eq
impl<K, V, N, B, H> Eq for HashMap<K, V, N, B>
where
K: Eq + Hash,
V: Eq,
B: BuildHasher<H>,
H: Hasher
{
fn eq(self, other: HashMap<K, V, N, B>) -> bool {

Source code: noir_stdlib/src/collections/map.nr#L426-L435

Checks if two HashMaps are equal.

Example:

eq_example
let mut map1: HashMap<Field, u64, 4, BuildHasherDefault<Poseidon2Hasher>> = HashMap::default();
let mut map2: HashMap<Field, u64, 4, BuildHasherDefault<Poseidon2Hasher>> = HashMap::default();

map1.insert(1, 2);
map1.insert(3, 4);

map2.insert(3, 4);
map2.insert(1, 2);

assert(map1 == map2);

Source code: test_programs/execution_success/hashmap/src/main.nr#L285-L296