Loading pageā¦
Rust walkthroughs
Loading pageā¦
indexmap::IndexSet differ from std::collections::HashSet in terms of iteration guarantees?IndexSet preserves insertion order, guaranteeing that iteration yields elements in the same sequence they were added, while HashSet provides no ordering guaranteesāiteration order is effectively random and can change between runs or versions. This difference stems from their internal implementations: IndexSet maintains a contiguous index alongside its hash table, while HashSet uses a hash table where iteration follows internal bucket layout. IndexSet also supports index-based access (set[index]), which HashSet cannot provide. The trade-off is slightly higher memory usage and different performance characteristics, but for many applications the predictable iteration order and index access are worth the cost.
use std::collections::HashSet;
fn main() {
let mut set = HashSet::new();
set.insert("apple");
set.insert("banana");
set.insert("cherry");
// Iteration order is unspecified
for item in &set {
println!("{}", item);
}
// Output order may vary: "cherry", "apple", "banana"
// Or any other permutation
}HashSet iteration order is unspecified and can change.
use indexmap::IndexSet;
fn main() {
let mut set = IndexSet::new();
set.insert("apple");
set.insert("banana");
set.insert("cherry");
// Iteration order is guaranteed to match insertion order
for item in &set {
println!("{}", item);
}
// Output is always: "apple", "banana", "cherry"
}IndexSet preserves insertion order in iteration.
use indexmap::IndexSet;
fn main() {
let mut set = IndexSet::new();
set.insert("first");
set.insert("second");
set.insert("third");
// Access by index - HashSet cannot do this
println!("First: {}", set[0]); // "first"
println!("Second: {}", set[1]); // "second"
println!("Third: {}", set[2]); // "third"
// Get index of an element
let idx = set.get_index_of("second");
println!("Index of 'second': {:?}", idx); // Some(1)
}IndexSet provides index-based access like a Vec.
use std::collections::HashSet;
fn main() {
let mut set = HashSet::new();
set.insert("a");
set.insert("b");
set.insert("c");
// Cannot index into HashSet
// let item = set[0]; // Compilation error
// No way to get "the first element"
// HashSet doesn't track insertion order
}HashSet has no concept of element positions.
use indexmap::IndexSet;
fn main() {
let mut set = IndexSet::new();
// Insert in specific order
set.insert(1);
set.insert(2);
set.insert(3);
set.insert(4);
set.insert(5);
// Remove and re-insert
set.remove(&3);
set.insert(3); // Goes to the end
// Order is now: 1, 2, 4, 5, 3
for item in &set {
println!("{}", item);
}
// Re-insert moves to end, preserving relative order of others
}Removal preserves remaining order; re-insertion appends to end.
use std::collections::HashSet;
fn main() {
// HashSet order depends on:
// 1. Hash function implementation
// 2. Hash randomization (security feature)
// 3. Internal bucket layout
// 4. Rust version (may change between versions)
let set1: HashSet<_> = [1, 2, 3, 4, 5].into_iter().collect();
let set2: HashSet<_> = [1, 2, 3, 4, 5].into_iter().collect();
// Order may differ between sets or runs
// Cannot rely on any ordering guarantee
}HashSet provides no stability guarantees for iteration order.
use indexmap::IndexSet;
use serde_json;
fn main() {
let mut set = IndexSet::new();
set.insert("zebra");
set.insert("apple");
set.insert("mango");
// JSON array preserves insertion order
let json = serde_json::to_string(&set).unwrap();
println!("{}", json);
// ["zebra","apple","mango"]
// Order is deterministic and matches insertion
}IndexSet enables deterministic serialization output.
use std::collections::HashSet;
fn main() {
// HashSet uses randomized hash seeds for security
// This means iteration order differs between program invocations
let set: HashSet<_> = [1, 2, 3, 4, 5].into_iter().collect();
// Run 1 might print: 3, 1, 5, 2, 4
// Run 2 might print: 5, 2, 3, 1, 4
// Order is intentionally unpredictable
// This is a security feature to prevent hashDoS attacks
}HashSet intentionally randomizes iteration order.
use std::collections::HashSet;
use indexmap::IndexSet;
fn main() {
// HashSet: O(1) average for insert, contains, remove
// IndexSet: O(1) average for insert, contains, remove
// Both have similar asymptotic complexity
// Differences:
// - IndexSet has slightly higher constant factors
// - IndexSet uses more memory (index array overhead)
// - IndexSet has worse cache locality for iteration
let mut hash_set = HashSet::new();
let mut index_set = IndexSet::new();
// Insert performance is similar
for i in 0..100_000 {
hash_set.insert(i);
index_set.insert(i);
}
// Contains is similar
assert!(hash_set.contains(&50_000));
assert!(index_set.contains(&50_000));
}Both offer similar asymptotic complexity with different constants.
use std::mem::size_of;
use std::collections::HashSet;
use indexmap::IndexSet;
fn main() {
// IndexSet has additional memory overhead for:
// 1. Index array mapping positions to hash table entries
// 2. Reverse mapping from hash table to indices
// Rough overhead: ~16 bytes per element plus hash table overhead
let hash_set: HashSet<i32> = HashSet::new();
let index_set: IndexSet<i32> = IndexSet::new();
// For large sets, IndexSet uses ~25-50% more memory
// Exact overhead depends on load factor and element size
}IndexSet uses more memory to maintain ordering information.
use indexmap::IndexSet;
fn main() {
let mut set = IndexSet::new();
// Maintain insertion order for user selections
set.insert("Option A");
set.insert("Option B");
set.insert("Option C");
// User deselects and reselects - moves to end
set.remove(&"Option B");
set.insert("Option B");
// Now: Option A, Option C, Option B
// Useful for "recently used" patterns
for (idx, item) in set.iter().enumerate() {
println!("{}. {}", idx + 1, item);
}
}IndexSet naturally models ordered selections and recently-used patterns.
use indexmap::IndexSet;
fn process_items(items: &[&str]) -> Vec<&str> {
let mut seen = IndexSet::new();
for item in items {
seen.insert(item); // Deduplicate while preserving order
}
seen.into_iter().collect()
}
fn main() {
let items = ["a", "b", "a", "c", "b", "d"];
let result = process_items(&items);
// Always: ["a", "b", "c", "d"]
// First occurrence preserved, duplicates removed
println!("{:?}", result);
}IndexSet deduplicates while preserving first-seen order.
use std::collections::HashSet;
fn main() {
// When order doesn't matter, HashSet is appropriate
let mut permissions: HashSet<&str> = HashSet::new();
permissions.insert("read");
permissions.insert("write");
permissions.insert("execute");
// Order is irrelevant for permission checking
if permissions.contains("read") {
println!("Has read permission");
}
// HashSet is semantically correct: set membership, not sequence
}Use HashSet when order has no meaning.
use indexmap::IndexSet;
fn main() {
let mut set = IndexSet::new();
set.insert("red");
set.insert("green");
set.insert("blue");
// Iterate with indices
for (idx, item) in set.iter().enumerate() {
println!("Index {}: {}", idx, item);
}
// Get mutable reference by index
if let Some(item) = set.get_mut(1) {
*item = "emerald";
}
// Indices are stable for the lifetime of the set
// (until removal, which shifts subsequent indices)
}IndexSet provides stable indices that can be used as handles.
use indexmap::IndexSet;
fn main() {
let mut set = IndexSet::new();
set.insert("a");
set.insert("b");
set.insert("c");
set.insert("d");
// Remove "b" at index 1
set.shift_remove("b");
// Indices shift: "a" stays at 0, "c" moves to 1, "d" moves to 2
assert_eq!(set[0], "a");
assert_eq!(set[1], "c");
assert_eq!(set[2], "d");
// shift_remove preserves order but changes indices
// swap_remove would not shift (different behavior)
}shift_remove maintains order but shifts indices; swap_remove is faster.
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
set.swap_remove("b");
// Order might be: "a", "d", "c"
// "b" swapped with last element, then removed
let mut set2 = IndexSet::new();
set2.insert("a");
set2.insert("b");
set2.insert("c");
set2.insert("d");
// shift_remove: O(n), preserves order
set2.shift_remove("b");
// Order is: "a", "c", "d"
// Indices shift to fill gap
}IndexSet offers two removal strategies with different trade-offs.
use std::collections::HashSet;
use indexmap::IndexSet;
fn main() {
// HashSet to IndexSet (order is arbitrary)
let hash_set: HashSet<_> = [1, 2, 3].into_iter().collect();
let index_set: IndexSet<_> = hash_set.into_iter().collect();
// Order after conversion is unspecified
// IndexSet to HashSet (order is lost)
let index_set: IndexSet<_> = [1, 2, 3].into_iter().collect();
let hash_set: HashSet<_> = index_set.into_iter().collect();
// HashSet has no ordering
// For order preservation, use Vec or IndexSet throughout
}Converting between types affects ordering semantics.
use indexmap::IndexSet;
fn main() {
// Tests that verify output order need deterministic iteration
fn process(input: &[&str]) -> Vec<&str> {
let mut set = IndexSet::new();
for item in input {
set.insert(item);
}
set.into_iter().collect()
}
// Test is deterministic
let result = process(&["c", "a", "b"]);
assert_eq!(result, vec!["c", "a", "b"]);
// With HashSet, test might be flaky due to random iteration order
}IndexSet enables deterministic tests for order-dependent behavior.
| Feature | HashSet | IndexSet |
|---------|-----------|------------|
| Iteration order | Unspecified | Insertion order |
| Index access | No | Yes (set[0]) |
| Index lookup | No | Yes (get_index_of) |
| Memory overhead | Lower | Higher |
| Insert speed | O(1) | O(1) |
| Lookup speed | O(1) | O(1) |
| Order-preserving remove | N/A | O(n) shift_remove |
| Fast remove | O(1) | O(1) swap_remove |
The fundamental difference between HashSet and IndexSet is iteration order semantics:
HashSet provides an unordered set abstraction. Iteration order is a consequence of internal hash table layout and randomized hashing, making it intentionally unpredictable. Use HashSet when order has no semantic meaningāsets of IDs, permissions, flags, or any collection where membership matters but sequence doesn't.
IndexSet maintains insertion order as part of its contract. This enables index-based access, deterministic iteration, and stable output for serialization. The cost is additional memory for the index mapping and slightly slower operations due to index maintenance. Use IndexSet when order mattersārecently-used lists, ordered deduplication, LRU caches, or any scenario where the sequence of elements has semantic meaning.
Key insight: IndexSet bridges the gap between HashSet (unordered, O(1) operations) and Vec (ordered, O(n) contains). It provides the set semantics of HashSet with the ordering guarantees of Vec. Choose based on whether your application needs ordering guaranteesāif it does, IndexSet is the right tool; if not, HashSet is simpler and more memory-efficient. The index access feature is often valuable: it lets you use indices as stable handles to set elements, enabling patterns like referencing elements by position in a configuration or protocol.