int bool float string array slice map chan
主要是 map 和 chan

int

int(有符号)和uint(无符号)的大小与操作系统相关，在32位操作系统中大小为32位(4字节)，64位操作系统中大小为64位(8字节)

int      8 字节
int8     1 字节
int16    2 字节
int32    4 字节
int64    8 字节

它们是不同的类型(type)

float

float32，即单精度，32位(4字节)，其中1位用来符号，8位用来指数，剩下的23位表示尾数，精确到小数点后7位 float64，即双精度，64位(8字节)，其中1位用来符号，11位用来指数，剩下的52位表示尾数，精确到小数点后15位

bool

只有2种：true和false bool值并不会隐式转换为数字值0或1，反之亦然。必须使用一个显式的if语句辅助转换：

i := 0
if b {
    i = 1
}

string

字符串可以包含任意的数据，包括byte值0，但是通常是用来包含人类可读的文本。文本字符串通常被解释为采用UTF8编码的Unicode码点（rune）序列。 一个字符串是一个不可改变的字节序列，实际上就是占用了一片连续的内存空间，所以能理解为一个字符数组 在go的源码中可以找到string的数据结构

type stringStruct struct {
    array unsafe.Pointer   // 指向一个 [length]byte 的数组
    length int             // 长度
}

其成员有2个，一个指向数组的指针，一个是所指数组的长度 示例图：go语言圣经3.5.1

array

cmd/compile/internal/types2.Array go 源码中数组的结构

type Array struct {
    len  int64 // 数组长度，即元素个数
    elem Type  // 元素类型
}

数组占用一片连续的内存空间

slice

src/runtime/slice.go go 源码中slice的结构

type slice struct {
    array unsafe.Pointer  // 指向数组的指针
    len   int             // 切片长度
    cap   int             // 切片容量
}

其成员有3个，一个指向数组的指针，一个是切片的长度，还有一个是切片的容量

切片的长度就是切片所包含的元素个数。 切片的容量是从它的第一个元素开始数，到其底层数组元素末尾的个数。

map

go 源码中map的结构 src/runtime/map.go

type hmap struct {
    
    count     int // map当前元素个数
    flags     uint8 // 读、写、扩容、迭代等标记，用于记录map当前状态
    B         uint8  // 用于计算桶大小， bucketSize = 1 << B ;log_2 of # of buckets (can hold up to loadFactor * 2^B items)
    noverflow uint16 // 溢出桶个数，当溢出桶个数过多时，这个值是一个近似值  approximate number of overflow buckets; see incrnoverflow for details
    hash0     uint32 // hash seed,计算key哈希值的随机值，保证一个key在不同map中存放的位置是随机的

    buckets    unsafe.Pointer // 当前哈希桶首地址   array of 2^B Buckets. may be nil if count==0.
    oldbuckets unsafe.Pointer // 旧哈希桶首地址  previous bucket array of half the size, non-nil only when growing
    nevacuate  uintptr        // 已迁移哈希桶个数   progress counter for evacuation (buckets less than this have been evacuated)

    extra *mapextra // 扩展字段，不一定每个map都需要    optional fields
}

map是使用hash表(哈希表/散列表)来实现的,一个hash表里可以有多个hash节点，也叫bucket(桶/哈希桶),而每个bucket就保存了map中的一个或一组键值对。
https://blog.csdn.net/fengshenyun/article/details/100582679

bucket的数据结构

type bmap struct {
    tophash [8]uint8 //存储哈希值的高8位,哈希值相同的键（准确的说是哈希值低位相同的键）存入当前bucket时会将哈希值的高位存储在该数组中，以方便后续匹配。
    data    byte[1]  //key value数据:key/key/key/.../value/value/value...,如此存放是为了节省字节对齐带来的空间浪费
    overflow *bmap   //溢出bucket的地址,指向的是下一个bucket，据此将所有冲突的键连接起来。
}

https://www.cnblogs.com/failymao/p/14902607.html
https://www.cnblogs.com/dawnlight/p/15552513.html

map数据结构最终梳理

