What are the trade-offs between `indexmap::IndexSet` and `std::collections::HashSet` for ordered unique collections?

IndexSet preserves insertion order while HashSet does not—this fundamental difference affects iteration behavior, lookup patterns, and memory layout. HashSet is optimized for fast membership testing with O(1) average lookup, using a hash table where element positions depend on hash values. IndexSet maintains a separate index structure that remembers insertion order, enabling predictable iteration and index-based access at the cost of additional memory overhead. The choice depends on whether you need ordered iteration, positional access, or maximum lookup performance.

HashSet: Unordered but Fast

use std::collections::HashSet;
 
fn main() {
    let mut set = HashSet::new();
    
    set.insert("first");
    set.insert("second");
    set.insert("third");
    
    // Iteration order is NOT guaranteed
    // May print in any order: "second", "first", "third"
    for item in &set {
        println!("{}", item);
    }
    
    // Fast membership testing - O(1) average
    assert!(set.contains("first"));
    assert!(!set.contains("fourth"));
    
    // No index-based access
    // Cannot do: set[0] or set.get_index(0)
}

HashSet prioritizes lookup speed over iteration order.

IndexSet: Ordered with Predictable Iteration

use indexmap::IndexSet;
 
fn main() {
    let mut set = IndexSet::new();
    
    set.insert("first");
    set.insert("second");
    set.insert("third");
    
    // Iteration order is GUARANTEED to match insertion order
    // Always prints: "first", "second", "third"
    for item in &set {
        println!("{}", item);
    }
    
    // Index-based access - O(1)
    assert_eq!(set.get_index(0), Some(&"first"));
    assert_eq!(set.get_index(1), Some(&"second"));
    
    // Still O(1) membership testing
    assert!(set.contains("first"));
}

IndexSet maintains insertion order and provides positional access.

Performance Characteristics

use std::collections::HashSet;
use indexmap::IndexSet;
 
fn main() {
    // HashSet memory layout:
    // - Single hash table
    // - Elements scattered based on hash
    // - Lower memory overhead
    
    // IndexSet memory layout:
    // - Hash table for lookups
    // - Separate Vec for ordering
    // - Higher memory overhead (~2x)
    
    // HashSet operations:
    // - insert: O(1) average
    // - contains: O(1) average
    // - remove: O(1) average
    // - iteration: O(n) but order undefined
    
    // IndexSet operations:
    // - insert: O(1) average
    // - contains: O(1) average
    // - remove: O(1) average (swap_remove) or O(n) (shift_remove)
    // - iteration: O(n) with guaranteed order
    // - get_index: O(1)
    // - get_index_of: O(1)
    
    println!("Both provide O(1) membership testing");
    println!("IndexSet adds O(1) index access");
    println!("IndexSet uses more memory for ordering");
}

Both have O(1) lookups; IndexSet adds ordering overhead.

Index-Based Operations

use indexmap::IndexSet;
 
fn main() {
    let mut set = IndexSet::new();
    
    set.insert("apple");
    set.insert("banana");
    set.insert("cherry");
    
    // Get by index
    let first = set.get_index(0);
    assert_eq!(first, Some(&"apple"));
    
    // Get index of value
    let idx = set.get_index_of(&"banana");
    assert_eq!(idx, Some(1));
    
    // Remove by index (swap with last, then pop)
    let removed = set.swap_remove_index(0);
    assert_eq!(removed, Some("apple".to_string()));
    
    // After swap_remove, order changes:
    // "banana" might now be at index 0
    println!("After removal: {:?}", set.iter().collect::<Vec<_>>());
    
    // Insert at specific position
    let mut set2 = IndexSet::new();
    set2.insert("a");
    set2.insert("c");
    set2.insert_at(1, "b");  // Insert "b" at index 1
    
    // Now: ["a", "b", "c"]
    assert_eq!(set2.get_index(0), Some(&"a"));
    assert_eq!(set2.get_index(1), Some(&"b"));
    assert_eq!(set2.get_index(2), Some(&"c"));
}

IndexSet provides get_index, get_index_of, and insert_at for positional operations.

