Hash tables & probabilistic structures

package main
 
import (
	"fmt"
	"hash/maphash"
)
 
type state uint8
 
const (
	empty state = iota
	used
	deleted // tombstone
)
 
type slot[K comparable, V any] struct {
	key   K
	val   V
	state state
}
 
// Map is an open-addressing hash map with linear probing and tombstones.
type Map[K comparable, V any] struct {
	slots      []slot[K, V]
	count      int // live entries
	tombstones int
	seed       maphash.Seed
}
 
func New[K comparable, V any]() *Map[K, V] {
	return &Map[K, V]{slots: make([]slot[K, V], 8), seed: maphash.MakeSeed()}
}
 
func (m *Map[K, V]) index(k K) int {
	return int(maphash.Comparable(m.seed, k) % uint64(len(m.slots)))
}
 
// find returns the slot holding k, or (-1, first reusable slot).
func (m *Map[K, V]) find(k K) (int, int) {
	reuse := -1
	for i, n := m.index(k), 0; n < len(m.slots); i, n = (i+1)%len(m.slots), n+1 {
		s := &m.slots[i]
		switch s.state {
		case empty:
			if reuse < 0 {
				reuse = i
			}
			return -1, reuse
		case deleted:
			if reuse < 0 {
				reuse = i // remember the first tombstone, but keep probing
			}
		case used:
			if s.key == k {
				return i, -1
			}
		}
	}
	return -1, reuse
}
 
func (m *Map[K, V]) grow() {
	old := m.slots
	m.slots = make([]slot[K, V], 2*len(old))
	m.count, m.tombstones = 0, 0
	for _, s := range old {
		if s.state == used {
			m.Set(s.key, s.val) // rehash into the bigger table; tombstones are dropped
		}
	}
}
 
func (m *Map[K, V]) Set(k K, v V) {
	if 4*(m.count+m.tombstones+1) > 3*len(m.slots) { // keep the load factor under 0.75
		m.grow()
	}
	i, reuse := m.find(k)
	if i >= 0 {
		m.slots[i].val = v
		return
	}
	if m.slots[reuse].state == deleted {
		m.tombstones--
	}
	m.slots[reuse] = slot[K, V]{key: k, val: v, state: used}
	m.count++
}
 
func (m *Map[K, V]) Get(k K) (V, bool) {
	if i, _ := m.find(k); i >= 0 {
		return m.slots[i].val, true
	}
	var zero V
	return zero, false
}
 
func (m *Map[K, V]) Delete(k K) {
	if i, _ := m.find(k); i >= 0 {
		var zero slot[K, V]
		m.slots[i] = zero
		m.slots[i].state = deleted
		m.count--
		m.tombstones++
	}
}
 
func (m *Map[K, V]) Len() int { return m.count }
 
func main() {
	m := New[string, int]()
	words := []string{"go", "rust", "zig", "c", "java", "python", "ruby", "elixir", "haskell", "ocaml"}
	for i, w := range words {
		m.Set(w, i)
	}
	fmt.Println("len", m.Len(), "slots", len(m.slots))
	v, ok := m.Get("haskell")
	fmt.Println("haskell:", v, ok)
	m.Delete("go")
	m.Delete("zig")
	_, ok = m.Get("go")
	fmt.Println("after deletes, go present:", ok, " len", m.Len())
 
	// Everything else must still be reachable past the tombstones.
	all := true
	for i, w := range words {
		if w == "go" || w == "zig" {
			continue
		}
		got, ok := m.Get(w)
		all = all && ok && got == i
	}
	fmt.Println("all other keys still found:", all)
 
	big := New[int, int]()
	for i := range 100_000 {
		big.Set(i, i*i)
	}
	x, _ := big.Get(99_999)
	fmt.Println("100000 keys, slots", len(big.slots), " 99999² =", x)
}

len 10 slots 16
haskell: 8 true
after deletes, go present: false  len 8
all other keys still found: true
100000 keys, slots 262144  99999² = 9999800001

package main
 
import (
	"fmt"
	"hash/fnv"
	"math"
)
 
type Bloom struct {
	bits []uint64
	m, k uint64
}
 
