Table of Contents

HyperLogLog<T> Class

Definition

Namespace
Bodu.Collections.Probabilistic
Assembly
Bodu.Collections.dll
Package
Bodu.Collections 1.0.0
Source
HyperLogLog{T}.cs

Represents a space-efficient probabilistic sketch that estimates the number of distinct elements added to it. The estimate is approximate: it carries a relative standard error of about 1.04/√m, where m is RegisterCount, but the sketch itself occupies only one byte per register regardless of how many elements are observed.

public sealed class HyperLogLog<T> where T : notnull

Type Parameters

T

The type of elements counted by the sketch. Must not be null.

Inheritance
HyperLogLog<T>
Inherited Members
Extension Methods

Examples

// Count distinct visitor ids with ~0.81% standard error (2^14 = 16,384 one-byte registers).
var distinct = new HyperLogLog<int>(precision: 14);

for (var i = 0; i < 100_000; i++)
    distinct.Add(i % 25_000); // 25,000 distinct values, each added four times

Console.WriteLine(distinct.EstimateCardinality()); // ~25,000

Remarks

The sketch is sized by the precision constructor argument b: it allocates m = 2^b single-byte registers, and EstimateCardinality() carries a relative standard error of approximately 1.04/√m (see StandardError). Each increment of b doubles the memory footprint and improves the error by a factor of √2: b = 4 uses 16 registers at ~26% error, while b = 14 uses 16,384 registers at ~0.81% error.

Elements are hashed via the supplied IEqualityComparer<T> (or Default): the comparer's 32-bit GetHashCode(T) is expanded through a deterministic SplitMix64-style avalanche into the shared double-hash pair, of which only the first 64-bit value is consumed - HyperLogLog needs a single well-avalanched hash, not a probe sequence, so the second value is deliberately unused. The top b bits select a register and the remaining 64 − b bits contribute their leading-zero rank. All entropy therefore derives from the 32-bit comparer hash - standard practice for comparer-based sketches - which caps the number of distinguishable elements at 2³² and bounds accuracy well below the theoretical HyperLogLog error on very large cardinalities: two elements with equal comparer hashes are indistinguishable and count once.

The expansion is platform-stable, but the comparer may not be: GetHashCode() is randomized per process, so exported state for string elements (or any type with a randomized hash) is only meaningful when re-imported within the same process, or when a custom comparer with a stable hash is used.

EstimateCardinality() applies the standard HyperLogLog small-range correction (linear counting) while any register is still zero and the raw estimate is at most 2.5·m. The classic large-range correction from the original paper - which compensates for hash collisions as the true cardinality approaches the size of the hash space - is not applied. Although the register pipeline is 64-bit, all of its entropy derives from the 32-bit comparer hash expanded through a bijective mixer, so the effective hash space remains 2³²: estimates progressively underestimate the true cardinality from roughly 10⁸ distinct elements onward, and approach a hard asymptote near 2³² (about 4.3 billion) - beyond that point additional distinct elements produce no increase in the estimate.

MergeWith(HyperLogLog<T>) combines two compatible sketches by register-wise maximum, after which this sketch estimates the number of distinct elements in the union of both source streams. Merging is lossless - merging sketches of two streams yields exactly the sketch that observing the concatenated stream would have produced - and elements present in both streams are not double-counted.

The export format produced by TryExport(Span<byte>, out int) / Export(Span<byte>) and consumed by Import(ReadOnlySpan<byte>, IEqualityComparer<T>?) is an opaque, version-checked snapshot, not a wire contract; its layout may change between library versions with a corresponding version-byte bump.

HyperLogLog<T> is not thread-safe. Concurrent reads and writes require external synchronization.

Constructors

HyperLogLog(int)

Initializes a new instance of the HyperLogLog<T> class with the specified precision, using the default equality comparer.

public HyperLogLog(int precision)

Parameters

precision int

The precision (b): the sketch allocates 2^b one-byte registers.

Remarks

Precision trades memory for accuracy: the sketch uses m = 2^b registers and the estimate's relative standard error is approximately 1.04/√m, so each extra bit of precision doubles the footprint and improves the error by √2.

Exceptions

ArgumentOutOfRangeException

precision is outside the inclusive interval [4, 18].

HyperLogLog(int, IEqualityComparer<T>?)

Initializes a new instance of the HyperLogLog<T> class with the specified precision, using the specified equality comparer.

public HyperLogLog(int precision, IEqualityComparer<T>? comparer)

Parameters

precision int

The precision (b): the sketch allocates 2^b one-byte registers.

comparer IEqualityComparer<T>

The equality comparer whose hash codes drive register selection. If null, the default equality comparer for T is used.

Remarks

Precision trades memory for accuracy: the sketch uses m = 2^b registers and the estimate's relative standard error is approximately 1.04/√m, so each extra bit of precision doubles the footprint and improves the error by √2.

Exceptions

ArgumentOutOfRangeException

precision is outside the inclusive interval [4, 18].

Properties

Comparer

Gets the equality comparer whose hash codes drive register selection.

public IEqualityComparer<T> Comparer { get; }

Property Value

