How do I work with IndexMap for Ordered Hash Maps in Rust?

Walkthrough

IndexMap is a crate that provides a hash map with insertion order preservation. Unlike std::collections::HashMap which has arbitrary iteration order, IndexMap maintains the order in which keys were inserted. It also provides O(1) element access by index.

Key concepts:

Insertion order — Keys are iterated in insertion order
Index-based access — Access elements by position (get_index)
IndexMap<K, V> — Ordered hash map type
IndexSet — Ordered hash set type
Entry API — Similar to HashMap's entry API

When to use IndexMap:

When insertion order matters
When you need index-based access to map entries
For deterministic serialization
When you need ordered JSON object keys

When NOT to use IndexMap:

Order doesn't matter (use HashMap)
Performance is critical and order isn't needed
Memory overhead is a concern
Need sorted order (use BTreeMap)

Code Examples

Basic IndexMap Usage

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    
    map.insert("apple", 3);
    map.insert("banana", 2);
    map.insert("cherry", 5);
    
    // Iteration preserves insertion order
    for (key, value) in &map {
        println!("{}: {}", key, value);
    }
}

Index-Based Access

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    map.insert("first", 1);
    map.insert("second", 2);
    map.insert("third", 3);
    
    // Access by index
    let (key, value) = map.get_index(0).unwrap();
    println!("Index 0: {} = {}", key, value);
    
    let (key, value) = map.get_index(1).unwrap();
    println!("Index 1: {} = {}", key, value);
    
    // Get index of a key
    let idx = map.get_index_of("second");
    println!("'second' is at index {:?}", idx);
}

IndexSet for Ordered Sets

use indexmap::IndexSet;
 
fn main() {
    let mut set = IndexSet::new();
    
    set.insert("red");
    set.insert("green");
    set.insert("blue");
    
    // Iterate in insertion order
    for color in &set {
        println!("Color: {}", color);
    }
    
    // Get by index
    let color = set.get_index(0).unwrap();
    println!("First color: {}", color);
}

Mutable Access by Index

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    map.insert("a", 10);
    map.insert("b", 20);
    map.insert("c", 30);
    
    // Mutate value by index
    if let Some((key, value)) = map.get_index_mut(1) {
        println!("Changing {}", key);
        *value = 25;
    }
    
    println!("Updated map: {:?}", map);
}

Remove and Shift

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    map.insert("d", 4);
    
    // Remove by key (shifts subsequent elements)
    let removed = map.remove("b");
    println!("Removed: {:?}", removed);
    
    // Now "c" is at index 1
    for (i, (k, v)) in map.iter().enumerate() {
        println!("Index {}: {} = {}", i, k, v);
    }
}

Swap and Pop

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    
    // Swap indices (fast - doesn't shift)
    map.swap_indices(0, 2);
    
    for (k, v) in &map {
        println!("{}: {}", k, v);
    }
    
    // Swap remove by key (O(1) but changes order)
    map.swap_remove("b");
    println!("After swap_remove: {:?}", map);
}

Entry API

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    
    // Use entry API similar to HashMap
    map.entry("apple").or_insert(5);
    map.entry("banana").or_insert(3);
    map.entry("apple").and_modify(|v| *v += 1);
    
    // Entry with default computation
    map.entry("cherry").or_insert_with(|| {
        println!("Creating default for cherry");
        10
    });
    
    println!("Map: {:?}", map);
}

Ordered JSON Serialization

use indexmap::IndexMap;
use serde_json::json;
 
fn main() {
    let mut map = IndexMap::new();
    map.insert("name", "Alice");
    map.insert("age", "30");
    map.insert("city", "Boston");
    
    // Keys will be serialized in insertion order
    let json = serde_json::to_string_pretty(&map).unwrap();
    println!("{}", json);
}

Insert at Position

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    map.insert("a", 1);
    map.insert("c", 3);
    
    // Insert at specific position
    map.insert_before("c", "b", 2);
    
    // Keys are now in order: a, b, c
    for (k, v) in &map {
        println!("{}: {}", k, v);
    }
}

Iteration Methods

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    
    // Iterate over keys
    for key in map.keys() {
        println!("Key: {}", key);
    }
    
    // Iterate over values
    for value in map.values() {
        println!("Value: {}", value);
    }
    
    // Iterate with indices
    for (idx, (key, value)) in map.iter().enumerate() {
        println!("Index {}: {} = {}", idx, key, value);
    }
}

Update Existing Entry Position

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    
    // Re-inserting existing key keeps its position
    map.insert("b", 20);
    
    // But you can move it
    map.move_index(1, 2);  // Move "b" from index 1 to index 2
    
    for (k, v) in &map {
        println!("{}: {}", k, v);
    }
}

Capacity Management

use indexmap::IndexMap;
 
fn main() {
    // Pre-allocate capacity
    let mut map: IndexMap<&str, i32> = IndexMap::with_capacity(100);
    
    println!("Capacity: {}", map.capacity());
    
    for i in 0..50 {
        map.insert(&format!("key{}", i), i);
    }
    
    println!("Len: {}, Capacity: {}", map.len(), map.capacity());
    
    // Shrink to fit
    map.shrink_to_fit();
    println!("After shrink: Capacity: {}", map.capacity());
}

Clear and Retain

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    map.insert("d", 4);
    
    // Retain only even values
    map.retain(|_k, v| *v % 2 == 0);
    
    println!("After retain: {:?}", map);
}

From/Into Other Collections

use indexmap::IndexMap;
use std::collections::HashMap;
 