func NewBloom(n int, p float64) *Bloom {
	m := uint64(math.Ceil(-float64(n) * math.Log(p) / (math.Ln2 * math.Ln2)))
	k := uint64(math.Round(float64(m) / float64(n) * math.Ln2))
	return &Bloom{bits: make([]uint64, (m+63)/64), m: m, k: max(k, 1)}
}
 
func (b *Bloom) hashes(s string) (uint64, uint64) {
	h := fnv.New64a()
	h.Write([]byte(s))
	h1 := h.Sum64()
	h2 := h1>>33 | h1<<31 // a second, different-looking hash from the same bits
	return h1, h2 | 1     // odd, so the k positions differ
}
 
func (b *Bloom) Add(s string) {
	h1, h2 := b.hashes(s)
	for i := range b.k {
		pos := (h1 + i*h2) % b.m
		b.bits[pos/64] |= 1 << (pos % 64)
	}
}
 
func (b *Bloom) MayContain(s string) bool {
	h1, h2 := b.hashes(s)
	for i := range b.k {
		pos := (h1 + i*h2) % b.m
		if b.bits[pos/64]&(1<<(pos%64)) == 0 {
			return false // definitely never added
		}
	}
	return true // probably added
}
 
func main() {
	const n = 10_000
	b := NewBloom(n, 0.01)
	fmt.Printf("%d items at 1%%: %d bits (%.1f KB), %d hashes\n", n, b.m, float64(b.m)/8/1024, b.k)
	for i := range n {
		b.Add(fmt.Sprintf("user-%d", i))
	}
	misses := 0
	for i := range n {
		if !b.MayContain(fmt.Sprintf("user-%d", i)) {
			misses++
		}
	}
	fmt.Println("false negatives:", misses)
	fp := 0
	for i := range 100_000 {
		if b.MayContain(fmt.Sprintf("visitor-%d", i)) {
			fp++
		}
	}
	fmt.Printf("false positives: %d of 100000 (%.2f%%)\n", fp, float64(fp)/1000)
}

10000 items at 1%: 95851 bits (11.7 KB), 7 hashes
false negatives: 0
false positives: 937 of 100000 (0.94%)

package main
 
import (
	"fmt"
	"math/rand/v2"
	"slices"
)
 
func reservoir(stream []int, k int, r *rand.Rand) []int {
	res := slices.Clone(stream[:k])
	for i := k; i < len(stream); i++ {
		if j := r.IntN(i + 1); j < k { // probability k/(i+1), with i 0-based
			res[j] = stream[i]
		}
	}
	return res
}
 
func fisherYates(a []int, r *rand.Rand) {
	for i := len(a) - 1; i > 0; i-- {
		j := r.IntN(i + 1) // 0..i
		a[i], a[j] = a[j], a[i]
	}
}
 
func naiveShuffle(a []int, r *rand.Rand) {
	for i := range a {
		j := r.IntN(len(a)) // WRONG: any index
		a[i], a[j] = a[j], a[i]
	}
}
 
func main() {
	r := rand.New(rand.NewPCG(7, 7))
 
	stream := make([]int, 100)
	for i := range stream {
		stream[i] = i
	}
	hits := make([]int, 100)
	for range 20_000 {
		for _, x := range reservoir(stream, 5, r) {
			hits[x]++
		}
	}
	fmt.Println("reservoir: each item picked about 1000 times:", hits[0], hits[50], hits[99])
 
	count := func(shuffle func([]int, *rand.Rand)) map[string]int {
		c := map[string]int{}
		for range 60_000 {
			a := []int{1, 2, 3}
			shuffle(a, r)
			c[fmt.Sprint(a)]++
		}
		return c
	}
	fmt.Println("fisher-yates:", count(fisherYates))  // all about 10000
	fmt.Println("naive:       ", count(naiveShuffle)) // some orders clearly favored
}

reservoir: each item picked about 1000 times: 1042 1016 1024
fisher-yates: map[[1 2 3]:10050 [1 3 2]:9979 [2 1 3]:9899 [2 3 1]:10074 [3 1 2]:10007 [3 2 1]:9991]
naive:        map[[1 2 3]:8984 [1 3 2]:10898 [2 1 3]:11183 [2 3 1]:11122 [3 1 2]:8967 [3 2 1]:8846]