基础数据结构¶

学习目标¶

学完本章后，学习者应该能够：

理解数组、链表、栈、队列、哈希表的特点。
根据访问模式选择合适的数据结构。
使用 Go 的 slice 和 map 实现常见结构。
理解这些结构在后端业务中的应用场景。

数组与 slice¶

数组是一段连续内存，按下标访问元素很快。Go 中数组长度是类型的一部分，实际开发更常用 slice。

slice 是对底层数组的一个视图，包含指针、长度和容量。

nums := []int{1, 2, 3}
nums = append(nums, 4)

适合场景：

保持顺序。
按下标访问。
批量遍历。
数据量不大或主要追加。

不适合场景：

频繁在头部插入或删除。
需要按值高频查找。
需要保证并发安全。

链表¶

链表由节点组成，每个节点保存数据和指向下一个节点的指针。

链表优点：

插入和删除节点不需要整体搬移元素。
适合实现一些队列或 LRU 结构。

链表缺点：

不能 O(1) 按下标访问。
指针跳转对 CPU 缓存不友好。
Go 业务代码中直接使用链表的场景不多。

Go 标准库提供了 container/list，常用于配合 map 实现 LRU。

栈¶

栈是后进先出结构：Last In First Out。

常见操作：

push：入栈。
pop：出栈。
peek：查看栈顶。

Go 中可以用 slice 实现：

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

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

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

应用场景：

函数调用栈。
表达式解析。
括号匹配。
DFS。
撤销操作。

队列¶

队列是先进先出结构：First In First Out。

应用场景：

任务队列。
BFS。
请求排队。
生产者消费者模型。

简单实现：

type Queue[T any] struct {
    items []T
}

func (q *Queue[T]) Push(v T) {
    q.items = append(q.items, v)
}

func (q *Queue[T]) Pop() (T, bool) {
    var zero T
    if len(q.items) == 0 {
        return zero, false
    }
    v := q.items[0]
    q.items[0] = zero
    q.items = q.items[1:]
    return v, true
}

注意：长期从 slice 头部切片可能导致底层数组仍被引用，影响内存释放。生产级队列通常会使用环形缓冲区、链表或成熟队列组件。

哈希表¶

哈希表通过哈希函数把 key 映射到桶，通常能提供接近 O(1) 的插入、删除和查询。

Go 中 map 就是哈希表：

users := map[int64]string{
    1001: "alice",
    1002: "bob",
}

name, ok := users[1001]

适合场景：

按 key 快速查找。
去重。
计数。
建立索引。
集合判断。

常见写法：

set := make(map[string]struct{})
set["read"] = struct{}{}

if _, ok := set["read"]; ok {
    // exists
}

后端场景中的选择¶

场景	推荐结构
按顺序返回列表	slice
按 ID 快速查找	map
去重	map / set
先进先出任务	queue
最近使用记录	map + linked list
括号匹配、撤销	stack
层序遍历	queue

Go 后端实际应用例子¶

例子一：用 map 做权限集合判断¶

接口鉴权时，常需要判断用户是否拥有某个权限。用 slice 每次遍历是 O(n)，用 map 可以让判断更直接：

func BuildPermissionSet(perms []string) map[string]struct{} {
    set := make(map[string]struct{}, len(perms))
    for _, perm := range perms {
        set[perm] = struct{}{}
    }
    return set
}

func Can(set map[string]struct{}, perm string) bool {
    _, ok := set[perm]
    return ok
}

在 RBAC、API Key 权限、菜单权限、数据权限中，这种写法非常常见。

例子二：用 channel 做进程内任务队列¶

本地内存队列可以用于演示 worker pool。生产环境通常会换成 Redis、Kafka、NATS 等可靠队列。

type Job struct {
    ID   string
    Name string
}

func worker(jobs <-chan Job) {
    for job := range jobs {
        // process job
        _ = job
    }
}

func StartWorkers(n int, jobs <-chan Job) {
    for i := 0; i < n; i++ {
        go worker(jobs)
    }
}

这里 channel 扮演并发安全队列的角色。它适合进程内任务分发，但不适合需要持久化和跨进程消费的任务。

常见误区¶

误区一：slice 可以替代所有结构。

