How does `indexmap::IndexSet` differ from `std::collections::HashSet` and when would you choose one?

IndexSet from the indexmap crate preserves insertion order while maintaining hash-based uniqueness, whereas HashSet from the standard library provides no ordering guarantees. Both offer O(1) average-case lookup, insertion, and deletion, but IndexSet additionally supports index-based access to elements in insertion order. The ordering guarantee comes at the cost of additional memory overhead and slightly different performance characteristics. Choose IndexSet when you need predictable iteration order or position-based access; use HashSet when you only need uniqueness with maximum performance.

Basic Creation and Insertion

use std::collections::HashSet;
use indexmap::IndexSet;
 
fn basic_usage() {
    // HashSet - order not guaranteed
    let mut hash_set: HashSet<&str> = HashSet::new();
    hash_set.insert("apple");
    hash_set.insert("banana");
    hash_set.insert("cherry");
    
    // Iteration order is unpredictable
    for item in &hash_set {
        println!("{}", item);  // Order varies between runs/versions
    }
    
    // IndexSet - preserves insertion order
    let mut index_set: IndexSet<&str> = IndexSet::new();
    index_set.insert("apple");
    index_set.insert("banana");
    index_set.insert("cherry");
    
    // Iteration order is guaranteed: apple, banana, cherry
    for item in &index_set {
        println!("{}", item);  // Always in insertion order
    }
}

IndexSet maintains the order in which elements were first inserted.

Iteration Order Guarantees

use std::collections::HashSet;
use indexmap::IndexSet;
 
fn iteration_order() {
    // HashSet iteration order depends on hash values and internal state
    let mut set1: HashSet<i32> = HashSet::new();
    set1.insert(1);
    set1.insert(2);
    set1.insert(3);
    
    let mut set2: HashSet<i32> = HashSet::new();
    set2.insert(3);
    set2.insert(2);
    set2.insert(1);
    
    // set1 and set2 may iterate in the same order despite different insertion order!
    // The order depends on hash values, not insertion order
    
    // IndexSet iteration order reflects insertion order
    let mut idx1: IndexSet<i32> = IndexSet::new();
    idx1.insert(1);
    idx1.insert(2);
    idx1.insert(3);
    
    let mut idx2: IndexSet<i32> = IndexSet::new();
    idx2.insert(3);
    idx2.insert(2);
    idx2.insert(1);
    
    // idx1 iterates: 1, 2, 3
    // idx2 iterates: 3, 2, 1
    // Order is deterministic and matches insertion order
}

HashSet order depends on hash values; IndexSet order reflects insertion sequence.

Index-Based Access

use indexmap::IndexSet;
 
fn index_access() {
    let mut set: IndexSet<&str> = IndexSet::new();
    set.insert("first");
    set.insert("second");
    set.insert("third");
    
    // Access by index - HashSet cannot do this
    let first = set[0];       // "first"
    let second = set[1];      // "second"
    let third = set[2];       // "third"
    
    // get() returns reference with index
    let (index, value) = set.get_full("second").unwrap();
    println!("'second' is at index {}: {:?}", index, value);
    
    // get_index returns element at position
    let at_one = set.get_index(1);  // Some(&"second")
    
    // Iterate with indices
    for (index, value) in set.iter().enumerate() {
        println!("{}: {}", index, value);
    }
}

IndexSet provides array-like indexed access to elements in insertion order.

Getting Indices and Positions

use indexmap::IndexSet;
 
fn position_operations() {
    let mut set: IndexSet<&str> = IndexSet::new();
    set.insert("a");
    set.insert("b");
    set.insert("c");
    
    // Get the index of an element
    let pos = set.get_index_of("b");  // Some(1)
    let not_found = set.get_index_of("z");  // None
    
    // Get element and its index together
    if let Some((idx, value)) = set.get_full("c") {
        println!("Found '{}' at index {}", value, idx);  // Found 'c' at index 2
    }
    
    // Get mutable reference with index
    if let Some((idx, value)) = set.get_full_mut("a") {
        println!("Modifying element at index {}", idx);
        // Note: cannot modify in a way that would change hash
    }
}

IndexSet can tell you the position of any element in insertion order.

Reinsertion Behavior

use indexmap::IndexSet;
 
fn reinsertion() {
    let mut set: IndexSet<&str> = IndexSet::new();
    
    set.insert("first");
    set.insert("second");
    set.insert("third");
    
    // Reinserting doesn't change position
    set.insert("second");  // Returns false (already present)
    
    // Order is still: first, second, third
    // "second" stays at index 1
    
    // Check iteration order
    for (i, item) in set.iter().enumerate() {
        println!("{}: {}", i, item);
    }
    // Output:
    // 0: first
    // 1: second
    // 2: third
}

