HashList

A container combining array insertion order with hash table fast lookup. This data structure combines:

1. Array: Maintains insertion order, supports sequential access
2. 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();

    // Insert elements
    let idx1 = list.push("Alice".to_string());
    let idx2 = list.push("Bob".to_string());
    let idx3 = list.push("Charlie".to_string());

    // Access using get_index
    assert_eq!(list.get_index(idx1), Some(&"Alice".to_string()));
    assert_eq!(list.get_index(idx2), Some(&"Bob".to_string()));

    // Find elements
    assert_eq!(list.index_of(&"Alice".to_string()), Some(idx1));
    assert!(list.contains(&"Bob".to_string()));

    // Iterate in insertion order
    println!("In insertion order:");
    for value in list.iter() {
        println!("  {}", value.1);
    }
    // Output:
    //   Alice
    //   Bob
    //   Charlie

    // Remove elements
    list.remove(&"Bob".to_string());

    // Use index_of to find elements
    assert_eq!(list.index_of(&"Alice".to_string()), Some(idx1));

    // Use pop method
    if let Some(value) = list.pop() {
        println!("Popped: {}", value);
    }

    // Clear all elements
    list.clear();
}

Create from Vec

use hash_link::HashList;

fn main() {
    let vec = vec!["apple", "banana", "cherry"];
    let list = HashList::from_vec(vec);

    // Verify element order
    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 {
    /// Returns the hash value of the element
    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()); // Same hash value

    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));
    }

    // Should contain two "hello" elements
    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());

    // Use ElementGuard to modify element
    {
        let mut guard = list.get_index_mut(idx).unwrap();
        println!("Hash before modification: {}", guard.original_hash());
        println!("Value before modification: {}", *guard);

        // Modify element value
        *guard = "modified".to_string();

        println!("Value after modification: {}", *guard);
        println!("Hash after modification: {}", guard.current_hash());
        println!("Hash changed: {}", guard.hash_changed());

        // ElementGuard automatically updates hash index on drop
    }

    // Verify lookup functionality after modification
    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)