• hmap是数组(切片)，组成元素是bucket(bmap,以便区分，这里后面都用bucket替代bmap)；bucket是链表，指针指向下一个扩充的bucket。
• map存储的是key/value对(k/v对、键值对)
• 当key传进来时，会经过一个hash函数运算得到一个唯一的hash值，在go中会将这个hash值分为高位和低位
• 如hash值：1314131425002500，高8位为13141314，低8位为25002500
• 低位用于寻找key属于hmap的哪个bucket，高位用于寻找bucket中的哪个key
• 如果key计算出的hash值低位相同，那么这些key存入相同的bucket中，在bucket中会存储它们的高位，用于存入的key的快速预览
• bucket是以key/key/key/.../value/value/value...的方式存储k/v对的，这是为了节省字节对齐带来的空间浪费
• 每个bucket只能存储8个k/v对，超过8个则会扩充一个新的bucket存放溢出的k/v对，然后指针指向新的bucket，以此类推，形成一个链表

负载因子与渐进式扩容

负载因子 = key数量/bucket数量 (len(map)/2^B)

• 因子过小，说明空间利用率低:key少bucket多，说明map的bucket数组个数多，一个bucket中存放的key少
• 因子过大，说明冲突严重，存取效率低:key多bucket少，说明map的bucket数组个数少，一个bucket中存放的key多，溢出bucket严重

每个哈希表的实现对负载因子容忍程度不同，go的阈值为6.5，即平均每个bucket存放6.5个k/v对；而redis的阈值为1，因为redis里每个bucket只存放一个k/v对

扩容条件

• 1.负载因子 > 6.5时，也即平均每个bucket存储的键值对达到6.5个。
• 2.overflow(溢出bucket)数量 > 2^15时，也即overflow数量超过32768时。

增量扩容
因子过大，则会新建一个bucket数组将hmap,大小为原有bucket数组的两倍，并将原有bucket数组的数据渐进式地迁移到新bucket数组，即每次访问map时都会触发一次搬迁，每次搬迁2个键值对。

hmap的buckets oldbuckets nevacuate 字段就是用来干这个的

等量扩容
buckets数量不变，只是重新做一遍类似增量扩容的搬迁动作，把松散的键值对重新排列一次，以使bucket的使用率更高，进而保证更快的存取。例如过于频繁的对k/v进行增删操作，而这些k/v集中在某个bucket里，则会导致溢出bucket严重，影响存取效率

插入与查找

插入

• 根据key值算出哈希值
• 取哈希值低位与hmap.B取模确定bucket位置
• 查找该key是否已经存在，如果存在则直接更新值
• 如果没找到将key，将key插入

查找

• 根据key值算出哈希值
• 取哈希值低位与hmap.B取模确定bucket位置
• 取哈希值高位在tophash数组中查询
• 如果tophashi中存储值也哈希值相等，则去找到该bucket中的key值进行比较
• 当前bucket没有找到，则继续从下个overflow的bucket中查找。
• 如果当前处于搬迁过程，则优先从oldbuckets查找 注：如果查找不到，也不会返回空值，而是返回相应类型的0值。

chan

src/runtime/chan.go

type hchan struct {
    qcount   uint           // 当前队列中剩余元素个数          total data in the queue
    dataqsiz uint           // 环形队列长度，即可以存放的元素个数      size of the circular queue
    buf      unsafe.Pointer // 环形队列指针                points to an array of dataqsiz elements
    elemsize uint16     // 每个元素的大小
    closed   uint32     // 标识关闭状态
    elemtype *_type // 元素类型                        element type
    sendx    uint   // 队列下标，指示元素写入时存放到队列中的位置       send index
    recvx    uint   //队列下标，指示元素从队列的该位置读出          receive index
    recvq    waitq  //等待读消息的goroutine队列            list of recv waiters
    sendq    waitq  // 等待写消息的goroutine队列               list of send waiters
    lock mutex  //互斥锁，chan不允许并发读写
    // lock protects all fields in hchan, as well as several
    // fields in sudogs blocked on this channel.
    //
    // Do not change another G's status while holding this lock
    // (in particular, do not ready a G), as this can deadlock
    // with stack shrinking.
    
}