Removal Strategies

use indexmap::IndexSet;
 
fn main() {
    let mut set = IndexSet::new();
    set.insert("a");
    set.insert("b");
    set.insert("c");
    set.insert("d");
    
    // swap_remove: O(1), but changes order
    // Swaps element with last, then removes last
    set.swap_remove("b");
    // Order might now be: ["a", "d", "c"]
    
    let mut set2 = IndexSet::new();
    set2.insert("a");
    set2.insert("b");
    set2.insert("c");
    set2.insert("d");
    
    // shift_remove: O(n), preserves order
    // Shifts all subsequent elements
    set2.shift_remove("b");
    // Order preserved: ["a", "c", "d"]
    
    // HashSet remove: O(1), no order to preserve
    let mut hash_set = std::collections::HashSet::new();
    hash_set.insert("a");
    hash_set.insert("b");
    hash_set.remove("b");  // No order implications
}

IndexSet offers swap_remove (fast, changes order) or shift_remove (slower, preserves order).

Use Case: Ordered Display

use indexmap::IndexSet;
 
fn main() {
    // When user-facing display order matters
    let mut menu_items = IndexSet::new();
    
    // Items appear in insertion order
    menu_items.insert("File");
    menu_items.insert("Edit");
    menu_items.insert("View");
    menu_items.insert("Help");
    
    // Menu displays predictably
    println!("Menu:");
    for (i, item) in menu_items.iter().enumerate() {
        println!("  {}. {}", i + 1, item);
    }
    
    // Output:
    // Menu:
    //   1. File
    //   2. Edit
    //   3. View
    //   4. Help
    
    // HashSet would display in unpredictable order
}

Use IndexSet when display order matters.

Use Case: Ordered Command Processing

use indexmap::IndexSet;
 
fn main() {
    // Process commands in order they were added
    // But avoid duplicates
    let mut commands = IndexSet::new();
    
    commands.insert("init");
    commands.insert("load");
    commands.insert("validate");  // First occurrence
    commands.insert("validate");  // Ignored (duplicate)
    commands.insert("save");
    
    // Execute in order
    for cmd in &commands {
        println!("Executing: {}", cmd);
    }
    
    // Output:
    // Executing: init
    // Executing: load
    // Executing: validate
    // Executing: save
}

IndexSet ensures unique commands while preserving execution order.

Use Case: Fast Position Lookup

use indexmap::IndexSet;
 
fn main() {
    let mut users = IndexSet::new();
    
    users.insert("alice");
    users.insert("bob");
    users.insert("charlie");
    
    // Find position quickly - O(1)
    if let Some(pos) = users.get_index_of(&"bob") {
        println!("bob is at position {}", pos);
    }
    
    // This is useful when:
    // - Building sparse arrays
    // - Tracking order of appearance
    // - Implementing ranked leaderboards
    
    // In a leaderboard, you can quickly find someone's rank
    let leaderboard: IndexSet<&str> = ["player1", "player2", "player3"]
        .iter().copied().collect();
    
    let rank = leaderboard.get_index_of(&"player2").map(|i| i + 1);
    println!("player2 rank: {:?}", rank);  // Some(2)
}

get_index_of provides O(1) position lookup, useful for ranking systems.

Memory Comparison

use std::collections::HashSet;
use indexmap::IndexSet;
 
fn main() {
    // HashSet memory:
    // - Hash table with buckets
    // - Each element stored once
    // - Load factor affects memory
    
    // IndexSet memory:
    // - Hash table (similar to HashSet)
    // - Additional Vec<usize> for indices
    // - Roughly 1.5-2x memory of HashSet
    
    let elements: Vec<String> = (0..1000)
        .map(|i| format!("element_{}", i))
        .collect();
    
    let hash_set: HashSet<String> = elements.iter().cloned().collect();
    let index_set: IndexSet<String> = elements.iter().cloned().collect();
    
    // Approximate size comparison
    println!("HashSet size hint: {} bytes", std::mem::size_of_val(&hash_set));
    println!("IndexSet size hint: {} bytes", std::mem::size_of_val(&index_set));
    
    // For large sets, IndexSet has noticeable memory overhead
    // But provides:
    // - Ordered iteration
    // - Index access
    // - Position lookup
}

