func(m *HashMap) Range(fn func(key string, value interface{})bool) { for _, head := range m.buckets { for e := head; e != nil; e = e.next { if !fn(e.key, e.value) { return } } } }
本文规定：Range 执行期间，不允许修改哈希表结构。原因是插入、删除和扩容都会改变桶或链表结构，可能导致元素遗漏、重复访问等问题。这个限制是本实现主动定义的 API 契约，并不是说 Go 原生 map 在遍历期间的所有写入都一律非法。
Go 原生 map 对遍历期间插入和删除有自己的语言规范语义；并发读写则是另一类问题。运行时可能检测到部分并发读写并触发 fatal error，但不能把它等同于普通的同 goroutine 遍历期间修改。
funchashString(s string)uint32 { h := uint32(2166136261) for i := 0; i < len(s); i++ { h ^= uint32(s[i]) h *= 16777619 } return h }
func(m *HashMap) index(key string) int { returnint(hashString(key) & uint32(len(m.buckets)-1)) }
func(m *HashMap) Set(key string, value interface{}) { idx := m.index(key) for e := m.buckets[idx]; e != nil; e = e.next { if e.key == key { e.value = value return } }
for _, head := range old { for e := head; e != nil; { next := e.next idx := m.index(e.key) e.next = m.buckets[idx] m.buckets[idx] = e e = next } } }
func(m *HashMap) Range(fn func(key string, value interface{})bool) { for _, head := range m.buckets { for e := head; e != nil; e = e.next { if !fn(e.key, e.value) { return } } } }
复杂度分析：这些选择带来了什么？
令 n 为元素数量，m 为桶数量，α = n / m 为负载因子。以下平均复杂度假设哈希分布合理，并暂时忽略字符串哈希计算本身的成本；若 key 长度为 L，计算哈希值通常还需要 O(L) 时间。
单次 Set 可能因为扩容而产生 O(m+n) 的成本，但在合理的翻倍扩容策略下，连续插入操作的扩容成本可以摊还到多次插入中。摊还复杂度较低，并不代表每一次操作的延迟都相同；如果系统特别关注尾延迟，就需要进一步研究分批迁移等策略。
测试：如何验证设计决策？
数据结构代码不能只靠“能跑”来证明正确。至少应该验证更新是否改变 size、删除边界是否正确、扩容后元素是否仍可访问，以及 Range 是否支持提前终止。
m.Delete("missing") if m.Len() != 1 { t.Fatalf("Len() = %d, want 1 after deleting missing key", m.Len()) }
m.Delete("name") if _, ok := m.Get("name"); ok { t.Fatal("key should not exist after Delete") } if m.Len() != 0 { t.Fatalf("Len() = %d, want 0 after Delete", m.Len()) } }
funcTestResizeKeepsEntries(t *testing.T) { m := New() const count = 1000
for i := 0; i < count; i++ { key := fmt.Sprintf("key-%d", i) m.Set(key, i) }
// pickCollidingKeys 返回 n 个落在同一个桶里的 key。 funcpickCollidingKeys(t *testing.T, m *HashMap, n int) []string { t.Helper()
groups := make(map[int][]string) for i := 0; i < 1000000; i++ { key := fmt.Sprintf("collide-%d", i) idx := m.index(key) groups[idx] = append(groups[idx], key) iflen(groups[idx]) >= n { return groups[idx][:n] } } t.Fatalf("failed to find %d keys in the same bucket", n) returnnil }
// chainKeys 按表头到表尾的顺序读出桶里的 key。 funcchainKeys(m *HashMap, idx int) []string { var keys []string for e := m.buckets[idx]; e != nil; e = e.next { keys = append(keys, e.key) } return keys }
funcTestDeleteHeadMiddleTail(t *testing.T) { m := New() keys := pickCollidingKeys(t, m, 3) // 头插后链序为 keys[2] -> keys[1] -> keys[0]
funcTestDifferentialAgainstNativeMap(t *testing.T) { m := New() want := make(map[string]int) r := rand.New(rand.NewSource(20261030))
for i := 0; i < 20000; i++ { key := fmt.Sprintf("k-%d", r.Intn(500))
if r.Intn(10) < 3 { // 30% 删除，70% 写入或更新 m.Delete(key) delete(want, key) } else { v := r.Int() m.Set(key, v) want[key] = v }
if m.Len() != len(want) { t.Fatalf("step %d: Len() = %d, want %d", i, m.Len(), len(want)) } }
for k, v := range want { if got, ok := m.Get(k); !ok || got != v { t.Fatalf("Get(%q) = (%v, %v), want (%v, true)", k, got, ok, v) } }
visited := 0 m.Range(func(key string, value interface{})bool { v, ok := want[key] if !ok { t.Fatalf("Range yielded unexpected key %q", key) } if value != v { t.Fatalf("Range yielded %q = %v, want %v", key, value, v) } visited++ returntrue }) if visited != len(want) { t.Fatalf("Range visited %d entries, want %d", visited, len(want)) } }
实现放在 hashmap.go，测试放在 hashmap_test.go，两者同属 package hashmap。这里有一个容易踩的坑：不要用 go test hashmap_test.go。显式列出文件时，Go 只编译点名的文件，实现文件不参与，New 会报 undefined。正确的写法是把目录交给它：go test .。上述用例在 Go 1.27 下全部通过，包括 -race。
没有覆盖的部分也很明确：并发安全不是本实现的目标，因此没有并发测试；在 Range 回调里修改表结构属于违反 API 契约，测试无法“验证”一个未定义行为。性能方面可以用 go test -bench . 观察，Set 因为要处理扩容，耗时会明显高于 Get。
与 Go 原生 map 的差距
本文实现的目标是讲清楚基本机制，不是复刻 Go 运行时。比较时还必须注意 Go 版本差异：Go 1.24 起，内置 map 已采用基于 Swiss Tables 的新实现；Go 1.23 及以前的实现采用传统桶与溢出桶结构。不要把旧版实现细节直接描述为当前版本的内部机制。