Reinserting an existing element doesn't change its position in IndexSet.

Removal and Order Preservation

use indexmap::IndexSet;
 
fn removal_behavior() {
    let mut set: IndexSet<&str> = IndexSet::new();
    set.insert("a");
    set.insert("b");
    set.insert("c");
    set.insert("d");
    
    // swap_remove - swaps with last element (fast, changes order)
    set.swap_remove("b");
    // Order now: a, d, c (d swapped into b's position)
    
    set.clear();
    set.insert("a");
    set.insert("b");
    set.insert("c");
    set.insert("d");
    
    // shift_remove - shifts elements to fill gap (slower, preserves order)
    set.shift_remove("b");
    // Order now: a, c, d (c and d shifted left)
    
    // remove is alias for swap_remove by default
    set.remove("c");  // Uses swap_remove semantics
}

IndexSet offers two removal strategies: swap_remove for speed, shift_remove for order preservation.

Performance Characteristics

use std::collections::HashSet;
use indexmap::IndexSet;
 
// Operation complexity comparison:
//
// Operation          | HashSet      | IndexSet
// --------------------|--------------|-----------------
// Insert              | O(1) avg     | O(1) avg
// Lookup (contains)   | O(1) avg     | O(1) avg
// Remove              | O(1) avg     | O(1) avg (swap_remove)
//                     |              | O(n) avg (shift_remove)
// Index access        | N/A          | O(1)
// Iteration           | O(n)         | O(n)
// Get index of elem   | N/A          | O(1) avg
 
fn performance_comparison() {
    let n = 100_000;
    
    // Both have similar lookup performance
    let mut hash_set: HashSet<i32> = (0..n).collect();
    let mut index_set: IndexSet<i32> = (0..n).collect();
    
    // Lookup is O(1) for both
    assert!(hash_set.contains(&50_000));
    assert!(index_set.contains(&50_000));
    
    // IndexSet has additional capabilities
    let elem = index_set[50_000];  // O(1) index access
    let idx = index_set.get_index_of(&50_000);  // O(1) position lookup
}

Both sets have O(1) average complexity for core operations; IndexSet adds O(1) indexed access.

Memory Layout

use std::collections::HashSet;
use indexmap::IndexSet;
 
fn memory_comparison() {
    // HashSet stores elements in hash buckets
    // Memory: hash table with buckets + elements
    // Layout depends on hash function and load factor
    
    // IndexSet stores:
    // 1. Hash table for O(1) lookup
    // 2. Sequential array for order preservation
    // Memory: hash table + elements array + indices mapping
    
    // IndexSet uses more memory to maintain order
    let hash_set: HashSet<i32> = (0..1000).collect();
    let index_set: IndexSet<i32> = (0..1000).collect();
    
    // IndexSet has higher memory overhead
    // But provides both hash lookup AND ordered access
}

IndexSet has higher memory overhead to maintain the ordering data structures.

When HashSet Is Sufficient

use std::collections::HashSet;
 
fn hashset_appropriate() {
    // When you only need uniqueness
    let mut seen: HashSet<String> = HashSet::new();
    for word in ["apple", "banana", "apple", "cherry"] {
        if seen.insert(word.to_string()) {
            println!("New word: {}", word);
        }
    }
    
    // When order doesn't matter
    let set1: HashSet<i32> = [1, 2, 3].iter().cloned().collect();
    let set2: HashSet<i32> = [3, 2, 1].iter().cloned().collect();
    assert_eq!(set1, set2);  // Equal regardless of insertion order
    
    // When memory matters
    // HashSet has lower overhead
    
    // When maximum performance is critical
    // HashSet may have slightly better cache behavior
}

Use HashSet when you only need uniqueness checking and set operations.

When to Choose IndexSet

use indexmap::IndexSet;
 
fn indexset_appropriate() {
    // When you need deterministic iteration order
    let mut ordered: IndexSet<String> = IndexSet::new();
    ordered.insert("first".to_string());
    ordered.insert("second".to_string());
    ordered.insert("third".to_string());
    
    // Order is guaranteed for serialization, display, etc.
    let output: Vec<_> = ordered.iter().collect();
    // output is always ["first", "second", "third"]
    
    // When you need index-based access
    let item = ordered[1];  // "second"
    
    // When order affects equality
    let mut a: IndexSet<i32> = IndexSet::new();
    a.insert(1);
    a.insert(2);
    
    let mut b: IndexSet<i32> = IndexSet::new();
    b.insert(2);
    b.insert(1);
    
    // Different insertion order = different sets (unlike HashSet)
    // Though as sets, they contain the same elements
    
    // When implementing ordered unique lists
    // Like a playlist with no duplicates
}

