hashmap.go

// Package hashmap implements a teaching hash table with separate chaining.
//
// For real code, use Go's built-in `map`. This package exists to make the
// inner workings of a hash table concrete: hashing, bucketing, chaining,
// load factor, and resizing.
package hashmap

import (
	"fmt"
	"hash/fnv"
)

const (
	defaultBuckets    = 8
	maxLoadFactorNum  = 3
	maxLoadFactorDen  = 4 // 0.75
)

type entry[K comparable, V any] struct {
	key   K
	value V
	next  *entry[K, V]
}

// HashMap is a separate-chaining hash table mapping keys of type K to values
// of type V. K must be comparable so we can detect existing keys; V can be
// anything.
type HashMap[K comparable, V any] struct {
	buckets []*entry[K, V]
	n       int
}

// New returns an empty hash map.
func New[K comparable, V any]() *HashMap[K, V] {
	return &HashMap[K, V]{buckets: make([]*entry[K, V], defaultBuckets)}
}

// Len returns the number of key-value pairs currently stored.
func (m *HashMap[K, V]) Len() int { return m.n }

// hash converts a key into a bucket index. We delegate the actual hashing to
// hash/fnv applied to the printed form of the key. This is slow but works
// for any comparable key type — perfect for teaching, not for production.
func (m *HashMap[K, V]) hash(k K) int {
	h := fnv.New64a()
	fmt.Fprint(h, k)
	return int(h.Sum64() % uint64(len(m.buckets)))
}

// Put inserts or updates an entry. If the key was already present the
// previous value is returned along with true.
func (m *HashMap[K, V]) Put(k K, v V) (V, bool) {
	idx := m.hash(k)
	for cur := m.buckets[idx]; cur != nil; cur = cur.next {
		if cur.key == k {
			old := cur.value
			cur.value = v
			return old, true
		}
	}
	m.buckets[idx] = &entry[K, V]{key: k, value: v, next: m.buckets[idx]}
	m.n++
	if m.n*maxLoadFactorDen > len(m.buckets)*maxLoadFactorNum {
		m.resize(len(m.buckets) * 2)
	}
	var zero V
	return zero, false
}

// Get returns the value for k along with true if present.
func (m *HashMap[K, V]) Get(k K) (V, bool) {
	idx := m.hash(k)
	for cur := m.buckets[idx]; cur != nil; cur = cur.next {
		if cur.key == k {
			return cur.value, true
		}
	}
	var zero V
	return zero, false
}

// Delete removes the entry with key k and returns its value along with true.
// If absent, it returns the zero value and false.
func (m *HashMap[K, V]) Delete(k K) (V, bool) {
	idx := m.hash(k)
	var prev *entry[K, V]
	for cur := m.buckets[idx]; cur != nil; cur = cur.next {
		if cur.key == k {
			if prev == nil {
				m.buckets[idx] = cur.next
			} else {
				prev.next = cur.next
			}
			m.n--
			return cur.value, true
		}
		prev = cur
	}
	var zero V
	return zero, false
}

// Range calls f(key, value) for every entry. Iteration order is unspecified
// and may change between runs (intentionally — to discourage relying on it).
func (m *HashMap[K, V]) Range(f func(K, V) bool) {
	for _, head := range m.buckets {
		for cur := head; cur != nil; cur = cur.next {
			if !f(cur.key, cur.value) {
				return
			}
		}
	}
}

// resize allocates a new bucket array of the given size and re-inserts all
// existing entries. Cost is O(n + new_bucket_count) but happens rarely
// because the bucket count doubles each time.
func (m *HashMap[K, V]) resize(newSize int) {
	if newSize < defaultBuckets {
		newSize = defaultBuckets
	}
	old := m.buckets
	m.buckets = make([]*entry[K, V], newSize)
	m.n = 0
	for _, head := range old {
		for cur := head; cur != nil; cur = cur.next {
			m.Put(cur.key, cur.value)
		}
	}
}