IndexSet uses more memory for its ordering guarantees.

Conversion Between Types

use std::collections::HashSet;
use indexmap::IndexSet;
 
fn main() {
    // HashSet to IndexSet
    let hash_set: HashSet<&str> = ["a", "b", "c"].iter().copied().collect();
    let index_set: IndexSet<&str> = hash_set.into_iter().collect();
    
    // Note: Order is still arbitrary (depends on hash)
    // IndexSet preserves insertion order, but hash_set had arbitrary order
    
    // IndexSet to HashSet
    let index_set: IndexSet<&str> = ["x", "y", "z"].iter().copied().collect();
    let hash_set: HashSet<&str> = index_set.into_iter().collect();
    
    // Order is lost when converting to HashSet
    
    // Maintaining order with ordered source:
    let ordered: IndexSet<&str> = vec!["first", "second", "third"]
        .into_iter().collect();
    
    // Order preserved from Vec:
    for (i, item) in ordered.iter().enumerate() {
        println!("{}: {}", i, item);
    }
}

Order is lost when converting to HashSet.

Serde Serialization Behavior

use indexmap::IndexSet;
use serde::{Serialize, Deserialize};
 
// IndexSet serializes as a sequence, preserving order
// HashSet serializes as a sequence, but order is undefined
 
fn main() {
    let mut set = IndexSet::new();
    set.insert("first");
    set.insert("second");
    set.insert("third");
    
    // Serializes to: ["first", "second", "third"]
    // Deserialization preserves order
    
    // This is useful for:
    // - JSON arrays where order matters
    // - Configuration files with ordered lists
    // - API responses with predictable serialization
}

IndexSet serialization preserves order, critical for deterministic JSON output.

Converting to Vec

use indexmap::IndexSet;
 
fn main() {
    let mut set = IndexSet::new();
    set.insert("a");
    set.insert("b");
    set.insert("c");
    
    // Convert to Vec preserving order
    let vec: Vec<&str> = set.into_iter().collect();
    assert_eq!(vec, vec!["a", "b", "c"]);
    
    // Or keep the IndexSet and iterate
    let mut set2 = IndexSet::new();
    set2.insert("x");
    set2.insert("y");
    set2.insert("z");
    
    let vec2: Vec<_> = set2.iter().collect();
    assert_eq!(vec2, vec![&"x", &"y", &"z"]);
}

IndexSet::into_iter() produces elements in insertion order.

When to Use Each

use std::collections::HashSet;
use indexmap::IndexSet;
 
fn main() {
    // Use HashSet when:
    // - Only need membership testing
    // - Don't care about iteration order
    // - Memory efficiency matters
    // - No need for positional access
    // - Removing elements frequently (no order preservation)
    
    let mut hash_set = HashSet::new();
    hash_set.insert("key1");
    hash_set.insert("key2");
    
    if hash_set.contains("key1") {
        println!("Found in hash_set");
    }
    
    // Use IndexSet when:
    // - Need ordered iteration
    // - Want to access elements by position
    // - Need to find position of elements
    // - Serialization order matters
    // - Implementing ordered unique lists
    
    let mut index_set = IndexSet::new();
    index_set.insert("key1");
    index_set.insert("key2");
    
    if let Some(pos) = index_set.get_index_of(&"key1") {
        println!("key1 is at position {}", pos);
    }
    
    // Deterministic iteration
    for item in &index_set {
        println!("{}", item);
    }
}

Choose HashSet for pure membership testing; IndexSet for order matters.

API Comparison

use std::collections::HashSet;
use indexmap::IndexSet;
 