Choose IndexSet for predictable order, index access, or when insertion sequence matters.

Set Operations

use std::collections::HashSet;
use indexmap::IndexSet;
 
fn set_operations() {
    // Both support standard set operations
    
    // HashSet
    let mut a: HashSet<i32> = [1, 2, 3].iter().cloned().collect();
    let b: HashSet<i32> = [2, 3, 4].iter().cloned().collect();
    
    a.union(&b);       // {1, 2, 3, 4} - order not guaranteed
    a.intersection(&b); // {2, 3}
    a.difference(&b);   // {1}
    a.symmetric_difference(&b); // {1, 4}
    
    // IndexSet - preserves order from left operand
    let mut x: IndexSet<i32> = [1, 2, 3].iter().cloned().collect();
    let y: IndexSet<i32> = [2, 3, 4].iter().cloned().collect();
    
    // Union preserves order: 1, 2, 3, 4
    let union: IndexSet<i32> = x.union(&y).copied().collect();
    
    // Intersection preserves order from first set: 2, 3
    let inter: IndexSet<i32> = x.intersection(&y).copied().collect();
}

IndexSet set operations preserve insertion order from the left operand.

Serialization and Determinism

use indexmap::IndexSet;
use serde::{Serialize, Deserialize};
 
#[derive(Serialize, Deserialize)]
struct Config {
    // Order matters for display/serialization
    allowed_users: IndexSet<String>,
}
 
fn serialization() {
    let mut config = Config {
        allowed_users: IndexSet::new(),
    };
    
    config.allowed_users.insert("alice".to_string());
    config.allowed_users.insert("bob".to_string());
    config.allowed_users.insert("charlie".to_string());
    
    // JSON will have users in insertion order
    let json = serde_json::to_string(&config).unwrap();
    // {"allowed_users":["alice","bob","charlie"]}
    
    // With HashSet, order would be unpredictable
    // This matters for:
    // - Configuration files (human readability)
    // - API responses (stable output for testing)
    // - Reproducible builds
}

IndexSet produces deterministic serialized output.

Ordered Command Processing

use indexmap::IndexSet;
 
fn command_processing() {
    // Process commands in order, skip duplicates
    let commands = vec!["init", "load", "process", "load", "save", "init"];
    
    let mut seen = IndexSet::new();
    for cmd in commands {
        if seen.insert(cmd) {
            println!("Executing: {}", cmd);
        } else {
            println!("Skipping duplicate: {}", cmd);
        }
    }
    
    // Output:
    // Executing: init
    // Executing: load
    // Executing: process
    // Skipping duplicate: load
    // Executing: save
    // Skipping duplicate: init
    
    // Order preserved, duplicates removed
    let unique_commands: Vec<_> = seen.iter().collect();
    // ["init", "load", "process", "save"]
}

IndexSet excels at deduplication while preserving order.

Comparison Summary

Feature	HashSet	IndexSet
Insertion order	Not preserved	Preserved
Index access	No	Yes, O(1)
Position lookup	No	Yes, O(1)
Memory overhead	Lower	Higher
Iteration order	Unspecified	Insertion order
Deterministic serialization	No	Yes
swap_remove	N/A	O(1), changes order
shift_remove	N/A	O(n), preserves order
Set operations	Order varies	Left operand order

Synthesis

IndexSet and HashSet serve different needs despite both providing uniqueness:

Choose HashSet when:

Only uniqueness checking is needed
Iteration order doesn't matter
Memory efficiency is important
Maximum performance is critical
Set equality should be order-independent

Choose IndexSet when:

Predictable iteration order is required
Index-based access to elements is needed
You need to know element positions
Deterministic serialization matters
Implementing ordered unique collections
Order affects application semantics

Key insight: IndexSet is a hybrid data structure that combines hash-based lookup with ordered storage. It's not just "a HashSet with ordering"—it provides capabilities that neither HashSet nor Vec alone can offer: O(1) lookup by value AND O(1) access by position. The trade-off is additional memory overhead to maintain both the hash table and the ordered index simultaneously. Use IndexSet when you need both uniqueness and order; stick with HashSet when uniqueness alone suffices.

How does indexmap::IndexSet differ from std::collections::HashSet and when would you choose one?