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 MaybeSend and '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. Wherever threads can share memory that means Send; on wasm32 without the atomics feature, which has one thread, it asks nothing.

// `Rc` is not `Send`: where threads share memory, 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).

Traits

MaybeSend

Send on every target where threads can share memory, which is every target but wasm32 without the atomics feature. A replaced or removed entry is freed on whichever thread frees its batch, so there its key and value must be Send.