chan最核心的部分由一个环形队列和2个waitq组成，环形队列用于存放数据（带缓冲的情况下），waitq用于实现阻塞和恢复goroutine。

type waitq struct {
    first *sudog
    last  *sudog
}

type sudog struct {
    g *g

    next *sudog
    prev *sudog
    elem unsafe.Pointer // data element (may point to stack)

    acquiretime int64
    releasetime int64
    ticket      uint32

    // isSelect indicates g is participating in a select, so
    // g.selectDone must be CAS'd to win the wake-up race.
    isSelect bool

    // success indicates whether communication over channel c
    // succeeded. It is true if the goroutine was awoken because a
    // value was delivered over channel c, and false if awoken
    // because c was closed.
    success bool

    parent   *sudog // semaRoot binary tree
    waitlink *sudog // g.waiting list or semaRoot
    waittail *sudog // semaRoot
    c        *hchan // channel
}

https://www.cnblogs.com/failymao/p/14891813.htmlhttps://i6448038.github.io/2019/04/11/go-channel/https://cloud.tencent.com/developer/article/1750350

最终梳理

channel在源码是hchan结构体，核心为1个循环队列、以及2个 分别等待读和写的 goroutine 等待队列(双向链表)

循环队列

qcount   uint             // 当前队列中剩余元素
dataqsiz uint             // 队列长度，即可以存放的元素个数
buf      unsafe.Pointer   // 队列
sendx    uint         // 队列下标，指示元素写入时存放到队列中的位置 
recvx    uint         // 队列下标，指示元素从队列的该位置读出
lock     mutex        // 互斥锁

在创建channel时,在内存中实例化了一个hchan的结构体，并返回一个ch指针。channel 是一个指针。

ch := make(chan int, 3)

在讨论之前先统一一下概念：
对于发送给channel的消息，channel是接收者，对channel来说是写操作；对于channel发送出去的消息，channel是发送者，对channel来说是读操作

sendx: 等待发送。需要发送给channel的元素的索引位置(index)，即元素写入时存放到队列中的位置。

recvx: 等待接收。需要从channel接收的元素的索引位置(index)，即从队列的该位置读出元素。

给channel发(send)数据 (ch<-xx)

// 1.创建一个channel
// 在内存中实例化了一个hchan的结构体，并返回一个ch指针。
// ch是指针，ch用使用队列 buf 来缓存数据
// 队列长度为dataqsiz为3，当前元素 qcount 为 0
// sendx和recvx均为 0
ch := make(chan int, 3)
// 2.将 一个元素写入 buf，
// 首先先加锁
// 将元素拷贝，传递给channel
// 索引 0 位置写入了新的元素，sendx变为1，即下一个元素需要写入索引1的位置；recvx不变，即下一个读操作从索引0的位置读取
// 队列长度为dataqsiz为3，当前元素 qcount 为 1
// 释放锁
ch<-1
ch<-1
ch<-1
// 队列缓存已满，再次写入会发生堵塞，这点我们后面再讲
// 每次写入sendx+1，写入了3个元素，因为是循环队列 sendx又变为0；因为没有读取，recvx一直不变还是0

// 3.从buf读取一个元素,和写元素类似
// 首先先加锁
// channel将元素传递给接收者
// 从索引 0 位置读出元素，recvx变为1，即需要读取的下一个元素位置为索引1；sendx为0，即下一个元素需要写入索引0的位置
// 队列长度为dataqsiz为3，当前元素 qcount 为 2
// 释放锁
<-ch
<-ch
<-ch

这个应该很有用，但太长了不想看 https://blog.csdn.net/kesenzhang/article/details/104488727

双向链表

主要实现了堵塞

recvq    waitq  //等待读消息的goroutine队列 
sendq    waitq  // 等待写消息的goroutine队列  

这部分与GPM调度有关，等我写好内存模型和调度后再继续写，to be continent ...