fn main() {
    // From Vec of tuples
    let map: IndexMap<&str, i32> = vec![
        ("a", 1),
        ("b", 2),
        ("c", 3),
    ].into_iter().collect();
    
    println!("From Vec: {:?}", map);
    
    // To HashMap (loses order)
    let hash_map: HashMap<_, _> = map.into_iter().collect();
    println!("To HashMap: {:?}", hash_map);
}

Sorted by Value

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    map.insert("apple", 3);
    map.insert("banana", 2);
    map.insert("cherry", 5);
    
    // Sort by value
    map.sort_by(|_k1, v1, _k2, v2| v1.cmp(v2));
    
    for (k, v) in &map {
        println!("{}: {}", k, v);
    }
}

Sorted by Key

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    map.insert("cherry", 5);
    map.insert("apple", 3);
    map.insert("banana", 2);
    
    // Sort by key
    map.sort_keys();
    
    for (k, v) in &map {
        println!("{}: {}", k, v);
    }
}

First and Last Operations

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    
    // Get first entry
    let first = map.first();
    println!("First: {:?}", first);
    
    // Get last entry
    let last = map.last();
    println!("Last: {:?}", last);
    
    // Pop first
    let popped = map.shift_remove_index(0);
    println!("Popped first: {:?}", popped);
}

Split IndexMap

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    map.insert("d", 4);
    map.insert("e", 5);
    
    // Split at index
    let map2 = map.split_off(3);
    
    println!("Original: {:?}", map);
    println!("Split off: {:?}", map2);
}

Bulk Operations

use indexmap::IndexMap;
 
fn main() {
    let mut map1 = IndexMap::new();
    map1.insert("a", 1);
    map1.insert("b", 2);
    
    let mut map2 = IndexMap::new();
    map2.insert("c", 3);
    map2.insert("a", 10);  // Duplicate key
    
    // Extend (keeps order, overwrites duplicates)
    map1.extend(map2);
    
    println!("Extended: {:?}", map1);
}

Partition IndexMap

use indexmap::IndexMap;
 
fn main() {
    let mut map = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    map.insert("d", 4);
    
    // Partition into two maps
    let (even, odd): (IndexMap<_, _>, IndexMap<_, _>) = 
        map.into_iter().partition(|(_, v)| *v % 2 == 0);
    
    println!("Even: {:?}", even);
    println!("Odd: {:?}", odd);
}

Use as Ordered Configuration

use indexmap::IndexMap;
 
struct Config {
    values: IndexMap<String, String>,
}
 
impl Config {
    fn new() -> Self {
        Self {
            values: IndexMap::new(),
        }
    }
    
    fn set(&mut self, key: &str, value: &str) {
        self.values.insert(key.to_string(), value.to_string());
    }
    
    fn get(&self, key: &str) -> Option<&String> {
        self.values.get(key)
    }
    
    fn keys_in_order(&self) -> Vec<&String> {
        self.values.keys().collect()
    }
}
 
fn main() {
    let mut config = Config::new();
    config.set("host", "localhost");
    config.set("port", "8080");
    config.set("debug", "true");
    
    println!("Keys in order: {:?}", config.keys_in_order());
}

IndexMap for LRU-like Access

use indexmap::IndexMap;
 
struct Cache {
    data: IndexMap<String, String>,
    capacity: usize,
}
 
impl Cache {
    fn new(capacity: usize) -> Self {
        Self {
            data: IndexMap::new(),
            capacity,
        }
    }
    
    fn get(&mut self, key: &str) -> Option<&String> {
        if self.data.contains_key(key) {
            // Move to end (most recently used)
            let idx = self.data.get_index_of(key).unwrap();
            self.data.move_index(idx, self.data.len() - 1);
        }
        self.data.get(key)
    }
    
    fn put(&mut self, key: String, value: String) {
        if self.data.len() >= self.capacity {
            // Remove first (least recently used)
            self.data.shift_remove_index(0);
        }
        self.data.insert(key, value);
    }
}
 
fn main() {
    let mut cache = Cache::new(3);
    cache.put("a".to_string(), "1".to_string());
    cache.put("b".to_string(), "2".to_string());
    cache.put("c".to_string(), "3".to_string());
    
    cache.get("a");  // Access "a" - moves to end
    cache.put("d".to_string(), "4".to_string());  // Evicts "b"
    
    println!("Cache contents: {:?}", cache.data);
}

Summary

IndexMap Type Signature:

use indexmap::IndexMap;
 
let map: IndexMap<K, V> = IndexMap::new();

Key Methods:

Method	Description
`insert(k, v)`	Insert entry
`get(k)`	Get value by key
`get_index(i)`	Get (key, value) by index
`get_index_of(k)`	Get index of key
`remove(k)`	Remove by key (shifts)
`swap_remove(k)`	Remove by key (swaps, O(1))
`shift_remove_index(i)`	Remove by index
`swap_indices(i, j)`	Swap two entries
`move_index(from, to)`	Move entry to new position
`sort_keys()`	Sort by key
`sort_by(cmp)`	Sort by comparator
`first()`	Get first entry
`last()`	Get last entry
`split_off(at)`	Split into two maps

IndexMap vs HashMap vs BTreeMap:

Feature	IndexMap	HashMap	BTreeMap
Iteration order	Insertion	Arbitrary	Sorted
Index access	O(1)	No	No
Key lookup	O(1)	O(1)	O(log n)
Ordered keys	Yes (insertion)	No	Yes (sorted)
Memory overhead	Higher	Lower	Lower

Key Points:

Maintains insertion order
Use get_index() for position-based access
Use get_index_of() to find key's position
remove() shifts, swap_remove() swaps (faster but changes order)
Use sort_keys() or sort_by() for sorted order
Works with serde for ordered JSON serialization
Use IndexSet for ordered sets
Great for configuration and ordered data structures