fn main() {
    // Common operations (both have):
    // - insert(&T) -> bool
    // - contains(&T) -> bool
    // - remove(&T) -> bool
    // - len() -> usize
    // - is_empty() -> bool
    // - iter() -> Iterator
    // - clear()
    
    // IndexSet-only operations:
    // - get_index(usize) -> Option<&T>
    // - get_index_of(&T) -> Option<usize>
    // - get_index_mut(usize) -> Option<&mut T> (if T: Clone)
    // - swap_remove_index(usize) -> Option<T>
    // - shift_remove_index(usize) -> Option<T>
    // - insert_at(usize, T)
    // - move_index(usize, usize)
    // - swap_indices(usize, usize)
    
    // HashSet has no positional operations
    
    let mut index_set = IndexSet::new();
    index_set.insert("a");
    index_set.insert("b");
    index_set.insert("c");
    
    // Move "b" to end
    index_set.move_index(1, 2);
    // Now: ["a", "c", "b"]
    
    // Swap first and last
    index_set.swap_indices(0, 2);
    // Now: ["b", "c", "a"]
}

IndexSet adds many positional operations not available in HashSet.

Real-World Example: Ordered Configuration

use indexmap::IndexSet;
 
// Configuration where order matters
struct Config {
    search_paths: IndexSet<String>,
}
 
impl Config {
    fn new() -> Self {
        Config {
            search_paths: IndexSet::new(),
        }
    }
    
    fn add_path(&mut self, path: &str) {
        // Duplicates are ignored, order preserved
        self.search_paths.insert(path.to_string());
    }
    
    fn search(&self, filename: &str) -> Option<String> {
        // Search in order - first match wins
        for path in &self.search_paths {
            let full_path = format!("{}/{}", path, filename);
            if std::path::Path::new(&full_path).exists() {
                return Some(full_path);
            }
        }
        None
    }
    
    fn get_priority(&self, path: &str) -> Option<usize> {
        // Lower index = higher priority
        self.search_paths.get_index_of(path)
    }
}
 
fn main() {
    let mut config = Config::new();
    config.add_path("/usr/local");
    config.add_path("/usr");
    config.add_path("/home/user");
    config.add_path("/usr/local");  // Ignored, already exists
    
    println!("Search order:");
    for (i, path) in config.search_paths.iter().enumerate() {
        println!("  {}: {}", i, path);
    }
    
    // Priority: lower index = searched first
    if let Some(pos) = config.get_priority("/usr") {
        println!("Priority of /usr: {}", pos);
    }
}

IndexSet ensures search order is deterministic and configurable.

Synthesis

Quick reference:

use std::collections::HashSet;
use indexmap::IndexSet;
 
fn main() {
    // HashSet: Unordered, minimal memory
    let mut hs: HashSet<&str> = HashSet::new();
    hs.insert("a");
    hs.insert("b");
    // Order undefined
    
    // IndexSet: Ordered, more memory
    let mut is: IndexSet<&str> = IndexSet::new();
    is.insert("a");
    is.insert("b");
    // Order preserved: ["a", "b"]
    
    // Common: O(1) membership testing
    assert!(hs.contains("a"));
    assert!(is.contains("a"));
    
    // IndexSet-only: O(1) index access
    assert_eq!(is.get_index(0), Some(&"a"));
    assert_eq!(is.get_index_of(&"b"), Some(1));
    
    // Memory: IndexSet uses ~2x memory of HashSet
    
    // Choose HashSet when:
    // - Only membership testing needed
    // - Memory constrained
    // - Order doesn't matter
    
    // Choose IndexSet when:
    // - Need ordered iteration
    // - Need positional access
    // - Need to find element positions
    // - Serialization order matters
    // - Implementing ordered unique lists
}

Key insight: The trade-off is clear—HashSet for maximum performance and minimal memory when order doesn't matter; IndexSet when you need ordered iteration, positional access, or deterministic serialization. Both provide O(1) membership testing, but IndexSet maintains a separate index structure that enables get_index(), get_index_of(), and guaranteed iteration order. For removal, swap_remove is O(1) but changes order, while shift_remove preserves order at O(n) cost. Use IndexSet for configuration paths, command queues, ordered menus, or any scenario where both uniqueness and order matter. Use HashSet for pure set operations like deduplication without ordering concerns.

What are the trade-offs between indexmap::IndexSet and std::collections::HashSet for ordered unique collections?