Go 泛型数据结构的实现：类型安全的 HashMap、Stack 与 PriorityQueue

没有泛型之前，通用数据结构是怎么写出来的

Go 1.18 引入泛型之前，想在 Go 里写一个通用的 Stack 或者 PriorityQueue，通常只有两条路。

Go 泛型数据结构的实现：类型安全的 HashMap、Stack 与 PriorityQueue

第一条路是复制代码。为 int 写一个 intStack，为 string 写一个 stringStack，为每个业务对象再写一个 TaskStack。短时间内能用，但随着类型变多，这些结构体的 Push、Pop 逻辑几乎一模一样，只是类型名不同。

第二条路是用 interface{} 做一个通用容器。代码只写一份，但使用方需要记住容器里存的到底是什么类型，每次取出来都要手动断言。断言失败或类型记错，程序直接走到 panic 分支。

最典型的场景是调度系统。系统里用 container/heap 维护待执行的任务，堆里塞满 interface{}。每次 Pop 出来都要断言回具体的 Task 类型。业务跑了一阵之后，有人改了 Task 的字段，或者加了一个新的任务实现，断言没有同步更新，生产环境第一个报错往往不是业务逻辑错误，而是 type assertion failed。

这种问题不是几行代码能修好的，它根植于容器失去了类型信息。泛型真正解决的问题，正是在编译期把类型关系重新建立起来。

Go 泛型的关键：类型参数和约束

Go 泛型的核心只有两个概念：类型参数和约束。类型参数让结构体或函数接收一个待定的类型，约束规定这个类型必须满足的条件。

写泛型数据结构时，最常用到的约束有三个：

any：等价于 interface{}，表示不限制类型，可读性上比 interface{} 更直观。
comparable：类型支持 == 和 !=，适合做 HashMap 的键或集合里的元素。
cmp.Ordered：类型支持 <、<=、>、>= 比较，适合排序场景。

有一个容易踩的坑需要注意。早期教程经常推荐 golang.org/x/exp/constraints 包，但 Go 1.21 之后 Ordered 已经移入标准库 cmp 包，新项目直接用 cmp.Ordered 就好，不要再依赖 exp 里的实验版本。

另外不要被 any 这个名字误导，它并不是一个特殊的泛型约束，只是 interface{} 的别名。约束写得越宽，你能对类型做的事就越少。any 约束下不能假设两个值可以比较、不能假设它们有大小顺序，这些限制是理解泛型的关键。

一个泛型 Stack，和它藏着的内存细节

Stack 是泛型数据结构里最合适的入门例子，它只有两个操作，很容易看清楚泛型的边界。

type Stack<T any> struct {
    items []T
}

func NewStack<T any>() *Stack<T> {
    return &Stack<T>{}
}

func (s *Stack<T>) Push(v T) {
    s.items = append(s.items, v)
}

func (s *Stack<T>) Pop() (T, bool) {
    if len(s.items) == 0 {
        var zero T
        return zero, false
    }
    idx := len(s.items) - 1
    v := s.items[idx]
    s.items[idx] = zero
    s.items = s.items[:idx]
    return v, true
}

这段代码里值得注意的不是 Push 和 Pop 本身，而是 Pop 中把 s.items[idx] 置回零值的两行。

Go 的 slice 底层是数组，如果不把这个元素清掉，底层数组会一直持有已经弹出对象的引用。元素是值类型时影响不大，但如果栈里存的是指针或带指针的结构体，这些对象将无法被 GC 回收，时间一长就是一个隐蔽的内存问题。

Pop 的返回值选用了 (T, bool) 而不是直接返回 T。原因是 T 的零值（比如 nil、0 或空字符串）在某些场景下可能是合法数据，调用方需要感知“栈为空”这件事，而不是把零值当成有效结果。

另一个值得知道的限制是：方法不能拥有类型参数。你没法写一个方法把 Stack[T] 转换成 Stack[U]，需要转成独立函数才能做。这个限制初期不明显，等你想给容器加通用的 Map、Filter 方法时会突然撞上。

类型安全的 HashMap：comparable 约束的典型场景

Go 的 map[K]V 本身就是类型安全的，为什么还要用泛型再包一层？最常见的答案是加行为：锁、过期时间、读写统计、深拷贝，或者统一记录访问日志。

