学习目标
读完本文，你应该能够：
- 理解 Go slice 的扩容机制（Go 1.18 前后差异），并手动实现动态数组
- 手写 LRU 缓存（map + 双向链表）和 LFU 缓存
- 实现带过期时间的 TTL 缓存，以及 LRU + TTL 双重淘汰缓存
- 实现跳表（Skip List）——Redis ZSet 底层数据结构
- 手写 Trie 树用于字符串前缀匹配
- 实现布隆过滤器和一致性哈希环
一、动态数组（模仿 Go Slice）
1.1 扩容规则（Go 1.18 前后）
面试官
Go slice 的扩容策略是什么？为什么会有变化？面试官
候选人
Go 1.18 之前：容量 ≤ 1024 时翻倍，超过后乘以 1.25。
Go 1.18 之后：容量 ≤ 256 时翻倍，超过后使用平滑增长公式。
变化原因：小容量时翻倍内存浪费明显（比如 cap=1 申请到 2，cap=128 申请到 256）。 平滑增长公式让扩容更渐进，减少内存碎片。
变化原因：小容量时翻倍内存浪费明显（比如 cap=1 申请到 2，cap=128 申请到 256）。 平滑增长公式让扩容更渐进，减少内存碎片。
1.2 代码实现
应用场景
在实际项目中，这个知识点经常应用于：
- 典型场景一：说明具体应用场景
- 典型场景二：说明另一个应用场景
- 面试要点：提醒面试中可能被问到的点
package main
import "fmt"
// DynamicArray 模仿 Go slice 的动态数组
type DynamicArray struct {
elem []interface{}
capacity int
size int
}
func NewDynamicArray() *DynamicArray {
return &DynamicArray{
elem: make([]interface{}, 0, 16),
capacity: 16,
}
}
// Append 追加元素，触发扩容
func (da *DynamicArray) Append(v interface{}) {
if da.size >= da.capacity {
da.grow()
}
da.elem[da.size] = v
da.size++
}
// grow 扩容逻辑（Go 1.18+ 风格）
func (da *DynamicArray) grow() {
newCap := da.capacity * 2
if da.capacity < 1024 {
// 小容量：直接翻倍
} else {
// 大容量：平滑增长
for newCap < da.size*2 {
newCap += newCap / 4
}
}
newElem := make([]interface{}, da.size, newCap)
copy(newElem, da.elem)
da.elem = newElem
da.capacity = newCap
}
func (da *DynamicArray) Get(i int) interface{} {
if i < 0 || i >= da.size {
panic("index out of range")
}
return da.elem[i]
}
func (da *DynamicArray) Len() int { return da.size }
复习提示：内存对齐：slice 扩容时
newCap 的计算要考虑内存对齐，实际源码中还有 roundupsize 函数处理对象大小对齐。二、单链表与双向链表
2.1 单链表
type ListNode struct {
Value int
Next *ListNode
}
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
cur :=
### 应用场景
在实际项目中，这个知识点经常应用于：
1. **典型场景一**：说明具体应用场景
2. **典型场景二**：说明另一个应用场景
3. **面试要点**：提醒面试中可能被问到的点
head
for cur != nil {
next := cur.Next
cur.Next = prev
prev = cur
cur = next
}
return prev
}
2.2 双向链表
type DoublyListNode struct {
Value int
Prev *DoublyListNode
Next *DoublyListNode
}
type DoublyLinkedList struct {
head *DoublyListNode
tail *DoublyListNode
size int
}
func (dll *DoublyLinkedList) AddFront(val int) {
node := &DoublyListNode{Value: val}
if dll.head == nil {
dll.head = node
dll.tail = node
} else {
node.Next = dll.head
dll.head.Prev = node
dll.head = node
}
dll.size++
}
func (dll *DoublyLinkedList) RemoveFro
### 应用场景
在实际项目中，这个知识点经常应用于：
1. **典型场景一**：说明具体应用场景
2. **典型场景二**：说明另一个应用场景
3. **面试要点**：提醒面试中可能被问到的点
nt() int {
if dll.head == nil {
panic("empty list")
}
val := dll.head.Value
dll.head = dll.head.Next
if dll.head == nil {
dll.tail = nil
} else {
dll.head.Prev = nil
}
dll.size--
return val
}
三、哈希表实现
3.1 链地址法
type hashEntry struct {
key string
value interface{}
next *hashEntry
}
type HashMap struct {
buckets []*hashEntry
size int
cap int
}
const defaultCapacity = 16
func NewHashMap() *HashMap {
return &HashMap{
buckets: make([]*hashEntry, defaultCapacity),
cap: defaultCapacity,
}
}
func (hm *HashMap) hash(key string) int {
h := uint32(0)
for i := 0; i < len(key); i++ {
h = h*31 + uint32(key[i])
}
return int(h % uint32(hm.cap))
}
func (hm *HashMap) Put(key string, value interface{}) {
idx := hm.hash(key)
entry := &hashEntry{key: key, value: value, next: hm.buckets[idx]}
hm.buckets[idx] = entry
hm.size++
// 负载因子超过 0.75 时扩容
if float64(hm.size)/float64(hm.cap) > 0.75 {
hm.resize()
}
}
func (hm *HashMap) Get(key string) (interface{}, bool) {
idx := hm.hash(key)
for e := hm.buckets[idx]; e != nil; e = e.next {
if e.key == key {
return e.value, true
}
}
return nil, false
}
func (hm *HashMap) resize() {
old := hm.buckets
hm.cap *= 2
hm.buckets = make([]*hashEntry, hm.cap)
hm.size = 0
for _, bucket := range old {
for e := bucket; e != nil; e = e.next {
hm.Put(e.key, e.value)
}
}
}
3.2 开放寻址法
type openAddrMap struct {
keys []string
values []interface{}
deleted []bool
size int
ca
### 应用场景
在实际项目中，这个知识点经常应用于：
1. **典型场景一**：说明具体应用场景
2. **典型场景二**：说明另一个应用场景
3. **面试要点**：提醒面试中可能被问到的点
p int
}
func (m *openAddrMap) Put(key string, value interface{}) {
idx := m.hash(key)
for {
if !m.deleted[idx] && m.keys[idx] == "" {
m.keys[idx] = key
m.values[idx] = value
m.size++
return
}
if m.keys[idx] == key {
m.values[idx] = value
return
}
idx = (idx + 1) % m.cap
}
}
四、LRU 缓存（高频！）
4.1 标准实现：map + 双向链表
type lruNode struct {
key string
val interface{}
prev *lruNode
next *lruNode
}
type LRUCache struct {
capacity int
cache map[string]*lruNode
head *lruNode // 虚拟头
tail *lruNode // 虚拟尾
}
func NewLRUCache(capacity int) *LRUCache {
head := &lruNode{}
tail := &lruNode{}
head.next = tail
tail.prev = head
return &LRUCache{
capacity: capacity,
cache: make(map[string]*lruNode),
head: head,
tail: tail,
}
}
func (c *LRUCache) Get(key string) interface{} {
if node, ok := c.cache[key]; ok {
c.moveToHead(node)
return node.val
}
return nil
}
func (c *LRUCache) Put(key string, value interface{}) {
if node, ok := c.cache[key]; ok {
node.val = value
c.moveToHead(node)
return
}
node := &lruNode{key: key, val: value}
c.cache[key] = node
c.addToHead(node)
if len(c.cache) > c.capacity {
removed := c.removeTail()
delete(c.cache, removed.key)
}
}
func (c *LRUCache) addToHead(node *lruNode) {
node.prev = c.head
node.next = c.head.next
c.head.next.prev = node
c.head.next = node
}
func (c *LRUCache) removeNode(node *lruNode) {
node.prev.next = node.next
node.next.prev = node.prev
}
func (c *LRUCache) moveToHead(node *lruNode) {
c.removeNode(node)
c.addToHead(node)
}
func (c *LRUCache) removeTail() *lruNode {
node := c.tail.prev
c.removeNode(node)
return node
}
LRU 缓存结构：哈希表 + 双向链表
看图要点：面试必考 LRU 为什么用哈希表 + 双向链表组合。哈希表提供 O(1) 按 key 定位节点；双向链表维护访问时序，head 之后是最近使用（MRU），tail.prev 是最久未用（LRU）。Get/Put 命中都把节点
moveToHead，超容量则删tail.prev并从 map 删除。伪头/伪尾哨兵省去了头尾空指针判断。追问：并发版用分段锁，每个 segment 各持一份 LRU。
4.2 并发安全版（分段锁）
type segment struct {
mu sync.RWMutex
cache map[string]*lruNode
capacity int
head *lruNode
tail *lruNode
}
type ConcurrentLRU struct {
segments []*segment
mask uint32
}
func NewConcurrentLRU(totalCap, numSegments int) *Concurrent
### 应用场景
在实际项目中，这个知识点经常应用于：
1. **典型场景一**：说明具体应用场景
2. **典型场景二**：说明另一个应用场景
3. **面试要点**：提醒面试中可能被问到的点
LRU {
cl := &ConcurrentLRU{
segments: make([]*segment, numSegments),
mask: uint32(numSegments - 1),
}
capPerSeg := totalCap / numSegments
for i := 0; i < numSegments; i++ {
cl.segments[i] = NewLRUCache(capPerSeg).toSegment()
}
return cl
}
func (cl *ConcurrentLRU) Get(key string) interface{} {
seg := cl.segments[hash(key)&cl.mask]
seg.mu.RLock()
defer seg.mu.RUnlock()
return seg.get(key)
}
五、LFU 缓存
5.1 核心思路
需要三个数据结构：
freqMap: 频率 → 双向链表（该频率下的所有节点）nodeMap: key → 节点minFreq: 当前最小频率
type freqNode struct {
key string
val interface{}
freq int
prev *freqNode
next *freqNode
}
type freqList struct {
size int
head *freqNode
tail *freqNode
}
func (fl *freqList) addNode(node *freqNode) {
node.prev = fl.head
node.next = fl.head.next
fl.head.next.prev = node
fl.head.next = node
fl.size++
}
type LFUCache struct {
capacity int
minFreq int
nodeMap map[string]*freqNode
freqMap map[int]*freqList
}
func (c *LFUCache) Get(key string) int {
if node, ok := c.nodeMap[key]; ok {
c.incrementFreq(node)
return node.val.(int)
}
return -1
}
func (c *LFUCache) Put(key string, value int) {
if c.capacity <= 0 {
return
}
if node, ok := c.nodeMap[key]; ok {
node.val = value
c.incrementFreq(node)
return
}
if len(c.nodeMap) >= c.capacity {
// 删除最少使用的
list := c.freqMap[c.minFreq]
toDelete := list.tail.prev
list.removeFromNode(toDelete)
delete(c.nodeMap, toDelete.key)
}
node := &freqNode{key: key, val: value, freq: 1}
c.nodeMap[key] = node
c.addToList(node)
c.minFreq = 1
}
func (c *LFUCache) incrementFreq(node *freqNode) {
oldFreq := node.freq
newFreq := oldFreq + 1
c.freqMap[oldFreq].removeFromNode(node)
if c.freqMap[oldFreq].size == 0 && c.minFreq == oldFreq {
c.minFreq = newFreq
}
node.freq = newFreq
c.addToList(node)
}
func (c *LFUCache) addToList(node *freqNode) {
list, ok := c.freqMap[node.freq]
if !ok {
list = &freqList{head: &freqNode{}, tail: &freqNode{}}
list.head.next = list.tail
list.tail.prev = list.head
c.freqMap[node.freq] = list
}
list.addNode(node)
}
六、TTL 缓存
type TTLItem struct {
value interface{}
expireAt time.Time
}
type TTLCache struct {
items map[string]TTLItem
mu sync.RWMutex
ticker *time.Ticker
stopCh chan struct{}
}
func NewTTLCache() *TTLCache {
tc := &TTLCache{
items: make(map[string]TTLItem),
ticker: time.NewTicker(1 * time.Second),
stopCh: make(chan struct{}),
}
go tc.cleanup()
return tc
}
func (tc *TTLCache) Set(key string, value interface{}, ttl time.Duration) {
tc.mu.Lock()
tc.items[key] = TTLItem{
value: value,
expireAt: time.Now().Add(ttl),
}
tc.mu.Unlock()
}
func (tc *TTLCache) Get(key string) (interface{}, bool) {
tc.mu.RLock()
item, ok := tc.items[key]
tc.mu.RUnlock()
if !ok || time.Now().After(item.expireAt) {
if ok {
tc.Delete(key)
}
return nil, false
}
return item.value, true
}
func (tc *TTLCache) cleanup() {
for {
select {
case <-tc.ticker.C:
tc.mu.Lock()
now := time.Now()
for k, v := range tc.items {
if now.After(v.expireAt) {
delete(tc.items, k)
}
}
tc.mu.Unlock()
case <-tc.stopCh:
return
}
}
}
七、LRU + TTL 双重淘汰
type LRTLTTCache struct {
lru *LRUCache
ttl *TTLCache
}
func (c *LRTLTTCache) Get(key string) interface{} {
if v, ok := c.ttl.Get(key); ok {
c.lru.Get(key) // 更新 LRU 顺序
return v
}
return nil
}
func (c *LRTLTTCache) Put(key string, value interface{}, ttl time.Duration) {
c.ttl.Set(key, value, ttl)
c.lru.Put(key, value)
}
八、跳表（Skip List）—— Redis ZSet 核心
8.1 原理
跳表通过多层链表实现 O(logN) 查找，类似二叉搜索树的替身。
const maxLevel = 16
type skipListNode struct {
value int
score float64
forward []*skipListNode
}
type SkipList struct {
head *skipListNode
level int
length int
rand *rand.Rand
}
func NewSkipList() *SkipList {
head := &skipListNode{forward: make([]*skipListNode, maxLevel)}
return &SkipList{head: head, level: 1, rand: rand.New(rand.NewSource(time.Now().UnixNano()))}
}
func (sl *SkipList) randomLevel() int {
level := 1
for level < maxLevel && sl.rand.Float64() < 0.5 {
level++
}
return level
}
func (sl *SkipList) Insert(score float64, value int) {
update := make([]*skipListNode, maxLevel)
current := sl.head
for i := sl.level - 1; i >= 0; i-- {
for current.forward[i] != nil && current.forward[i].score < score {
current = current.forward[i]
}
update[i] = current
}
newLevel := sl.randomLevel()
if newLevel > sl.level {
for i := sl.level; i < newLevel; i++ {
update[i] = sl.head
}
sl.level = newLevel
}
newNode := &skipListNode{
value: value,
score: score,
forward: make([]*skipListNode, newLevel),
}
for i := 0; i < newLevel; i++ {
newNode.forward[i] = update[i].forward[i]
update[i].forward[i] = newNode
}
sl.length++
}
九、Trie 树（前缀树）
type TrieNode struct {
children [26]*TrieNode
isEnd bool
word string
}
type Trie struct {
root *TrieNode
}
func NewTrie() *Trie {
return &Trie{root: &TrieNode{}}
}
func (t *Trie) Insert(word string) {
node := t.root
for _, ch := range word {
idx := ch - 'a'
if node.children[idx] == nil {
node.children[idx] = &TrieNode{}
}
node = node.children[idx]
}
node.isEnd = true
node.word = word
}
func (t *Trie) Search(word string) bool {
node := t.traverse(word)
return node != nil && node.isEnd
}
func (t *Trie) HasPrefix(prefix string) bool {
return t.traverse(prefix) != nil
}
func (t *Trie) traverse(prefix string) *TrieNode {
node := t.root
for _, ch := range prefix {
idx := ch - 'a'
if node.children[idx] == nil {
return nil
}
node = node.children[idx]
}
return node
}
十、布隆过滤器
type BloomFilter struct {
bitVector []bool
size int
hashFuncs []func([]byte) uint64
}
func NewBloomFilter(expectedItems int, falsePositiveRate float64) *BloomFilter {
bitSize := int(-float64(expectedItems)*math.Log(falsePositiveRate)/math.Pow(math.Ln2, 2))
hashCount := int(float64(bitSize)/float64(expectedItems)*math.Ln2)
filter := &BloomFilter{
bitVector: make([]bool, bitSize),
size: bitSize,
hashFuncs: make([]func([]byte) uint64, hashCount),
}
for i := 0; i < hashCount; i++ {
filter.hashFuncs[i] = makeHashFunc(i)
}
return filter
}
func (bf *BloomFilter) Add(item string) {
bytes := []byte(item)
for _, hash := range bf.hashFuncs {
h := hash(bytes)
bf.bitVector[h%uint64(bf.size)] = true
}
}
func (bf *BloomFilter) MightContain(item string) bool {
bytes := []byte(item)
for _, hash := range bf.hashFuncs {
h := hash(bytes)
if !bf.bitVector[h%uint64(bf.size)] {
return false
}
}
return true
}
func makeHashFunc(seed int) func([]byte) uint64 {
return func(data []byte) uint64 {
var h uint64 = uint64(seed)
for _, b := range data {
h = h*31 + uint64(b)
}
return h
}
}
十一、一致性哈希
type ConsistentHash struct {
keys []int // 虚拟节点位置
hashMap map[int]*node // 位置 → 节点
hashFunc func(string) int
n int // 每个真实节点的虚拟节点数
}
type node struct {
addr string
}
func NewConsistentHash(n int, hashFunc func(string) int) *ConsistentHash {
return &ConsistentHash{
hashMap: make(map[int]*node),
hashFunc: hashFunc,
n: n,
}
}
func (ch *ConsistentHash) Add(addr string) {
for i := 0; i < ch.n; i++ {
hash := ch.hashFunc(addr + strconv.Itoa(i))
ch.keys = append(ch.keys, hash)
ch.hashMap[hash] = &node{addr: addr}
}
sort.Ints(ch.keys)
}
func (ch *ConsistentHash) Get(key string) string {
hash := ch.hashFunc(key)
idx := sort.Search(len(ch.keys), func(i int) bool {
return ch.keys[i] >= hash
})
if idx == len(ch.keys) {
idx = 0
}
return ch.hashMap[ch.keys[idx]].addr
}
十二、环形缓冲区 RingBuffer
type RingBuffer struct {
data []interface{}
size int
cap int
readPos int
writePos int
count int
}
func NewRingBuffer(cap int) *RingBuffer {
return &RingBuffer{
data: make([]interface{}, cap),
cap: cap,
}
}
func (rb *RingBuffer) Put(item interface{}) bool {
if rb.count == rb.cap {
return false
}
rb.data[rb.writePos] = item
rb.writePos = (rb.writePos + 1) % rb.cap
rb.count++
return true
}
func (rb *RingBuffer) Get() (interface{}, bool) {
if rb.count == 0 {
return nil, false
}
item := rb.data[rb.readPos]
rb.data[rb.readPos] = nil // 帮助 GC
rb.readPos = (rb.readPos + 1) % rb.cap
rb.count--
return item, true
}
十三、自测题
面试官
LRU 和 LFU 的区别是什么？各适用于什么场景？
候选人
- LRU：最近使用的保留，不关心使用次数。适合"数据访问呈现局部性"的场景，如页面缓存。
- LFU：使用频率最高的保留，最近使用不重要。适合有"热点数据"的场景，如 CDN 缓存、热门商品缓存。
进阶：LRU-k 是两者的结合，记录最近 k 次访问。
面试官
跳表和平衡二叉树（如红黑树）相比有什么优劣？
候选人
跳表优点：
- 实现简单，不需要旋转
- 插入/删除 O(logN) 且稳定
- 范围查询友好
- 并发友好（局部加锁即可）
缺点：
- 空间开销大（每层都需要指针）
- 常数因子较大
Redis 选择跳表而不是红黑树，是因为跳表在范围操作上更高效。
十四、本章小结
复习提示：
- LRU 缓存是面试最高频题，务必能手写 map + 双向链表的完整实现
- Go slice 扩容在 1.18 后有重大变化，了解平滑增长公式是加分项
- 跳表是 Redis ZSet 的核心，理解其概率特性（每层 50% 概率向上）
- 布隆过滤器注意误判率计算，位数组大小 = -n·ln(p)/ln²(2)
- 下一篇将讲解设计模式与工程实践，包括 Rate Limiter、Circuit Breaker 等
参考
- 《Go 并发编程实战》第 5 章：数据结构
- Redis 源码：
src/t_zset.c（跳表实现） - Google Guava BloomFilter 论文