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

Loading page…