HashList
A container combining array insertion order with hash table fast lookup. This data structure combines:
- Array: Maintains insertion order, supports sequential access
- Hash Table: Provides fast lookup, insertion, and deletion operations
Features
- Ordered: Maintains element insertion order
- Fast Lookup: O(1) average lookup time based on hash table
- Lazy Deletion: Supports efficient deletion operations
- Smart Resizing: Automatic expansion based on load factor
- Memory Compaction: Optional automatic compaction to reclaim space
Installation
Add dependency in Cargo.toml:
[dependencies]
hash-link = "0.1"
Quick Start
Basic Usage
use hash_link::HashList;
fn main() {
let mut list = HashList::new();
let idx1 = list.push("Alice".to_string());
let idx2 = list.push("Bob".to_string());
let idx3 = list.push("Charlie".to_string());
assert_eq!(list.get_index(idx1), Some(&"Alice".to_string()));
assert_eq!(list.get_index(idx2), Some(&"Bob".to_string()));
assert_eq!(list.index_of(&"Alice".to_string()), Some(idx1));
assert!(list.contains(&"Bob".to_string()));
println!("In insertion order:");
for value in list.iter() {
println!(" {}", value.1);
}
list.remove(&"Bob".to_string());
assert_eq!(list.index_of(&"Alice".to_string()), Some(idx1));
if let Some(value) = list.pop() {
println!("Popped: {}", value);
}
list.clear();
}
Create from Vec
use hash_link::HashList;
fn main() {
let vec = vec!["apple", "banana", "cherry"];
let list = HashList::from_vec(vec);
let collected: Vec<&str> = list.iter().map(|(_, s)| *s).collect();
assert_eq!(collected, vec!["apple", "banana", "cherry"]);
}
Hashable Trait
Custom hash element trait for efficient hash computation:
pub trait Hashable: Eq {
fn get_hash(&self) -> u32;
}
Custom Type Implementation
For custom types, implement the Hashable trait:
use hash_link::{HashList, Hashable};
#[derive(Debug, PartialEq, Eq)]
struct MyData {
value: i32,
name: String,
}
impl Hashable for MyData {
fn get_hash(&self) -> u32 {
let name_hash = self.name.get_hash();
(self.value as u32).wrapping_add(name_hash)
}
}
Hashable Trait Implementation
The library provides optimized implementations for common primitive types:
- String and &str: Uses FNV-1a hash algorithm
- usize, u32: Returns itself directly as hash value
- i32: Converts to u32
- [u8]: Uses FNV-1a hash algorithm for byte slices
All types implementing Hashable must also implement PartialEq for equality comparison.
Find by Hash Value
use hash_link::{HashList, Hashable};
fn main() {
let mut list = HashList::new();
list.push("hello".to_string());
list.push("world".to_string());
list.push("hello".to_string());
let hello_hash = "hello".get_hash();
let mut iter = list.find_hash(hello_hash);
let mut found = Vec::new();
while let Some((index, value)) = iter.next() {
found.push((index, value.clone()));
assert_eq!(list.get(index), Some(value));
}
assert_eq!(found.len(), 2);
}
Note: Indices returned by find_hash() are vector slot indices, not sorted indices of valid elements. These indices remain stable before compact() operations.
Safe Element Modification
Use ElementGuard to safely modify elements while maintaining hash index synchronization:
use hash_link::HashList;
fn main() {
let mut list = HashList::new();
let idx = list.push("hello".to_string());
{
let mut guard = list.get_index_mut(idx).unwrap();
println!("Hash before modification: {}", guard.original_hash());
println!("Value before modification: {}", *guard);
*guard = "modified".to_string();
println!("Value after modification: {}", *guard);
println!("Hash after modification: {}", guard.current_hash());
println!("Hash changed: {}", guard.hash_changed());
}
assert!(list.index_of(&"hello".to_string()).is_none());
assert_eq!(list.index_of(&"modified".to_string()), Some(idx));
}
Memory Management
Resizing Mechanism
HashList uses intelligent resizing based on load factor:
- Trigger: When valid element count + 1 reaches 75% of hash bucket count
- Formula:
(count() + 1) / hash_buckets.len() >= 0.75
- Hash Bucket Resizing: Each expansion is 2x the original
- Element Array Resizing: New capacity =
current valid element count * 2 (minimum 4)
Performance Characteristics
- Insertion: O(1) average, O(n) worst case (during resizing)
- Lookup: O(1) average, O(n) worst case (hash collisions)
- Deletion: O(1) average (lazy deletion)
- Iteration: O(n)
- Resizing: O(n) (requires re-inserting all elements)
- Compaction: O(n) (requires rebuilding data structure)