跳转至

源码分析

  • 分类于 源码分析
  • 需要 10 分钟阅读时间

Golang源码分析系列之Map底层实现

映射也被称为哈希表(hash table)、字典。它是一种由key-value组成的抽象数据结构。大多数情况下，它都能在O(1)的时间复杂度下实现增删改查功能。若在极端情况下出现所有key都发生哈希碰撞时则退回成链表形式，此时复杂度为O(N)。

映射底层一般都是由数组组成，该数组每个元素称为桶，它使用hash函数将key分配到不同桶中，若出现碰撞冲突时候，则采用链地址法（也称为拉链法）或者开放寻址法解决冲突。下图就是一个由姓名-号码构成的哈希表的结构图：

Go语言中映射中key若出现冲突碰撞时候，则采用链地址法解决，Go语言中映射具有以下特点：

  • 引用类型变量
  • 读写并发不安全
  • 遍历结果是随机的

数据结构

Go语言中映射的数据结构是runtime.hmap(runtime/map.go):

// A header for a Go map.
type hmap struct {
    count     int //  元素个数，用于len函数返回map元素数量
    flags     uint8 // 标志位，标志当前map正在写等状态
    B         uint8  // buckets个数的对数，即桶数量 = 2 ^ B
    noverflow uint16 // overflow桶数量的近似值，overflow桶即溢出桶，即链表法中存在链表上的桶的个数
    hash0     uint32 // 随机数种子，用于计算key的哈希值

    buckets    unsafe.Pointer // 指向buckets数组，如果元素个数为0时，该值为nil
    oldbuckets unsafe.Pointer // 扩容时指向旧的buckets
    nevacuate  uintptr        // 用于指示迁移进度，小于此值的桶已经迁移完成

    extra *mapextra // 额外记录overflow桶信息
}
  • 分类于 源码分析
  • 需要 5 分钟阅读时间

Golang源码分析系列之atomic底层实现

atomic概述

atomic是Go内置原子操作包。下面是官方说明：

Package atomic provides low-level atomic memory primitives useful for implementing synchronization algorithms. atomic包提供了用于实现同步机制的底层原子内存原语。

These functions require great care to be used correctly. Except for special, low-level applications, synchronization is better done with channels or the facilities of the sync package. Share memory by communicating; don't communicate by sharing memory. 使用这些功能需要非常小心。除了特殊的底层应用程序外，最好使用通道或sync包来进行同步。通过通信来共享内存；不要通过共享内存来通信。

  • 分类于 源码分析
  • 需要 4 分钟阅读时间

Golang源码分析系列之sync.Map底层实现

Golang中sync/map提供了并发读写map功能。这里面分析的源码基于go1.14.13版本。

sync.Map的结构

type Map struct {
    mu Mutex // 排他锁，用于对dirty map操作时候加锁处理

    read atomic.Value // read map

    // dirty map。新增key时候，只写入dirty map中，需要使用mu
    dirty map[interface{}]*entry

    // 用来记录从read map中读取key时miss的次数
    misses int
}
  • 分类于 源码分析
  • 需要 6 分钟阅读时间

Golang源码分析系列之Channel底层实现

Golang中Channel是goroutine间重要通信的方式，是并发安全的，通道内的数据First In First Out，我们可以把通道想象成队列。这里面分析的源码基于go1.13版本。

channel数据结构

Channel底层数据结构是一个结构体。

type hchan struct {
    qcount   uint // 队列中元素个数
    dataqsiz uint // 循环队列的大小
    buf      unsafe.Pointer // 指向循环队列
    elemsize uint16 // 通道里面的元素大小
    closed   uint32 // 通道关闭的标志
    elemtype *_type // 通道元素的类型
    sendx    uint   // 待发送的索引，即循环队列中的队尾指针front
    recvx    uint   // 待读取的索引，即循环队列中的队头指针rear
    recvq    waitq  // 接收等待队列
    sendq    waitq  // 发送等待队列
    lock mutex // 互斥锁
}
  • 分类于 源码分析
  • 需要 5 分钟阅读时间

Golang源码分析系列之官方Context包

Context简介

Context是由Golang官方开发的并发控制包，一方面可以用于当请求超时或者取消时候，相关的goroutine马上退出释放资源，另一方面Context本身含义就是上下文，其可以在多个goroutine或者多个处理函数之间传递共享的信息。

创建一个新的context，必须基于一个父context，新的context又可以作为其他context的父context。所有context在一起构造成一个context树。

context tree