Chaintable

A SwissTable-style open-addressed hash map with O(1) uniform random sampling for Redis-style eviction.

Every live key appears exactly once in a dense side index (random_slots). Sampling never scans the table. Keys with expiry are also tracked in volatile_slots.

Features

• SwissTable layout: groups of 8 slots with 7-bit control fingerprints
• random_slots: dense Vec<SlotId> — true O(1) random pick
• volatile_slots: same idea, only for keys with expiry
• Eviction policies: allkeys-random / allkeys-lru / allkeys-lfu (+ volatile variants)
• No reservoir-over-all-keys: eviction samples from the side index only

Quick start

cd chaintable
cargo build
cargo test

Example

use chaintable::{Dict, EvictionPolicy};
use rand::RngExt;

let mut dict = Dict::new();
dict.insert_with_meta("a".into(), 1, Some(100), Some(1));
dict.insert_with_meta("b".into(), 2, None, Some(2));

let mut rng = rand::rng();
let slots = dict.sample_slots(3, &mut rng);
let _ = dict.evict(EvictionPolicy::AllkeysLru { sample_size: 5 }, &mut rng);

Sampling & eviction

API	Behavior
sample_slots(n)	n slots with replacement, O(n)
sample_slots_unique(n)	up to n distinct slots
sample_volatile_slots(n)	same, volatile keys only
EvictionPolicy::AllkeysRandom	one random live key
AllkeysLru { sample_size }	sample then evict oldest last_accessed_at
AllkeysLfu { sample_size }	sample then evict lowest access_count
Volatile*	same policies restricted to expiring keys

Design

groups[g].ctrl[s]     // EMPTY / DELETED / h2 fingerprint
groups[g].entries[s]  // Option<Entry> with random_index, volatile_index, LRU/LFU meta

random_slots:   [SlotId, ...]   // len == dict.len(); every live key once
volatile_slots: [SlotId, ...]   // only keys with expires_at

• insert (new): place in SwissTable, push SlotId, store random_index
• insert (existing): update value/meta only — no duplicate slot
• remove: swap_remove from side indexes, fix moved entry’s index, tombstone ctrl
• rehash: rebuild both indexes from scratch (old SlotIds are invalid)

License

Licensed under the MIT License. See LICENSE for details.

Copyright (c) 2026 Aritro