IEqualityComparer<T>

The IEqualityComparer<T> instance supplied at construction, or the default comparer.

Precision

Gets the precision (b): the number of hash bits used to select a register.

public int Precision { get; }

Property Value

int

The precision constructor argument; always within the inclusive interval [4, 18].

RegisterCount

Gets the number of registers (m) backing the sketch.

public int RegisterCount { get; }

Property Value

int

2^b where b is Precision; each register occupies one byte.

StandardError

Gets the relative standard error of EstimateCardinality() implied by the precision.

public double StandardError { get; }

Property Value

double

1.04/√m where m is RegisterCount - approximately 0.26 at precision 4 and 0.0081 at precision 14.

Remarks

This is the asymptotic one-sigma relative error of the HyperLogLog estimator; roughly 65% of estimates fall within one standard error of the true cardinality and roughly 99% within three.

Methods

Add(T)

Adds an element to the sketch. Adding an element that hashes identically to one already observed leaves the sketch unchanged.

public void Add(T item)

Parameters

item T

The element to count. Must not be null.

Exceptions

ArgumentNullException

item is null.

Clear()

Removes all state from the sketch by zeroing every register, after which EstimateCardinality() returns 0.

public void Clear()

EstimateCardinality()

Estimates the number of distinct elements added to the sketch.

public double EstimateCardinality()

Returns

double

The estimated distinct-element count: the bias-corrected harmonic mean α·m²/Σ2^(−reg), or the linear counting estimate m·ln(m/V) (V = number of zero registers) when the raw estimate is at most 2.5·m and at least one register is still zero. An empty sketch returns exactly 0.

Remarks

The estimate is unbiased with a relative standard error of approximately StandardError. It is not monotonic in the true cardinality at fine granularity - adding one element can move the estimate by more or less than one - but it converges on the true count as the stream grows.

The original algorithm's large-range correction is not applied. Because the 64-bit ranking pipeline draws all of its entropy from the 32-bit comparer hash (expanded through a bijective mixer), the effective hash space is 2³²: the estimate progressively falls below the true cardinality from roughly 10⁸ distinct elements onward and saturates near 2³². See the class remarks for details.

Export(Span<byte>)

Writes the sketch state to destination, which must be at least GetExportByteCount() bytes long.

public void Export(Span<byte> destination)

Parameters

destination Span<byte>

The buffer that receives the exported state.

Exceptions

ArgumentException

destination is shorter than GetExportByteCount() bytes.

GetExportByteCount()

Returns the number of bytes required to export the sketch state via TryExport(Span<byte>, out int) or Export(Span<byte>).

public int GetExportByteCount()

Returns

int

The exact export size in bytes for this sketch's configuration.

Import(ReadOnlySpan<byte>, IEqualityComparer<T>?)

Creates a HyperLogLog<T> from state previously produced by TryExport(Span<byte>, out int) or Export(Span<byte>).

public static HyperLogLog<T> Import(ReadOnlySpan<byte> source, IEqualityComparer<T>? comparer = null)

Parameters

source ReadOnlySpan<byte>

The exported sketch state.

comparer IEqualityComparer<T>

The equality comparer to associate with the imported sketch. Must be the comparer (or an equal comparer) the exporting sketch used, or estimates are undefined. If null, the default equality comparer for T is used.

Returns

HyperLogLog<T>

A new sketch whose register state matches the exported sketch.

Remarks

The comparer is not part of the exported state; the caller must re-supply it. For element types with process-randomized hash codes (notably string under the default comparer), an export is only meaningful within the process that produced it.

Exceptions

ArgumentException

source is truncated, carries an unsupported format version, or does not describe a valid sketch.

MergeWith(HyperLogLog<T>)

Merges another compatible sketch into this one by taking the register-wise maximum, so that this sketch subsequently estimates the number of distinct elements in the union of both source streams.

public void MergeWith(HyperLogLog<T> other)

Parameters

other HyperLogLog<T>

The sketch to merge into this one. Must not be null.

Remarks

Compatibility requires an identical Precision and the same or an equal comparer instance - in practice, sketches constructed with the same parameters. The other sketch is not modified. The merge is lossless and idempotent: elements observed by both sketches are not double-counted, and merging a sketch with itself leaves it unchanged.

Comparer identity is decided by Equals(object) (after a reference check). Two distinct instances of a custom comparer type that does not override Equals(object) compare unequal even when behaviourally identical, and the merge is rejected. Share a single comparer instance between sketches that will be merged, or override Equals (and GetHashCode) on the comparer type.

Exceptions

ArgumentNullException

other is null.

ArgumentException

other is incompatible: its Precision or comparer differs from this sketch's.

TryExport(Span<byte>, out int)

Attempts to write the sketch state to destination.

public bool TryExport(Span<byte> destination, out int bytesWritten)

Parameters

destination Span<byte>

The buffer that receives the exported state.

bytesWritten int

When the method returns true, the number of bytes written (always GetExportByteCount()); otherwise 0.

Returns

bool

true when destination is large enough and the state was written; otherwise false.

Applies to

ProductVersions
.NET8, 10