Lesson 20 · Pick a register - Build a Bloom Filter and Probabilistic Sketches

Pick a register

A HyperLogLog answers a third question - how many distinct items did the stream hold? It splits the hash into two parts; the first part chooses which register to update. Today you build that register selection.

The goal

Use the top p bits of an item's hash to select one of 2 to the p registers.

Start here - the target

TO DO

Scenario: The high bits of the hash choose a register

Givenp = 4, giving 16 registers, where the register index is the top 4 bits of the 64-bit Hash1

Whenthe register for "cat" is computed (Hash1("cat") is 0xf5e307190ce4a327, whose top 4 bits are 1111)

Thenit is 15

Andthe register for "the" is 5 and the register for "dog" is 12

Background

HyperLogLog estimates cardinality - the count of distinct items - in a few hundred bytes no matter how many items stream past. The trick starts by hashing each item and slicing the 64-bit hash into two fields. The top p bits pick one of 2^p registers; the rest of the bits will feed a measurement in the next lesson. With p = 4 there are 16 registers, and an item’s register is simply its hash shifted right by 64 - p.

Using the hash’s high bits to bucket items means the same item always lands in the same register, and distinct items scatter roughly evenly across all of them. Each register will summarize the items that fell into it, and combining the registers at the end yields the estimate. Today is just the routing - which register does an item belong to.

Make it work

type HLL struct {
  registers []uint8
  p         uint // number of index bits
}
func NewHLL(p uint) *HLL { return &HLL{registers: make([]uint8, 1<<p), p: p} }
func (h *HLL) register(x uint64) int { return int(x >> (64 - h.p)) } // top p bits

CheckpointDONE

Your HyperLogLog routes each item to a register by its high bits. Commit and stop here.