Arc<Mutex>

Guides

Rust walkthroughs

← Back to all guides

What are the trade-offs between indexmap::IndexMap::get_index and get for accessing entries by position vs key?

IndexMap::get accesses entries by key with O(1) average lookup time, while get_index accesses entries by insertion position with O(1) time, enabling ordered iteration and position-based operations that aren't possible with standard hash maps. The fundamental difference is the access pattern: get uses a hash table for key-based lookups (like HashMap), while get_index exploits IndexMap's internal order-preserving structure to access elements by their sequential position. Both are O(1), but they serve different use cases—get for key-based retrieval and get_index for position-based access when you need to treat the map as an ordered sequence.

IndexMap's Dual Nature

use indexmap::IndexMap;
 
fn dual_nature() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    
    map.insert("first", 1);
    map.insert("second", 2);
    map.insert("third", 3);
    
    // IndexMap maintains insertion order
    // Internally: both a hash table AND a sequential array
    
    // Access by key (like HashMap)
    let value = map.get("second");     // Some(&2)
    
    // Access by position (like Vec)
    let (key, value) = map.get_index(1);  // Some((&"second", &2))
    
    // Both operations are O(1)
    // - get: hashes key, looks up in hash table
    // - get_index: indexes into internal array
}

IndexMap combines hash table key lookups with array-based ordered storage.

get: Key-Based Lookup

use indexmap::IndexMap;
 
fn get_by_key() {
    let mut map: IndexMap<String, u32> = IndexMap::new();
    map.insert("apple".to_string(), 1);
    map.insert("banana".to_string(), 2);
    map.insert("cherry".to_string(), 3);
    
    // get returns Option<&V>
    let value: Option<&u32> = map.get("banana");
    assert_eq!(value, Some(&2));
    
    // get returns None for missing keys
    let missing = map.get("grape");
    assert_eq!(missing, None);
    
    // get_key_value returns Option<(&K, &V)>
    let entry = map.get_key_value("cherry");
    assert_eq!(entry, Some((&"cherry".to_string(), &3)));
    
    // Works exactly like HashMap::get
    // Same O(1) average time complexity
}

get provides familiar key-based lookup identical to HashMap.

get_index: Position-Based Access

use indexmap::IndexMap;
 
fn get_by_position() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    
    // get_index returns Option<(&K, &V)>
    let first = map.get_index(0);
    assert_eq!(first, Some((&"a", &1)));
    
    let second = map.get_index(1);
    assert_eq!(second, Some((&"b", &2)));
    
    // Returns None for out-of-bounds
    let invalid = map.get_index(10);
    assert_eq!(invalid, None);
    
    // get_index_mut returns Option<(&K, &mut V)>
    // (Note: key is still shared reference)
    if let Some((key, value)) = map.get_index_mut(2) {
        assert_eq!(key, &"c");
        *value = 33;
    }
}

get_index retrieves entries by their position in insertion order.

The Position Semantics

use indexmap::IndexMap;
 
fn position_semantics() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    
    // Positions are assigned in insertion order
    map.insert("first", 1);   // position 0
    map.insert("second", 2);  // position 1
    map.insert("third", 3);   // position 2
    
    // Re-inserting same key doesn't change position
    map.insert("first", 10);  // Still position 0, value updated
    
    assert_eq!(map.get_index(0), Some((&"first", &10)));
    assert_eq!(map.len(), 3);  // Still 3 entries
    
    // Removing shifts subsequent positions
    map.remove("first");  // Removes position 0
    
    assert_eq!(map.get_index(0), Some((&"second", &2)));  // "second" now at 0
    assert_eq!(map.get_index(1), Some((&"third", &3)));    // "third" now at 1
    
    // Position is meaningful and stable relative to operations
}

Positions shift when entries are removed—subsequent entries move up.

Use Case: Ordered Iteration by Key

use indexmap::IndexMap;
 
