🎬 Fearless Concurrency Threads, Arc>, channels — safe parallelism enforced by the compiler.

📝 Text version (for readers / accessibility)

• std::thread::spawn creates OS threads — closures must be Send + 'static

• Arc> provides shared mutable state across threads safely

• Channels (mpsc) enable message passing — multiple producers, single consumer

• Send and Sync marker traits enforce thread safety at compile time

• Data races are impossible — the type system prevents them before your code runs

466: Concurrent HashMap

Difficulty: 3 Level: Intermediate A sharded map lets multiple threads read and write simultaneously without global locking.

The Problem This Solves

A single `Mutex<HashMap>` serialises every access — inserts, lookups, and deletions all queue behind the same lock. Under high concurrency this becomes a bottleneck: 16 threads fighting over one lock achieve barely more throughput than 1. The standard fix is sharding: split the map into N independent `RwLock<HashMap>` buckets. Each key hashes to exactly one shard. Operations on different shards proceed in parallel, with no contention. Operations on the same shard still serialize, but the probability of collision drops by N. This is the pattern behind DashMap, Java's `ConcurrentHashMap`, and most production-grade concurrent maps.

The Intuition

Imagine a library with 16 shelves. Instead of one librarian who handles all requests, 16 librarians each manage their shelf. You can all check out books simultaneously as long as you're at different shelves. Only if two people need the same shelf do they have to take turns.

How It Works in Rust

1. Choose shard count — a power of two (16–64) is typical:

const SHARDS: usize = 16;
let shards: Vec<RwLock<HashMap<K, V>>> = (0..SHARDS).map(|_| RwLock::new(HashMap::new())).collect();

2. Hash to shard:

fn shard_index<K: Hash>(key: &K) -> usize {
    let mut h = DefaultHasher::new();
    key.hash(&mut h);
    h.finish() as usize % SHARDS
}

3. Read with shared lock:

let idx = shard_index(&key);
let guard = shards[idx].read().unwrap();
guard.get(&key).cloned()

4. Write with exclusive lock:

let idx = shard_index(&key);
let mut guard = shards[idx].write().unwrap();
guard.insert(key, value);

5. Wrap in `Arc` to share across threads: `Arc<ShardedMap<K, V>>`.

What This Unlocks

Parallel reads at no cost — `RwLock` lets N readers hold locks simultaneously; contention only occurs for writers.
Near-linear write scaling — with 16 shards, expected lock contention is 1/16th of an unsharded map.
Foundation for DashMap — the popular `dashmap` crate is a battle-tested, production-ready version of exactly this pattern.

Key Differences

Concept	OCaml	Rust
Concurrent map	`Hashtbl` + `Mutex` per thread	Sharded `RwLock<HashMap>`
Read concurrency	Blocked by any lock	Multiple readers via `RwLock`
Crate option	None in stdlib	`dashmap::DashMap`
Thread safety	Runtime exception risk	Compile-time `Send`/`Sync`

// 466. Concurrent HashMap — sharded locking
use std::collections::HashMap;
use std::hash::{Hash,Hasher,DefaultHasher};
use std::sync::{Arc,RwLock};
use std::thread;

pub struct ShardedMap<K,V> { shards: Vec<RwLock<HashMap<K,V>>>, n: usize }

impl<K:Hash+Eq+Clone,V:Clone> ShardedMap<K,V> {
    pub fn new(n: usize) -> Self { ShardedMap { shards:(0..n).map(|_|RwLock::new(HashMap::new())).collect(), n } }
    fn idx(&self, k: &K) -> usize { let mut h=DefaultHasher::new(); k.hash(&mut h); h.finish() as usize % self.n }
    pub fn insert(&self, k: K, v: V) { self.shards[self.idx(&k)].write().unwrap().insert(k,v); }
    pub fn get(&self, k: &K) -> Option<V> { self.shards[self.idx(k)].read().unwrap().get(k).cloned() }
    pub fn len(&self) -> usize { self.shards.iter().map(|s| s.read().unwrap().len()).sum() }
}

fn main() {
    let m: Arc<ShardedMap<String,u64>> = Arc::new(ShardedMap::new(16));
    let hs: Vec<_> = (0..4).map(|id|{let m=Arc::clone(&m); thread::spawn(move || {
        for i in 0..25u64 { m.insert(format!("k{}-{}",id,i), id*25+i); }
    })}).collect();
    for h in hs { h.join().unwrap(); }
    println!("entries: {} (expected 100)", m.len());
    println!("k2-10 = {:?}", m.get(&"k2-10".to_string()));
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test] fn test_concurrent() {
        let m=Arc::new(ShardedMap::<u32,u32>::new(8));
        thread::scope(|s|{ for i in 0..100u32 { let m=Arc::clone(&m); s.spawn(move || m.insert(i,i*2)); } });
        assert_eq!(m.len(),100);
    }
    #[test] fn test_get() { let m=ShardedMap::<String,i32>::new(4); m.insert("hi".to_string(),42); assert_eq!(m.get(&"hi".to_string()),Some(42)); }
}

(* 466. Sharded concurrent HashMap – OCaml *)
let n = 16
let shards = Array.init n (fun _ -> (Hashtbl.create 8, Mutex.create ()))

let shard k = (Hashtbl.hash k) mod n

let insert k v = let (t,m)=shards.(shard k) in
  Mutex.lock m; Hashtbl.replace t k v; Mutex.unlock m

let find k = let (t,m)=shards.(shard k) in
  Mutex.lock m; let v=Hashtbl.find_opt t k in Mutex.unlock m; v

let len () = Array.fold_left (fun a (t,m) ->
  Mutex.lock m; let l=Hashtbl.length t in Mutex.unlock m; a+l) 0 shards

let () =
  let ts=Array.init 4 (fun id ->
    Thread.create (fun () ->
      for i=0 to 24 do insert (Printf.sprintf "k%d-%d" id i) (id*25+i) done) ()
  ) in
  Array.iter Thread.join ts;
  Printf.printf "total=%d\n" (len ());
  Printf.printf "k2-10=%s\n" (match find "k2-10" with None->"?" | Some v->string_of_int v)