slice 很常用，但按值查找是 O(n)，高频查找时应该考虑 map。

误区二：map 是并发安全的。

Go 原生 map 并发读写不安全，需要加锁、使用 sync.Map，或通过单 goroutine 管理状态。

误区三：队列用 items = items[1:] 永远没问题。

如果底层数组仍被引用，大对象可能无法及时释放。高频队列应使用更合适的数据结构。

实战任务¶

实现一个简单的字符串集合：

要求：

支持 Add。
支持 Remove。
支持 Contains。
支持 Len。
使用 map[string]struct{} 实现。

思考：

为什么 value 使用 struct{} 而不是 bool？
这个结构是否并发安全？
如果需要并发安全，应该怎么改？

参考实现

基础版本：

type StringSet struct {
    items map[string]struct{}
}

func NewStringSet() *StringSet {
    return &StringSet{items: make(map[string]struct{})}
}

func (s *StringSet) Add(v string) {
    s.items[v] = struct{}{}
}

func (s *StringSet) Remove(v string) {
    delete(s.items, v)
}

func (s *StringSet) Contains(v string) bool {
    _, ok := s.items[v]
    return ok
}

func (s *StringSet) Len() int {
    return len(s.items)
}

struct{} 不占额外空间，适合表达“只关心 key 是否存在”。这个结构不是并发安全的。并发场景可以加 sync.RWMutex：

type SafeStringSet struct {
    mu    sync.RWMutex
    items map[string]struct{}
}

读操作加 RLock，写操作加 Lock。如果读写并发很复杂，也可以考虑把状态集中到单 goroutine 或使用 sync.Map。

面试题¶

1. slice 和数组有什么区别？¶

参考答案

数组长度固定，长度是类型的一部分，例如 [3]int 和 [4]int 是不同类型。slice 是对底层数组的动态视图，包含指针、长度和容量，实际开发中更常用。

slice 可以通过 append 扩容，但扩容时可能分配新的底层数组并复制元素。理解这一点有助于避免意外共享底层数组和不必要的内存分配。

2. 什么场景适合使用 map？¶

参考答案

当需要按 key 快速查找、去重、计数、建立索引或做集合判断时，map 很合适。它通常能提供接近 O(1) 的查询和插入。

但 map 不保证遍历顺序，也不是并发读写安全的。如果需要有序结果，要额外排序；如果有并发读写，要加锁或使用其他并发安全方案。

3. 栈和队列的区别是什么？¶

参考答案

栈是后进先出，适合括号匹配、表达式解析、DFS、撤销等场景。队列是先进先出，适合任务排队、BFS、生产者消费者等场景。

面试回答时最好不仅说定义，还能举出实际应用。比如 Webhook 投递任务可以进入队列，递归 DFS 可以改成显式栈。

4. Go map 并发读写会有什么问题？¶

参考答案

Go 原生 map 不支持并发读写。如果一个 goroutine 写 map，另一个 goroutine 同时读或写，可能触发运行时错误，也可能产生数据竞争。

解决方式包括使用 sync.RWMutex 保护 map、使用 sync.Map，或者通过 channel 把所有 map 操作收敛到一个 goroutine 中。

5. 为什么队列不总是直接用 `slice[1:]` 实现？¶

参考答案

slice[1:] 很简单，但底层数组可能仍被引用，导致已经弹出的元素不能及时释放。如果元素很大或队列长期运行，可能造成内存占用异常。

高频队列可以使用环形缓冲区、链表，或者成熟的队列组件。简单业务中可以用 slice，但要理解它的边界。

基础数据结构¶

学习目标¶

数组与 slice¶

链表¶

栈¶

队列¶

哈希表¶

后端场景中的选择¶

Go 后端实际应用例子¶

例子一：用 map 做权限集合判断¶

例子二：用 channel 做进程内任务队列¶

常见误区¶

实战任务¶

面试题¶

1. slice 和数组有什么区别？¶

2. 什么场景适合使用 map？¶

3. 栈和队列的区别是什么？¶

4. Go map 并发读写会有什么问题？¶

5. 为什么队列不总是直接用 slice[1:] 实现？¶

5. 为什么队列不总是直接用 `slice[1:]` 实现？¶