robinxx_map 0.1.0

# robinxx_map


[![CI](https://github.com/da578/robinxx_map/actions/workflows/ci.yml/badge.svg)](https://github.com/da578/robinxx_map/actions/workflows/ci.yml)
[![Crates.io](https://img.shields.io/crates/v/robinxx_map.svg)](https://crates.io/crates/robinxx_map)
[![docs.rs](https://img.shields.io/docsrs/robinxx_map)](https://docs.rs/robinxx_map)
[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](LICENSE)

High-performance, thread-safe open-addressing hash map utilizing **Robin Hood displacement** with **Distance from Home (DfH)** tracking and **xxHash3** for key hashing. Designed for `#![no_std]` environments with explicit `alloc` support.

## Features

- **`#![no_std]` + `alloc` compatible** \
Runs in bare-metal, WASM, and embedded environments.
- **Thread-Safe by Default** \
Internal `SpinMutex` guarantees `Send + Sync` without OS primitives.
- **Robin Hood Probing** \
Bounded worst-case probe chains via DfH displacement.
- **SoA Memory Layout** \
Parallel 64B-aligned arrays for cache-line efficiency & auto-vectorization.
- **Zero External Dependencies** \
Core relies only on `xxhash-rust` for stable, deterministic hashing.
- **Strict Safety Contract** \
100% safe public API. Internal `unsafe` blocks guarded by documented invariants.

## Installation

Add to `Cargo.toml`:
```toml
[dependencies]
robinxx_map = "0.1.0"
```

## Quick Start

```rust
use robinxx_map::RobinHoodMap;

// Thread-safe, defaults to Global allocator in std environments
let map = RobinHoodMap::new();
map.insert("rust", 2024);
map.insert("cpp", 2011);

assert_eq!(map.get(&"rust"), Some(&2024));
assert_eq!(map.len(), 2);
```

## Architecture

```
[User/Client]
     │
     ▼
┌─────────────────────┐
│  RobinHoodMap<K,V>  │ ◄── Safe Public API (SpinMutex wrapped)
└─────────┬───────────┘
          │ MutexGuard
          ▼
┌─────────────────────┐
│    RawTable<K,V>    │ ◄── SoA Layout: [Meta] [Keys] [Values] @ 64B align
└─────────────────────┘
```
- **Hashing**: `xxh3_64` (non-cryptographic, extremely fast)
- **Probing**: Linear with DfH tracking & Robin Hood swap
- **Deletion**: Backward shift (tombstone-free)
- **Resize**: Triggered at 80% load factor, rehashes via Robin Hood insertion

## Performance (v0.1.0 Baseline)

| Operation | `robinxx_map` | `std::HashMap` | `hashbrown` |
|-----------|--------------|----------------|-------------|
| `insert`  | ~8.4 ms      | ~8.1 ms        | ~4.6 ms     |
| `find`    | **~3.6 ms**  | ~4.8 ms        | ~1.3 ms     |
| `erase`   | **~3.1 ms**  | ~7.2 ms        | ~2.7 ms     |
| `resize`  | ~19.6 ms     | ~18.2 ms       | ~10.6 ms    |

*Tested on 100k `u64` entries, x86_64 Linux, Rust 1.95.0. Competitive with industry standards; optimized for lookup & deletion workloads.*

## Safety & MSRV

- **MSRV** \
`1.95.0` | Edition: `2024`
- **Public API** \
100% safe. Panics only on OOM or debug invariant violations.
- **Concurrency** \
`&self` methods are thread-safe. `&mut self` requires exclusive access.
- **Memory** \
Drop-safe, zero-leak, alignment-guaranteed. `unsafe` confined to allocation & pointer math.

## License

Distributed under the MIT License. See [LICENSE](LICENSE) for details.

## Coding Standards

- **Safety** \
`unsafe` blocks must include `// SAFETY:` comments explaining invariants.
- **Documentation** \
All `pub` items follow `Summary → Description → Examples → Panics → Errors → Safety → See Also`.
- **Testing** \
Unit tests for logic, `proptest` for invariants, `criterion` for regression.

## Out of Scope

- Cryptographic hashing, async I/O, Serde, or OS-specific locks (`parking_lot`).
- Dynamic SIMD intrinsics (rely on stable auto-vectorization).

We appreciate clean, well-tested, and documented contributions!