fn ordered_iteration() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    map.insert("zebra", 1);
    map.insert("alpha", 2);
    map.insert("beta", 3);
    
    // Standard HashMap: iteration order is undefined
    // IndexMap: iteration follows insertion order
    
    // Access entries in insertion order using get_index
    for i in 0..map.len() {
        if let Some((key, value)) = map.get_index(i) {
            println!("{}: {} => {}", i, key, value);
        }
    }
    // Output:
    // 0: zebra => 1
    // 1: alpha => 2
    // 2: beta => 3
    
    // This is also what .iter() gives you
    for (key, value) in map.iter() {
        println!("{} => {}", key, value);
    }
}

get_index enables random access to entries in insertion order.

Use Case: Finding Position of a Key

use indexmap::IndexMap;
 
fn find_position() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    map.insert("first", 1);
    map.insert("second", 2);
    map.insert("third", 3);
    
    // get_full returns (index, &K, &V) - position AND entry
    if let Some((index, key, value)) = map.get_full("second") {
        println!("'second' is at position {}", index);
        println!("Value: {}", value);
    }
    
    // Useful when you need both the position and the entry
    // Like finding the index of an element in a Vec
}

get_full returns position alongside key and value for key-based lookups.

Use Case: Indexed Modification

use indexmap::IndexMap;
 
fn indexed_modification() {
    let mut map: IndexMap<String, i32> = IndexMap::new();
    map.insert("counter".to_string(), 0);
    
    // Modify by key (like HashMap)
    if let Some(value) = map.get_mut("counter") {
        *value += 1;
    }
    
    // Modify by position (IndexMap unique feature)
    if let Some((key, value)) = map.get_index_mut(0) {
        // key is &K (shared), value is &mut V
        *value += 10;
    }
    
    assert_eq!(map.get("counter"), Some(&11));
}

get_index_mut enables position-based modification.

Swapping and Moving Entries

use indexmap::IndexMap;
 
fn swap_and_move() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    map.insert("c", 3);
    
    // swap_indices swaps entries at two positions
    map.swap_indices(0, 2);
    
    // Now: c is at position 0, a is at position 2
    assert_eq!(map.get_index(0), Some((&"c", &3)));
    assert_eq!(map.get_index(2), Some((&"a", &1)));
    
    // move_index moves entry from one position to another
    let mut map2: IndexMap<&str, i32> = IndexMap::new();
    map2.insert("x", 1);
    map2.insert("y", 2);
    map2.insert("z", 3);
    
    // Move "x" from position 0 to position 2
    map2.move_index(0, 2);
    
    // Order is now: y, z, x
    assert_eq!(map2.get_index(0), Some((&"y", &2)));
    assert_eq!(map2.get_index(1), Some((&"z", &3)));
    assert_eq!(map2.get_index(2), Some((&"x", &1)));
}

IndexMap provides position manipulation operations unavailable in HashMap.

Performance Characteristics

use indexmap::IndexMap;
use std::collections::HashMap;
 
fn performance_comparison() {
    // HashMap::get
    // - Time: O(1) average, O(n) worst case (hash collisions)
    // - Memory: hash table overhead
    // - Access: Key only
    
    // IndexMap::get
    // - Time: O(1) average, O(n) worst case
    // - Memory: hash table + array
    // - Access: Key only
    
    // IndexMap::get_index
    // - Time: O(1) always (array indexing)
    // - Memory: array overhead
    // - Access: Position only
    
    // The "position" in IndexMap is essentially an array index
    // Accessing by position is literally: internal_array[position]
    // This is why it's O(1) and very fast
    
    // HashMap has no equivalent - no position concept
}

Both get and get_index are O(1), but get_index is simpler array indexing.

Comparison with HashMap

use indexmap::IndexMap;
use std::collections::HashMap;
 
