Struct CountMinSketch 

pub struct CountMinSketch { /* private fields */ }

A high-concurrency, memory-efficient frequency estimator.

Uses AtomicU16 counters in a 2D matrix to provide a probabilistic upper bound on item frequency. Designed for high-throughput environments where a small overestimation error is acceptable in exchange for wait-free/lock-free performance.

Implementations

impl CountMinSketch

pub fn new(columns: usize, rows: usize) -> Self

Creates a new CountMinSketch with the specified logical dimensions.

Arguments

• columns - The logical width per row. The actual storage is doubled and rounded to the next power of two to optimize indexing via bitwise masking.
• rows - The number of independent hash functions.

Panics

Panics if rows > 8, as it exceeds the available static prime seeds.

pub fn increment<K>(&self, key: &K, context: &ThreadContext)

where K: Eq + Hash + ?Sized,

Increments the frequency estimate for a key across all rows.

Uses a saturating atomic CAS loop to ensure counters never overflow. If contention is detected, the provided backoff is utilized to reduce CPU cache-coherency traffic.

pub fn decrement<K>(&self, key: &K, context: &ThreadContext)

where K: Eq + Hash + ?Sized,

Decrements the frequency estimate for a key, saturating at zero.

Useful for manual aging or correction. The CAS loop prevents integer underflow, which would otherwise erroneously transform a “cold” item into an “ultra-hot” item (65,535).

pub fn decay(&self, context: &ThreadContext)

Performs a global aging operation by halving every counter in the sketch.

This reduces the “weight” of historical data, allowing the sketch to adapt to changes in key distribution over time. Uses a CAS loop per counter to maintain atomicity during the bit-shift.

pub fn contains<K: Eq + Hash>(&self, key: &K) -> bool

Checks if an item is likely present in the sketch (estimate > 0).

pub fn get<K>(&self, key: &K) -> u16

where K: Eq + Hash + ?Sized,

Retrieves the estimated frequency of a key.

The estimate is the minimum value found across all rows for the given key. This is a mathematically guaranteed upper bound of the true frequency.