Crate kovan_map 

Two concurrent hash maps built on kovan’s memory reclamation.

• HashMap: separate chaining. HashMap::new starts with 524,288 buckets (about 4 MiB, so a large map rarely resizes and a lookup is often one pointer); HashMap::with_capacity starts with as many as asked. It grows when its load passes 3/4 and shrinks below 1/4, never under its initial capacity.
• HopscotchMap: open addressing in hopscotch neighborhoods. It starts at 64 slots and grows and shrinks with its contents.

Reads never wait: a lookup reads the current table under a kovan guard while writers and a resize run. Writers (inserts, removals, the conditional writes, clear) take no lock and race each other by compare-and-swap; a writer that meets a resize in flight waits for it to finish, and a hopscotch writer waits for the thread that holds its key’s neighborhood. Hashing is FoldHash (foldhash::fast::FixedState) unless a hasher is given.

Keys and values

Keys are Hash + Eq + Clone and values Clone (a read hands out a clone), both Send + 'static: a replaced or removed entry is freed by kovan once no reader can reach it, on whichever thread frees it, so its destructor may run on another thread.

// `Rc` is not `Send`: a map of them does not compile.
let map = kovan_map::HashMap::with_capacity(8);
map.insert(1, std::rc::Rc::new(1));

Example

use kovan_map::HashMap;
use std::sync::Arc;
use std::thread;

// Create a shared hash map
let map = Arc::new(HashMap::new());

// Spawn multiple threads for concurrent inserts
let mut handles = vec![];
for thread_id in 0..4 {
    let map = Arc::clone(&map);
    let handle = thread::spawn(move || {
        for i in 0..1000 {
            let key = thread_id * 1000 + i;
            map.insert(key, key * 2);
        }
    });
    handles.push(handle);
}

// Wait for all threads to complete
for handle in handles {
    handle.join().unwrap();
}

// Read values from any thread
assert_eq!(map.get(&0), Some(0));
assert_eq!(map.get(&1000), Some(2000));

// Remove values
assert_eq!(map.remove(&0), Some(0));
assert_eq!(map.remove(&0), None);

Safety

The implementation uses unsafe code internally for performance but provides a safe API. Memory safety is guaranteed through the Kovan memory reclamation system, which ensures nodes are only deallocated when no threads are accessing them.

Structs

HashMap

High-Performance Lock-Free Map with automatic grow/shrink.

HopscotchIntoIter

Owned iterator yielding (K, V) by value - moves out of the entries, no clone. Each drained slot is nulled so the table destructor stays a no-op.

HopscotchIter

Iterator over HopscotchMap entries (HopscotchMap::iter).

HopscotchKeys

Iterator over HopscotchMap keys (clones K).

HopscotchMap

A concurrent, lock-free hash map based on Hopscotch Hashing.

HopscotchValues

Iterator over HopscotchMap values (clones V).

IntoIter

Owned iterator yielding (K, V) by value - moves out of the nodes, no clone. Consuming the map gives exclusive access, so no guard protection of the yielded values is needed. A deleted node still in a chain (never unlinked, so never retired) is freed here with its key and value.

Iter

Iterator over HashMap entries (HashMap::iter).

Keys

Iterator over HashMap keys.

Values

Iterator over HashMap values (clones V).