fn vs_hashmap() {
    // HashMap: Key -> Value
    // - get(key): O(1)
    // - No position concept
    // - Iteration order undefined
    
    // IndexMap: Key -> Value WITH order preservation
    // - get(key): O(1)
    // - get_index(position): O(1)
    // - Iteration follows insertion order
    
    let mut hash: HashMap<&str, i32> = HashMap::new();
    hash.insert("a", 1);
    hash.insert("b", 2);
    
    // HashMap has no equivalent to get_index
    // No way to access "first inserted" or "second inserted"
    
    let mut index: IndexMap<&str, i32> = IndexMap::new();
    index.insert("a", 1);
    index.insert("b", 2);
    
    // IndexMap can do both:
    let by_key = index.get("a");
    let by_pos = index.get_index(0);
    
    // Both give access to same entries, just different access patterns
}

IndexMap provides get_index as a capability HashMap cannot offer.

Comparison with Vec

use indexmap::IndexMap;
 
fn vs_vec() {
    // Vec<(K, V)>: Position -> (K, V)
    // - get(index): O(1)
    // - Finding by key: O(n)
    
    // IndexMap: Key -> Value AND Position -> (K, V)
    // - get(key): O(1)
    // - get_index(position): O(1)
    
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    map.insert("apple", 1);
    map.insert("banana", 2);
    
    // IndexMap: Both operations are O(1)
    // Vec: Only positional access is O(1)
    
    // Use IndexMap when:
    // - You need both key lookup AND positional access
    // - You need insertion order preserved
    // - You need efficient removal without losing order
    
    // Use Vec when:
    // - You only need positional access
    // - You don't need key lookup
    // - Memory efficiency is critical
}

IndexMap bridges the gap between HashMap and Vec.

Practical Example: Ordered Configuration

use indexmap::IndexMap;
 
fn ordered_config() {
    // Configuration where order matters
    let mut config: IndexMap<String, String> = IndexMap::new();
    
    config.insert("database_url".to_string(), "postgres://localhost".to_string());
    config.insert("redis_url".to_string(), "redis://localhost".to_string());
    config.insert("api_key".to_string(), "secret".to_string());
    
    // Access by key for specific settings
    if let Some(db_url) = config.get("database_url") {
        println!("Connecting to: {}", db_url);
    }
    
    // Access by position for ordered display
    println!("Configuration (in order):");
    for i in 0..config.len() {
        if let Some((key, value)) = config.get_index(i) {
            println!("  {}: {} = {}", i, key, value);
        }
    }
    
    // Or simply use iter() for ordered iteration
    for (key, value) in config.iter() {
        println!("{} = {}", key, value);
    }
}

IndexMap naturally handles use cases requiring both key lookup and ordered access.

Practical Example: LRU Cache Position Tracking

use indexmap::IndexMap;
 
fn lru_operations() {
    // LRU (Least Recently Used) cache uses position for recency
    
    let mut cache: IndexMap<String, String> = IndexMap::new();
    
    // Insert items
    cache.insert("page1".to_string(), "data1".to_string());
    cache.insert("page2".to_string(), "data2".to_string());
    cache.insert("page3".to_string(), "data3".to_string());
    
    // Access "page1" - should move to "most recent" position
    // (In a real LRU, you'd use move_index to reposition)
    
    fn access_lru(cache: &mut IndexMap<String, String>, key: &str) -> Option<&String> {
        // Get the position of the key
        let (index, _, value) = cache.get_full(key)?;
        
        // Move to end (most recently used position)
        let new_index = cache.len() - 1;
        if index != new_index {
            cache.move_index(index, new_index);
        }
        
        cache.get(key)
    }
    
    // Least recently used is now at position 0
    // Most recently used is at position len-1
}

IndexMap's position operations enable efficient LRU cache implementations.

Memory Layout

use indexmap::IndexMap;
 
fn memory_layout() {
    // IndexMap internal structure (simplified):
    //
    // struct IndexMap<K, V> {
    //     entries: Vec<(K, V)>,           // Dense array
    //     indices: HashTable<usize>,     // Hash map: K -> index
    // }
    //
    // get(key):
    // 1. Hash the key
    // 2. Look up index in hash table
    // 3. Access entries[index]
    // 4. Return &V
    
    // get_index(position):
    // 1. Access entries[position]
    // 2. Return (&K, &V)
    
    // This is why both operations are O(1):
    // - get: hash + array access
    // - get_index: direct array access
    
    // Memory overhead compared to HashMap:
    // - Additional: Vec entries (but HashMap also stores entries)
    // - Similar total memory, different organization
    
    let map: IndexMap<i32, i32> = IndexMap::new();
    // Memory: entries array + hash table for indices
}

