Kodas

hash.go — karkasas

Sukurk hash.go. Kaip ir nuo septintos pamokos, gauni karkasą: paketą, importus, tipus, parašus ir sutartis komentaruose. Kūnai — tavo.

Ką verta pasižymėti prieš rašant:

Put su jau esamu raktu privalo PAKEISTI įrašą, ne pridėti antrą. Testas tai tikrina; šeštas žingsnis paaiškina, kodėl tai svarbu.
Kiekvienas raktų palyginimas eina per c.Hit(). Tas skaičius ir yra praeitos grandinėlės ilgis — vienintelis dydis, kuriuo remiasi visas „vidutinis O(1)".
Plėsk PRIEŠ įterpdamas, kai apkrova pasiekė 1.0. Jei plėsi po įterpimo, koeficientas trumpam viršys ribą — testas tai pastebės.
grow iš naujo skaičiuoja hashKey % naujas dydis. Senas kibiro numeris po padvigubinimo nebegalioja; perkelti grandinėlę kaip visumą nevalia.
NoGrow yra tik demonstracijai (-nogrow): jis leidžia pamatyti, kas būna be plėtimosi.

ChainStats vidurkį skaičiuoja tik per netuščius kibirus. Su tuščiais vidurkis būtų tiesiog apkrovos koeficientas ir nieko naujo nepasakytų; be jų jis rodo, kokio ilgio grandinėlę realiai pereini, kai kibiras iš viso ką nors turi.

hash.go SUKURTI

Sukurk šį failą kataloge ./

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")
}