Hash Tables — Programuoki

Code

hash.go — the skeleton

Create hash.go. As since lesson 7 you get a skeleton: package, imports, types, signatures and contracts in the comments. The bodies are yours.

Worth noting before you start:

Put with a key that is already present must REPLACE the item, not add a second one. The test checks it; step 6 explains why it matters.
Every key comparison goes through c.Hit(). That count is the chain you walked — the one quantity the whole "average O(1)" rests on.
Grow BEFORE inserting, once the load factor has reached 1.0. Grow after and the factor briefly exceeds the bound — the test will notice.
grow recomputes hashKey % new size. The old bucket number is meaningless after doubling; you cannot move a chain across wholesale.
NoGrow exists only for the demonstration (-nogrow): it lets you see what happens without resizing.

ChainStats averages over the non-empty buckets only. Including the empty ones would make the mean equal the load factor and tell you nothing new; without them it tells you how long a chain actually is when a bucket holds anything at all.

hash.go CREATE

Create this file in ./

package main

import "algo/metrics"

// This file is YOURS to fill in. The algorithm is in step 2; hash_test.go
// decides whether you got it right.
//
// Every comparison between two KEYS goes through c.Hit(). That count is the
// chain length you walked, and it is what "O(1) average" actually rests on —
// so it is the number the whole lesson is about.

// entry is one node in a bucket's chain.
type entry struct {
	key  string
	item Item
	next *entry
}

// HashIndex is a hash table with separate chaining.
//
// Go's map already does this and more. You are writing it because "O(1)
// average" stops being a slogan once you have seen the chain.
type HashIndex struct {
	buckets []*entry
	n       int  // how many items are stored
	Resizes int  // how many times the table has grown
	NoGrow  bool // set by -nogrow, to show what happens without resizing
}

// NewHashIndex makes a table with the given number of buckets (at least 1).
func NewHashIndex(buckets int) *HashIndex {
	panic("not implemented")
}

// hashKey is FNV-1a: start from the offset basis, then for each byte xor it in
// and multiply by the prime.
//
//	offset = 14695981039346656037
//	prime  =     1099511628211
//
// It hashes BYTES, and for a hash table that is correct — two identical strings
// have identical bytes whatever alphabet they are written in. Step 7 shows a
// structure where working in bytes is NOT correct.
func hashKey(s string) uint64 {
	panic("not implemented")
}

// LoadFactor is items divided by buckets.
func (h *HashIndex) LoadFactor() float64 { panic("not implemented") }

func (h *HashIndex) Len() int     { panic("not implemented") }
func (h *HashIndex) Buckets() int { panic("not implemented") }

// Put stores an item under its Title.
//
// If the key is ALREADY PRESENT it must REPLACE the existing item, not add a
// second entry — a duplicate key is not a collision, and the test checks this.
//
// Before inserting, grow when the load factor has reached 1.0 (unless NoGrow).
func (h *HashIndex) Put(it Item, c *metrics.Counter) {
	panic("not implemented")
}

// Get finds an item by Title, walking the bucket's chain and counting every key
// comparison.
func (h *HashIndex) Get(title string, c *metrics.Counter) (Item, bool) {
	panic("not implemented")
}

// grow doubles the bucket count and rehashes every entry. O(n) when it happens,
// and it is what keeps the average chain short. Count the resizes.
func (h *HashIndex) grow() {
	panic("not implemented")
}

// ChainStats returns the longest chain, how many buckets are empty, and the
// mean chain length over the NON-EMPTY buckets.
func (h *HashIndex) ChainStats() (longest, empty int, mean float64) {
	panic("not implemented")
}

// Keys returns every stored Title in whatever order the buckets are walked.
//
// THAT ORDER IS NOT MEANINGFUL, and step 8 is about why that matters.
func (h *HashIndex) Keys() []string {
	panic("not implemented")
}