pub struct CountMinSketch { /* private fields */ }Expand description
A lock-free probabilistic data structure for frequency estimation.
This implementation optimizes for CPU cache locality and multithreaded throughput by bit-packing 8-bit saturating counters into 64-bit atomic blocks.
Implementations§
Source§impl CountMinSketch
impl CountMinSketch
Sourcepub fn new(width: usize, depth: usize) -> Self
pub fn new(width: usize, depth: usize) -> Self
Creates a new probabilistic estimator with a specified geometry.
The physical storage is calculated by mapping the requested logical width to 64-bit atomic blocks (8 counters per block).
§Arguments
width- The logical number of counters per row. This is rounded to the next power of two to enable bitwise indexing.depth- The number of independent hash functions (rows) used to minimize the probability of overestimation.
§Panics
Panics if depth exceeds 8, as the implementation relies on a fixed set
of static prime seeds for hashing independence.
Sourcepub fn increment<K: Eq + Hash>(&self, key: &K)
pub fn increment<K: Eq + Hash>(&self, key: &K)
Increments the frequency counters for the given key.
This operation is performed across all rows (defined by depth) using a
saturating add. Counters will not exceed 255.
§Arguments
key- The item whose frequency should be increased.
Sourcepub fn decrement<K: Eq + Hash>(&self, key: &K)
pub fn decrement<K: Eq + Hash>(&self, key: &K)
Decrements the frequency counters for the given key.
This is used for manual aging or item removal within the sketch. Counters will not underflow below 0.
§Arguments
key- The item whose frequency should be decreased.
Sourcepub fn decay(&self)
pub fn decay(&self)
Performs an aging operation by halving all counters in the sketch.
This uses a bitwise trick to divide eight 8-bit counters by 2 simultaneously within each 64-bit word.
Sourcepub fn contains<K: Eq + Hash>(&self, key: &K) -> bool
pub fn contains<K: Eq + Hash>(&self, key: &K) -> bool
Returns true if the key has an estimated frequency greater than zero.
Derived by taking the minimum frequency observed across all rows.
§Arguments
key- The item to check for presence in the sketch.
Sourcepub fn get<K: Eq + Hash>(&self, key: &K) -> u8
pub fn get<K: Eq + Hash>(&self, key: &K) -> u8
Returns the estimated frequency of the provided key.
The estimate is derived by taking the minimum value found across all rows
(defined by depth). Due to the probabilistic nature of the sketch, this
value is an upper bound of the actual frequency.
§Arguments
key- The item whose frequency estimate is being requested.