A Fast LinkedHashMap in Rust

A while back I built a linkedlist in rust that’s twice as fast as the one in the standard library and is easy to use. The LinkedHashMap builds directly on top of it. In this post I’ll walk through a few ways to use it.

The deepmesa_collections::LinkedHashMap combines a HashMap and a LinkedList to give you O(1) inserts, lookups and deletes along with a predictable iteration order.

The standard library’s HashMap makes no promises about the order you get entries back in — and it deliberately randomizes that order between runs. Most of the time that’s fine. But when you need to iterate entries in the order they were inserted, or build an LRU cache that evicts the least recently used entry, you need the map and a list to stay in sync. The LinkedHashMap does exactly that, in constant time, without you having to wire the two together by hand.

All the basic functions — get(), get_mut(), insert(), put(), remove() and remove_entry() — run in constant time. They carry a little more overhead than the bare HashMap because every operation also keeps the underlying linked list up to date, but the asymptotic cost is the same.

Getting Started

Add the deepmesa-collections crate as a dependency in your Cargo.toml and bring the types you need into scope.

[dependencies]
deepmesa-collections = "0.14.0"

The map is generic over a key K (which must be Hash + Eq) and a value V. The simplest way to construct one is with_capacity(), which defaults to insertion order.

use deepmesa_collections::LinkedHashMap;

let mut map = LinkedHashMap::<u16, &str>::with_capacity(10);
map.put(1, "a");
map.put(2, "b");
map.put(3, "c");

assert_eq!(map.get(&2), Some(&"b"));

// iteration follows insertion order
let keys: Vec<_> = map.keys().copied().collect();
assert_eq!(keys, vec![1, 2, 3]);

There are two ways to add an entry: put() inserts a key/value pair and returns nothing, while insert() returns the previous value for that key if one existed (just like the standard library).

Insertion Order vs. Access Order

The behavior that makes a LinkedHashMap interesting is its iteration order, and you choose it at construction time with the Order enum:

Order::InsertionOrder — entries iterate from the oldest insertion to the newest. This is what with_capacity() gives you.
Order::AccessOrder — entries iterate from the least recently accessed to the most recently accessed. Every call to get(), get_mut() or get_key_value() moves that key to the most-recent end.

To pick the order explicitly, use new(), which takes a capacity, an Order, and an optional eviction callback (more on that below).

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let mut map = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
map.put(1, "a");
map.put(2, "b");

// reading key 1 moves it to the most-recent end
assert_eq!(map.get(&1), Some(&"a"));

let keys: Vec<_> = map.keys().copied().collect();
assert_eq!(keys, vec![2, 1]);

This is worth pausing on: because access order is tracked on reads, get() takes &mut self, not &self. Reading from the map can reorder it.

Capacity & Reallocation

Like the LinkedList it’s built on, the LinkedHashMap preallocates memory so it isn’t allocating and freeing nodes on every insert. The capacity() is the number of entries it can hold before it has to allocate more, and the len() is the number of entries it currently holds.

When the length reaches the capacity and you add another entry, the map grows. If it was constructed with a non-zero capacity, the capacity doubles on each growth. If you construct it with a capacity of zero, it preallocates nothing and grows one entry at a time. Removing keys frees the entries but does not shrink the allocated capacity, so the memory stays available for future inserts.

As with the list, set a realistic capacity up front whenever you can — it saves the map from a series of doubling reallocations as it fills.

Building an LRU Cache

Put access order together with the eviction callback and you get an LRU cache in a few lines. The third argument to new() is an optional function that runs on every insert. It receives the current length, the capacity, and a reference to the head (least-recent) Entry; if it returns true, the head entry is evicted.

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::{Entry, Order};

// Evict the oldest entry whenever we exceed capacity.
fn evict<K, V>(len: usize, capacity: usize, _e: &Entry<K, V>) -> bool {
    len > capacity
}

let mut cache = LinkedHashMap::<u16, &str>::new(3, Order::AccessOrder, Some(evict));
cache.put(1, "a");
cache.put(2, "b");
cache.put(3, "c");

// touch key 2 so it's now the most recently used
assert_eq!(cache.get(&2), Some(&"b"));

// inserting a 4th entry evicts the least recently used key (1)
cache.put(4, "d");
assert_eq!(cache.get(&1), None);

Because the eviction callback gets the head entry, you aren’t limited to a strict size cap — you can evict based on the entry’s contents, a time-to-live stored in the value, or anything else you can compute.

Entry Handles

Sometimes you want to reach into a specific entry — read it or move it within the ordering — without disturbing the access-order tracking that a get() would trigger. That’s what handles are for.

entry_handle() returns an EntryHandle<K, V> for a key. You can read through it with get_entry(), get_value() and get_value_mut(), or reposition the entry in O(1) with make_head() and make_tail() — all without counting as an access.

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let mut map = LinkedHashMap::<u16, &str>::new(10, Order::InsertionOrder, None);
map.insert(1, "a");
map.insert(2, "b");
map.insert(3, "c");

// move key 1 to the tail without registering an access
if let Some(handle) = map.entry_handle(&1) {
    map.make_tail(handle);
}

let keys: Vec<_> = map.keys().copied().collect();
assert_eq!(keys, vec![2, 3, 1]);

Like the node handles vended by the LinkedList, entry handles can be passed around by value, and the map’s handle-based methods return None if the handle no longer points at a live entry — so using a stale handle is safe.

Head & Tail

Because the ordering is a real linked list under the hood, you can work with both ends directly. head() and tail() peek at the oldest and newest entries, and remove_head() / remove_tail() pop them — handy if you’d rather drive eviction yourself instead of using the callback.

use deepmesa_collections::LinkedHashMap;

let mut map = LinkedHashMap::<u16, &str>::with_capacity(10);
map.put(1, "a");
map.put(2, "b");
map.put(3, "c");

assert_eq!(map.head(), Some((&1, &"a"))); // oldest
assert_eq!(map.tail(), Some((&3, &"c"))); // newest

// evict the oldest entry by hand
assert_eq!(map.remove_head(), Some((1, "a")));
assert_eq!(map.len(), 2);

Iterators

Finally, the map iterates in whichever order you configured. iter() and iter_mut() walk key/value pairs, while keys(), values() and values_mut() give you one half at a time. Iterating runs in O(n) over the number of entries — not the capacity — and, importantly, iteration itself does not change the access order.

use deepmesa_collections::LinkedHashMap;

let mut map = LinkedHashMap::<u16, u16>::with_capacity(10);
for i in 0..5 {
    map.put(i, i * 10);
}

for (k, v) in map.iter() {
    println!("{k} => {v}");
}
// prints, in insertion order:
// 0 => 0
// 1 => 10
// 2 => 20
// 3 => 30
// 4 => 40

That’s the whirlwind tour: a hash map with the lookup performance you expect, the iteration order you choose, and an LRU cache hiding inside it whenever you need one. The full API is on docs.rs.