# 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`:

```toml
[dependencies]
hash-link = "0.1"
```

## Quick Start

### Basic Usage

```rust
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

```rust
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:

```rust
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:

```rust
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

```rust
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:

```rust
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)
