LinkedHashMap

The LinkedHashMap combines a HashMap and a LinkedList for O(1) inserts, lookups and deletes along with a predictable iteration order.

All the basic functions - get(), get_mut(), get_key_value(), put(), insert(), remove(), remove_entry() - provide constant time performance which is expected to be lower than that of the Hashmap given the added expense of of maintaining and updating the underlying linked list.

Getting Started

use deepmesa::collections::LinkedHashMap;
use deepmesa::collections::map::Order;

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

assert_eq!(lhm.get(&1), Some(&"a"));
assert_eq!(lhm.get(&2), Some(&"b"));

if let Some(val) = lhm.get_mut(&1) {
    *val = "d";
}

assert_eq!(lhm.get(&1), Some(&"d"));

Iteration Order

This map holds a LinkedList of all the elements that defines the iteration order. The order is either InsertionOrder or AccessOrder. InsertionOrder is the order in which the keys were inserted into the map from least recently inserted (oldest) to most recently inserted (newest). ReInserting a key (via the insert or put methods) will change the insertion order to make the re-inserted key the most recently inserted (newest) in the order.

AccessOrder is the order in which the keys in the map were last accessed (via the get(), get_key_value(), get_mut() methods) from least-recently accessed (oldest) to most recently accessed (newest). Iterating over the map using one of the iterators - iter(), iter_mut(), keys(), values(), values_mut() - does not affect the order.

Iteration over the map requires time proportional to the length of the map (O(len)) regardless of the capacity because it iterates over the elements of the underlying linked list. The iteration order of the map is always from oldest entry (accessed or inserted) to the newest entry (accessed or inserted).

The map offers iterators over the elements, keys and values with mutable iterators for elements and values. The iterators can also be reversed.

// Construct a map in InsertionOrder
use deepmesa::collections::LinkedHashMap;
use deepmesa::collections::map::Order;

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

lhm.get(&1);

let mut iter = lhm.iter();
assert_eq!(iter.next(), Some((&1, &"a")));
assert_eq!(iter.next(), Some((&2, &"b")));
assert_eq!(iter.next(), None);
iter = iter.reverse();
assert_eq!(iter.next(), Some((&2, &"b")));
assert_eq!(iter.next(), Some((&1, &"a")));
assert_eq!(iter.next(), None);


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

lhm.get(&1);

let mut iter = lhm.iter();
assert_eq!(iter.next(), Some((&2, &"b")));
assert_eq!(iter.next(), Some((&1, &"a")));
assert_eq!(iter.next(), None);
iter = iter.reverse();
assert_eq!(iter.next(), Some((&1, &"a")));
assert_eq!(iter.next(), Some((&2, &"b")));
assert_eq!(iter.next(), None);

Evicting Elements

The Map also supports construction with an evict_eldest function that can be provided to implement a policy for removing entries when new elements are added to the map. A LinkedHashMap with AccessOrder and an eviction function is well suited to building an LRU Cache.

use deepmesa::collections::map::Entry;
pub fn evict<K,V>(len: usize, capacity: usize, e: &Entry<K, V>) -> bool {
    if len > capacity {
        return true;
    }
    return false;
}

use deepmesa::collections::LinkedHashMap;
use deepmesa::collections::map::Order;

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

assert_eq!(lhm.get(&2), Some(&"b"));
lhm.put(4, "d");
assert_eq!(lhm.get(&1), None);