#hash-set #no-std #linked-hash-map #detail #ordered-hash-set

no-std ordered_hash_map

HashMap which preserves insertion order

5 releases (3 breaking)

0.4.0 Nov 12, 2023
0.3.1 Nov 10, 2023
0.3.0 Nov 10, 2023
0.2.0 Mar 4, 2023
0.1.0 Mar 1, 2023

#1262 in Data structures

Download history 153/week @ 2024-03-13 132/week @ 2024-03-20 183/week @ 2024-03-27 187/week @ 2024-04-03 147/week @ 2024-04-10 233/week @ 2024-04-17 230/week @ 2024-04-24 167/week @ 2024-05-01 177/week @ 2024-05-08 501/week @ 2024-05-15 228/week @ 2024-05-22 457/week @ 2024-05-29 454/week @ 2024-06-05 245/week @ 2024-06-12 313/week @ 2024-06-19 392/week @ 2024-06-26

1,493 downloads per month
Used in 5 crates

BSD-2-Clause

94KB
2K SLoC

OrderedHashMap

A HashMap (and Set) which preserves insertion order.

This crate provides a no_std implementation of a Ordered Hash Map (and it's corresponding Set) using as little unsafe as possible. MIRI is used to audit the unsafe which does exist.

The API aims to match the standard library HashMap/Set with additional LinkedList style methods and ordered-itertors.

Changelog

Details

This crate is powered by hashbrown, leveraging the already well vetted HashMap implementation and added the bits required to implement a LinkedList within the map. The additional memory footprint of the OrderedHashMap over the hashbrown HashMap is 2 pointers upon making a collection + 3 pointers per element. The pointers arise from the LinkedList where the collection itself has a pointer to the head and the tail, each node has a pointer to the next and previous node, and the Key in the map is a pointer into the Value where it lives.

Features

serde - Enable serde Serialization and Deserialization

Usage

use ordered_hash_map::OrderedHashMap;

let mut map: OrderedHashMap<_, _> = [(1, "one"), (2, "two")].into_iter().collect();
map.insert(3, "three");
assert_eq!(map.iter().next(), Some((&1, &"one")));

Dependencies

~2MB
~26K SLoC