Understanding the internal structure explains the O(1) performance.

API Summary

use indexmap::IndexMap;
 
fn api_summary() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    map.insert("a", 1);
    map.insert("b", 2);
    
    // By key:
    // - get(&K) -> Option<&V>
    // - get_mut(&K) -> Option<&mut V>
    // - get_key_value(&K) -> Option<(&K, &V)>
    // - get_full(&K) -> Option<(usize, &K, &V)>
    
    // By position:
    // - get_index(usize) -> Option<(&K, &V)>
    // - get_index_mut(usize) -> Option<(&K, &mut V)>
    
    // Modify positions:
    // - swap_indices(usize, usize)
    // - move_index(usize, usize)
    
    // Find position:
    // - get_full(&K) returns position
    
    // Difference from HashMap:
    // - HashMap has no position-based methods
    // - HashMap iteration order is undefined
    
    // Difference from Vec:
    // - Vec has position access, but O(n) key lookup
    // - IndexMap has O(1) for both
}

IndexMap provides comprehensive key and position-based APIs.

When to Use Each

use indexmap::IndexMap;
 
fn when_to_use() {
    // Use get() when:
    // - You have a key and need the value
    // - Behavior should match HashMap usage
    // - You don't care about position
    
    // Use get_index() when:
    // - You need the Nth entry in insertion order
    // - Implementing ordered map algorithms
    // - You need both key and value for a position
    // - Building LRU caches or similar structures
    
    // Use IndexMap instead of HashMap when:
    // - Insertion order matters
    // - You need position-based access
    // - You need to iterate in insertion order
    
    // Use IndexMap instead of Vec<(K, V)> when:
    // - You need O(1) key lookup
    // - You still want position-based access
}

Choose based on whether you need position-based operations alongside key lookup.

Synthesis

Quick reference:

use indexmap::IndexMap;
 
fn quick_reference() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    map.insert("first", 1);
    map.insert("second", 2);
    map.insert("third", 3);
    
    // get: Access by key (O(1))
    let value = map.get("second");      // Some(&2)
    
    // get_index: Access by position (O(1))
    let entry = map.get_index(1);       // Some((&"second", &2))
    
    // get returns Option<&V>
    // get_index returns Option<(&K, &V)>
    
    // Use get when:
    // - You have a key and need a value
    // - Standard map lookup behavior
    
    // Use get_index when:
    // - You need entry at specific position
    // - Working with insertion order
    // - Need both key and value from position
    
    // Both are O(1) but serve different purposes:
    // - get: hash lookup -> array access
    // - get_index: direct array access
    
    // Position is meaningful in IndexMap:
    // - 0 is first inserted
    // - len-1 is last inserted
    // - Position changes on removal (shifts down)
}
 
// Key insight:
// IndexMap gives you both HashMap::get(key) and Vec::get(index)
// Both are O(1) - you don't sacrifice performance for dual access

Key insight: IndexMap::get and get_index provide two orthogonal access patterns over the same data structure. The get method is the familiar key-to-value lookup inherited from HashMap—hash the key, find the bucket, return the value. The get_index method exploits IndexMap's internal architecture: entries are stored in a contiguous array alongside the hash table, making positional access a simple array index operation. Both are O(1), but they answer different questions: "what's the value for key X?" versus "what's the entry at position N?" This dual nature makes IndexMap ideal when you need both key lookup and ordered access—implementing ordered configuration maps, LRU caches, or any structure where insertion order matters. Use get for key-based retrieval (the common case), and get_index when position is meaningful (ordered access, position-based algorithms). The trade-off is memory overhead compared to HashMap, but for many applications, the O(1) dual access pattern is worth the cost.