下面是一个带 RWMutex 的泛型 HashMap。它并不比原生 map 更花哨，但把并发控制的细节收拢到一个地方，业务代码只需要关心 Set 和 Get：

type HashMap<K comparable, V any> struct {
    mu sync.RWMutex
    m  map[K]V
}

func NewHashMap<K comparable, V any>() *HashMap<K, V> {
    return &HashMap<K, V>{m: make(map[K]V)}
}

func (h *HashMap<K, V>) Set(k K, v V) {
    h.mu.Lock()
    defer h.mu.Unlock()
    h.m[k] = v
}

func (h *HashMap<K, V>) Get(k K) (V, bool) {
    h.mu.RLock()
    defer h.mu.RUnlock()
    v, ok := h.m[k]
    return v, ok
}

K 的约束必须是 comparable。这里有一个容易忽略的细节：某个 struct 如果包含 slice、map 或 func 字段，是不能用 == 比较的，也就无法作为 map 的键，编译器会直接拒绝。

封装的意义在于，你可以给所有业务 map 统一加指标采集、TTL 清理或者审计日志，而不是要求每个调用方都记得“并发读 map 要加锁”。在微服务项目里，这类泛型容器经常从一个内部工具类慢慢长成基础库，使用方从这层封装里得到的不是复杂功能，而是统一的边界。

PriorityQueue：给 container/heap 套一层类型安全

Go 标准库的 container/heap 是一个比较典型的“泛型前时代”设计。它提供的是堆操作算法，但要求你实现 heap.Interface，这个接口的方法签名是 Push(x any) 和 Pop() any。也就是说，堆里存的具体类型对接口完全透明，每次 Pop 出来都必须自己断言回真实类型。

用泛型包装它并不复杂，核心思路是：内部保留一个使用 any 的实现，外部用泛型类型把不安全的类型转换隔离起来。

type priorityQueueImpl<T any> struct {
    items []T
    less  func(a, b T) bool
}

func (pq *priorityQueueImpl<T>) Len() int { return len(pq.items) }
func (pq *priorityQueueImpl<T>) Less(i, j int) bool {
    return pq.less(pq.items[i], pq.items[j])
}
func (pq *priorityQueueImpl<T>) Swap(i, j int) {
    pq.items[i], pq.items[j] = pq.items[j], pq.items[i]
}
func (pq *priorityQueueImpl<T>) Push(x any) {
    pq.items = append(pq.items, x.(T))
}
func (pq *priorityQueueImpl<T>) Pop() any {
    old := pq.items
    n := len(old)
    v := old[n-1]
    pq.items = old[:n-1]
    return v
}

type PriorityQueue<T any> struct {
    inner *priorityQueueImpl<T>
}

func NewPriorityQueue<T any>(less func(a, b T) bool) *PriorityQueue<T> {
    pq := &PriorityQueue<T>{
        inner: &priorityQueueImpl<T>{less: less},
    }
    heap.Init(pq.inner)
    return pq
}

func (pq *PriorityQueue<T>) Push(v T) {
    heap.Push(pq.inner, v)
}

func (pq *PriorityQueue<T>) Pop() T {
    return heap.Pop(pq.inner).(T)
}

这里选择传入 less 函数，而不是把 T 约束成 cmp.Ordered，是为了保留更大的自由度。任务按执行时间排、按优先级排、按重试次数排，只需要传入不同的比较函数。如果约束写成 [T cmp.Ordered]，要求使用者把任务类型改成可排序的包装结构体，反而多了一层不必要的侵入。

impl 内部那个 x.(T) 仍然是一次运行时断言，这点没有必要回避。它被隔离在泛型包装里，外部 API 的 Push 参数和 Pop 返回值在编译期已经确定，调用方不再需要知道堆里到底存了什么类型。

泛型方案和 interface{} 方案的取舍

维度	interface{} 容器	泛型容器
类型安全	编译期无检查，错误在运行时暴露	编译期确定类型，内部集中处理断言
代码复用	一份实现，多处断言	一份实现，类型各异也能复用
性能	存在装箱和逃逸开销，视使用方式而定	泛型特化后多数场景接近手写版本
可读性	需要查看使用处推断类型	类型自文档化，IDE 提示更友好
使用门槛	零门槛，容易写难维护	需要理解约束和类型参数边界