Skip to content

01-data-structures.md

Latest commit

 

History

History
301 lines (233 loc) · 5.87 KB

01-data-structures.md

File metadata and controls

301 lines (233 loc) · 5.87 KB

4.1 核心数据结构

📍 导航：返回目录 | 下一节：排序算法

Hash表与LRU缓存

LRU Cache实现（Go）

import "sync"

type Node struct {
    key, value int
    prev, next *Node
}

type LRUCache struct {
    mu       sync.RWMutex
    capacity int
    cache    map[int]*Node
    head     *Node
    tail     *Node
}

func NewLRUCache(capacity int) *LRUCache {
    lru := &LRUCache{
        capacity: capacity,
        cache:    make(map[int]*Node),
        head:     &Node{},
        tail:     &Node{},
    }
    lru.head.next = lru.tail
    lru.tail.prev = lru.head
    return lru
}

func (lru *LRUCache) Get(key int) int {
    lru.mu.Lock()
    defer lru.mu.Unlock()
    
    if node, ok := lru.cache[key]; ok {
        lru.moveToHead(node)
        return node.value
    }
    return -1
}

func (lru *LRUCache) Put(key, value int) {
    lru.mu.Lock()
    defer lru.mu.Unlock()
    
    if node, ok := lru.cache[key]; ok {
        node.value = value
        lru.moveToHead(node)
        return
    }
    
    node := &Node{key: key, value: value}
    lru.cache[key] = node
    lru.addToHead(node)
    
    if len(lru.cache) > lru.capacity {
        removed := lru.removeTail()
        delete(lru.cache, removed.key)
    }
}

func (lru *LRUCache) moveToHead(node *Node) {
    lru.removeNode(node)
    lru.addToHead(node)
}

func (lru *LRUCache) removeNode(node *Node) {
    node.prev.next = node.next
    node.next.prev = node.prev
}

func (lru *LRUCache) addToHead(node *Node) {
    node.prev = lru.head
    node.next = lru.head.next
    lru.head.next.prev = node
    lru.head.next = node
}

func (lru *LRUCache) removeTail() *Node {
    node := lru.tail.prev
    lru.removeNode(node)
    return node
}

时间复杂度：O(1)
空间复杂度：O(capacity)

跳表（Skip List）

原理

多层链表结构，通过"跳跃"加速查找：

Level 3: 1 ----------> 7 ----------> 19
Level 2: 1 ------> 4 -> 7 -> 10 --> 19
Level 1: 1 -> 2 -> 4 -> 7 -> 10 -> 13 -> 19
Level 0: 1 -> 2 -> 3 -> 4 -> 7 -> 10 -> 13 -> 16 -> 19

实现（Go）

import (
    "math/rand"
)

const MaxLevel = 16

type SkipListNode struct {
    key     int
    value   interface{}
    forward []*SkipListNode
}

type SkipList struct {
    header *SkipListNode
    level  int
}

func NewSkipList() *SkipList {
    return &SkipList{
        header: &SkipListNode{forward: make([]*SkipListNode, MaxLevel)},
        level:  1,
    }
}

func (sl *SkipList) randomLevel() int {
    level := 1
    for rand.Float32() < 0.5 && level < MaxLevel {
        level++
    }
    return level
}

func (sl *SkipList) Insert(key int, value interface{}) {
    update := make([]*SkipListNode, MaxLevel)
    current := sl.header
    
    // 查找插入位置
    for i := sl.level - 1; i >= 0; i-- {
        for current.forward[i] != nil && current.forward[i].key < key {
            current = current.forward[i]
        }
        update[i] = current
    }
    
    // 创建新节点
    level := sl.randomLevel()
    if level > sl.level {
        for i := sl.level; i < level; i++ {
            update[i] = sl.header
        }
        sl.level = level
    }
    
    newNode := &SkipListNode{
        key:     key,
        value:   value,
        forward: make([]*SkipListNode, level),
    }
    
    // 插入节点
    for i := 0; i < level; i++ {
        newNode.forward[i] = update[i].forward[i]
        update[i].forward[i] = newNode
    }
}

func (sl *SkipList) Search(key int) interface{} {
    current := sl.header
    
    for i := sl.level - 1; i >= 0; i-- {
        for current.forward[i] != nil && current.forward[i].key < key {
            current = current.forward[i]
        }
    }
    
    current = current.forward[0]
    if current != nil && current.key == key {
        return current.value
    }
    return nil
}

时间复杂度：平均O(log n)
应用：Redis的有序集合（Sorted Set）

B+树

特点

  • 所有数据存储在叶子节点
  • 叶子节点形成有序链表
  • 非叶子节点只存索引

应用场景

  • MySQL索引
  • 文件系统索引

优势：

  • 树高低（3-4层支持千万级数据）
  • 范围查询高效
  • 磁盘IO次数少

布隆过滤器

原理

通过多个哈希函数判断元素是否存在：

  • 不存在：一定不存在
  • 存在：可能存在（有误判率）

实现（Go）

import "hash/fnv"

type BloomFilter struct {
    bits   []bool
    size   int
    hashes int
}

func NewBloomFilter(size, hashes int) *BloomFilter {
    return &BloomFilter{
        bits:   make([]bool, size),
        size:   size,
        hashes: hashes,
    }
}

func (bf *BloomFilter) Add(item string) {
    for i := 0; i < bf.hashes; i++ {
        hash := bf.hash(item, i)
        bf.bits[hash%uint32(bf.size)] = true
    }
}

func (bf *BloomFilter) Contains(item string) bool {
    for i := 0; i < bf.hashes; i++ {
        hash := bf.hash(item, i)
        if !bf.bits[hash%uint32(bf.size)] {
            return false
        }
    }
    return true
}

func (bf *BloomFilter) hash(item string, seed int) uint32 {
    h := fnv.New32a()
    h.Write([]byte(item))
    h.Write([]byte{byte(seed)})
    return h.Sum32()
}

应用场景

  • 缓存穿透防护
  • 网页URL去重
  • 垃圾邮件过滤

本章小结

关键要点：

  • ✅ LRU Cache：O(1)读写，双向链表+哈希表
  • ✅ 跳表：多层链表，Redis有序集合的实现
  • ✅ B+树：MySQL索引，树高低，范围查询高效
  • ✅ 布隆过滤器：空间高效，允许误判

💡 思考题：

  1. 为什么MySQL使用B+树而不是B树？
  2. 跳表的层数如何确定？
  3. 如何降低布隆过滤器的误判率？

⏮️ 返回目录 | ⏭️ 下一节：排序算法