Merging

One powerful feature of HyperLogLog is that multiple counters can be merged easily.

Each HyperLogLog contains many registers (buckets). To merge two HyperLogLogs, we simply compare the registers one by one and keep the maximum value for each register.

class HyperLogLog {
  // ... constructor and add() method from before ...
 
  merge(other: HyperLogLog): HyperLogLog {
    if (other.p !== this.p) {
      throw new Error("Cannot merge HyperLogLogs with different precision");
    }
 
    const result = new HyperLogLog(this.p);
    for (let i = 0; i < this.m; i++) {
      result.registers[i] = Math.max(this.registers[i], other.registers[i]);
    }
    return result;
  }
}

This works because each register stores the best information seen so far. Taking the maximum preserves all useful information from both counters.

Thanks to this property, HyperLogLog is very useful in distributed systems, where many servers count data separately and later combine the results to get the total number of unique items.