Struct HyperLogLog 

pub struct HyperLogLog<T, H, W = usize, const BETA: bool = true> { /* private fields */ }

Estimator logic implementing the HyperLogLog algorithm.

Instances are created through HyperLogLogBuilder:

// Default: LogLog-β correction enabled, usize backend
let logic = HyperLogLogBuilder::new(1_000_000)
    .log2_num_regs(8)
    .build::<String>().unwrap();

// Disable LogLog-β, use classic HLL + linear-counting fallback
let logic = HyperLogLogBuilder::new(1_000_000)
    .log2_num_regs(8)
    .beta::<false>()
    .build::<String>().unwrap();

Type parameters

• T: the type of elements to count (must implement Hash).

• H: the BuildHasher used to hash elements.

• W: the unsigned word type for the register backend (see below).

• BETA: when true (the default), the LogLog-β bias correction is used during estimation. This provides better accuracy across the full cardinality range through a single formula, eliminating the need for a separate linear-counting correction. The cost is roughly 20ns per estimate call when some registers are still zero; when all registers are populated, the correction is skipped and performance is identical to the classic formula. Set to false via HyperLogLogBuilder::beta to use the original HyperLogLog formula instead.

Backend alignment

W must be able to represent exactly the backend of an estimator. While usually usize will work (and it is the default type chosen by HyperLogLogBuilder::new), with odd register sizes and a small number of registers it might be necessary to select a smaller type, resulting in slower merges. For example, using 16 5-bit registers one needs to use u16, whereas for 16 6-bit registers u32 will be sufficient.

Formally, W::BITS must divide (1 << log2_num_regs) * register_size (using HyperLogLog::register_size(num_elements)). HyperLogLogBuilder::min_log2_num_regs returns the minimum value for log2_num_regs that satisfies this property.

Implementations

impl HyperLogLog<(), (), (), true>

pub fn log2_num_of_registers(rsd: f64) -> usize

Returns the logarithm of the number of registers per estimator that are necessary to attain a given relative standard deviation.

Arguments

• rsd: the relative standard deviation to be attained.

pub fn rel_std(log2_num_regs: usize) -> f64

Returns the relative standard deviation corresponding to a given number of registers per estimator.

Arguments

• log2_num_regs: the logarithm of the number of registers per estimator.

pub fn register_size(num_elements: usize) -> usize

Returns the register size in bits, given an upper bound on the number of distinct elements.

Arguments

• num_elements: an upper bound on the number of distinct elements.

Trait Implementations

impl<T, H: Clone, W: Clone, const BETA: bool> Clone for HyperLogLog<T, H, W, BETA>

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug, H: Debug, W: Debug, const BETA: bool> Debug for HyperLogLog<T, H, W, BETA>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T, H, W, const BETA: bool> Display for HyperLogLog<T, H, W, BETA>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Hash, H: BuildHasher + Clone, W: Word, const BETA: bool> EstimationLogic for HyperLogLog<T, H, W, BETA>

where u32: PrimitiveNumberAs<W>,

type Item = T

The type of items.

type Backend = [W]

The type of the backend.

type Estimator<'a> = DefaultEstimator<HyperLogLog<T, H, W, BETA>, &'a HyperLogLog<T, H, W, BETA>, Box<[W]>> where T: 'a, W: 'a, H: 'a

The type of an estimator.

fn new_estimator(&self) -> Self::Estimator<'_>

Creates a new empty estimator using this logic.

fn add(&self, backend: &mut Self::Backend, element: impl Borrow<T>)

Adds an element to an estimator with the given backend.

fn estimate(&self, backend: &[W]) -> f64

Returns an estimation of the number of distinct elements that have been added to an estimator with the given backend so far.

fn clear(&self, backend: &mut [W])

Clears a backend, making it empty.

fn set(&self, dst: &mut [W], src: &[W])

Sets the contents of dst to the contents of src.

impl<T: Hash, H: BuildHasher + Clone, W: Word, const BETA: bool> MergeEstimationLogic for HyperLogLog<T, H, W, BETA>

where u32: PrimitiveNumberAs<W>,

type Helper = HyperLogLogHelper<W>

The type of the helper used in merge calculations.

fn new_helper(&self) -> Self::Helper

Creates a new helper to use in merge operations.

fn merge_with_helper(&self, dst: &mut [W], src: &[W], helper: &mut Self::Helper)

Merges src into dst using the provided helper to avoid allocations.

fn merge(&self, dst: &mut Self::Backend, src: &Self::Backend)

Merges src into dst.

impl<T: PartialEq, H: PartialEq, W: PartialEq, const BETA: bool> PartialEq for HyperLogLog<T, H, W, BETA>

fn eq(&self, other: &HyperLogLog<T, H, W, BETA>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: Hash, H: BuildHasher + Clone, W: Word, const BETA: bool> SliceEstimationLogic<W> for HyperLogLog<T, H, W, BETA>

where u32: PrimitiveNumberAs<W>,

fn backend_len(&self) -> usize

The number of elements of type T in a backend.

impl<T, H, W, const BETA: bool> StructuralPartialEq for HyperLogLog<T, H, W, BETA>