HyperLogLog.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace DataStructures.Probabilistic;

public class HyperLogLog<T> where T : notnull
{
    private const int P = 16;
    private const double Alpha = .673;
    private readonly int[] registers;
    private readonly HashSet<int> setRegisters;

    /// <summary>
    /// Initializes a new instance of the <see cref="HyperLogLog{T}"/> class.
    /// </summary>
    public HyperLogLog()
    {
        var m = 1 << P;
        registers = new int[m];
        setRegisters = new HashSet<int>();
    }

    /// <summary>
    /// Merge's two HyperLogLog's together to form a union HLL.
    /// </summary>
    /// <param name="first">the first HLL.</param>
    /// <param name="second">The second HLL.</param>
    /// <returns>A HyperLogLog with the combined values of the two sets of registers.</returns>
    public static HyperLogLog<T> Merge(HyperLogLog<T> first, HyperLogLog<T> second)
    {
        var output = new HyperLogLog<T>();
        for (var i = 0; i < second.registers.Length; i++)
        {
            output.registers[i] = Math.Max(first.registers[i], second.registers[i]);
        }

        output.setRegisters.UnionWith(first.setRegisters);
        output.setRegisters.UnionWith(second.setRegisters);
        return output;
    }

    /// <summary>
    /// Adds an item to the HyperLogLog.
    /// </summary>
    /// <param name="item">The Item to be added.</param>
    public void Add(T item)
    {
        var x = item.GetHashCode();
        var binString = Convert.ToString(x, 2); // converts hash to binary
        var j = Convert.ToInt32(binString.Substring(0, Math.Min(P, binString.Length)), 2); // convert first b bits to register index
        var w = (int)Math.Log2(x ^ (x & (x - 1))); // find position of the right most 1.
        registers[j] = Math.Max(registers[j], w); // set the appropriate register to the appropriate value.
        setRegisters.Add(j);
    }

    /// <summary>
    /// Determines the approximate cardinality of the HyperLogLog.
    /// </summary>
    /// <returns>the approximate cardinality.</returns>
    public int Cardinality()
    {
        // calculate the bottom part of the harmonic mean of the registers
        double z = setRegisters.Sum(index => Math.Pow(2, -1 * registers[index]));

        // calculate the harmonic mean of the set registers
        return (int)Math.Ceiling(Alpha * setRegisters.Count * (setRegisters.Count / z));
    }
}