标签：切片 Slice string bucket Golang 哈希原理数据结构 channel

chan

1.chan数据结构

src/runtime/chan.go:hchan定义了channel的数据结构：

type hchan struct {
    qcount   uint           // 当前队列中剩余元素个数
    dataqsiz uint           // 环形队列长度，即可以存放的元素个数
    buf      unsafe.Pointer // 环形队列指针
    elemsize uint16         // 每个元素的大小
    closed   uint32            // 标识关闭状态
    elemtype *_type         // 元素类型
    sendx    uint           // 队列下标，指示元素写入时存放到队列中的位置
    recvx    uint           // 队列下标，指示元素从队列的该位置读出
    recvq    waitq          // 等待读消息的goroutine队列
    sendq    waitq          // 等待写消息的goroutine队列
    lock mutex              // 互斥锁，chan不允许并发读写
}

1.1 环形队列

chan内部实现了一个环形队列作为其缓冲区，队列的长度是创建chan时指定的。

下图展示了一个可缓存6个元素的channel示意图：

dataqsiz指示了队列长度为6，即可缓存6个元素；
buf指向队列的内存，队列中还剩余两个元素；
qcount表示队列中还有两个元素；
sendx指示后续写入的数据存储的位置，取值[0, 6)；
recvx指示从该位置读取数据, 取值[0, 6)；

1.2 等待队列

从channel读数据，如果channel缓冲区为空或者没有缓冲区，当前goroutine会被阻塞。向channel写数据，如果channel缓冲区已满或者没有缓冲区，当前goroutine会被阻塞。

被阻塞的goroutine将会挂在channel的等待队列中：

因读阻塞的goroutine会被向channel写入数据的goroutine唤醒；
因写阻塞的goroutine会被从channel读数据的goroutine唤醒；

下图展示了一个没有缓冲区的channel，有几个goroutine阻塞等待读数据：

注意，一般情况下recvq和sendq至少有一个为空。只有一个例外，那就是同一个goroutine使用select语句向channel一边写数据，一边读数据。

1.3 类型信息

一个channel只能传递一种类型的值，类型信息存储在hchan数据结构中。

elemtype代表类型，用于数据传递过程中的赋值；
elemsize代表类型大小，用于在buf中定位元素位置。

1.4 锁

一个channel同时仅允许被一个goroutine读写

2.channel读写

2.1 创建channel

创建channel的过程实际上是初始化hchan结构。其中类型信息和缓冲区长度由make语句传入，buf的大小则与元素大小和缓冲区长度共同决定。

创建channel的伪代码如下所示：

func makechan(t *chantype, size int) *hchan {
    var c *hchan
    c = new(hchan)
    c.buf = malloc(元素类型大小*size)
    c.elemsize = 元素类型大小
    c.elemtype = 元素类型
    c.dataqsiz = size

    return c
}

2.2 向channel写数据

向一个channel中写数据简单过程如下：

如果等待接收队列recvq不为空，说明缓冲区中没有数据或者没有缓冲区，此时直接从recvq取出G,并把数据写入，最后把该G唤醒，结束发送过程；
如果缓冲区中有空余位置，将数据写入缓冲区，结束发送过程；
如果缓冲区中没有空余位置，将待发送数据写入G，将当前G加入sendq，进入睡眠，等待被读goroutine唤醒；

简单流程图如下：

2.3 从channel读数据

从一个channel读数据简单过程如下：

如果等待发送队列sendq不为空，且没有缓冲区，直接从sendq中取出G，把G中数据读出，最后把G唤醒，结束读取过程；
如果等待发送队列sendq不为空，此时说明缓冲区已满，从缓冲区中首部读出数据，把G中数据写入缓冲区尾部，把G唤醒，结束读取过程；
如果缓冲区中有数据，则从缓冲区取出数据，结束读取过程；
将当前goroutine加入recvq，进入睡眠，等待被写goroutine唤醒；

简单流程图如下：

2.4 关闭channel

关闭channel时会把recvq中的G全部唤醒，本该写入G的数据位置为nil。把sendq中的G全部唤醒，但这些G会panic。

除此之外，panic出现的常见场景还有：

关闭值为nil的channel
关闭已经被关闭的channel
向已经关闭的channel写数据

3.常见用法

3.1 单向channel

我们知道channel可以通过参数传递，所谓单向channel只是对channel的一种使用限制，这跟C语言使用const修饰函数参数为只读是一个道理。

func readChan(chanName <-chan int)：通过形参限定函数内部只能从channel中读取数据
func writeChan(chanName chan<- int)：通过形参限定函数内部只能向channel中写入数据

func readChan(chanName <-chan int) {
    <- chanName
}

func writeChan(chanName chan<- int) {
    chanName <- 1
}

func main() {
    var mychan = make(chan int, 10)

    writeChan(mychan)
    readChan(mychan)
}

mychan是个正常的channel，而readChan()参数限制了传入的channel只能用来读，writeChan()参数限制了传入的channel只能用来写。

3.2 select

通过select可以监控两个channel，任意一个可读时就从其中读出数据。

select的case语句读channel不会阻塞，尽管channel中没有数据。这是由于case语句编译后调用读channel时会明确传入不阻塞的参数，此时读不到数据时不会将当前goroutine加入到等待队列，而是直接返回。

3.3 range

通过range可以持续从channel中读出数据，好像在遍历一个数组一样，当channel中没有数据时会阻塞当前goroutine，与读channel时阻塞处理机制一样。

func chanRange(chanName chan int) {
    for e := range chanName {
        fmt.Printf("Get element from chan: %d\n", e)
    }
}

注意：如果向此channel写数据的goroutine退出时，系统检测到这种情况后会panic，否则range将会永久阻塞。

slice

1.slice实现原理

1.1 slice数据结构

源码包中src/runtime/slice.go:slice定义了Slice的数据结构：

type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}

从数据结构看Slice很清晰, array指针指向底层数组，len表示切片长度，cap表示底层数组容量。

1.2 使用make创建slice

使用make来创建Slice时，可以同时指定长度和容量，创建时底层会分配一个数组，数组的长度即容量。

1.3 使用数组创建slice

使用数组来创建Slice时，Slice将与原数组共用一部分内存，所以数组和切片操作可能作用于同一块内存

1.4 slice扩容

扩容操作只关心容量，会把原Slice数据拷贝到新Slice，追加数据由append在扩容结束后完成。上图可见，扩容后新的Slice长度仍然是5，但容量由5提升到了10，原Slice的数据也都拷贝到了新Slice指向的数组中。

扩容容量的选择遵循以下规则：

如果原Slice容量小于1024，则新Slice容量将扩大为原来的2倍；
如果原Slice容量大于等于1024，则新Slice容量将扩大为原来的1.25倍；

使用append()向Slice添加一个元素的实现步骤如下：

假如Slice容量够用，则将新元素追加进去，Slice.len++，返回原Slice
原Slice容量不够，则将Slice先扩容，扩容后得到新Slice
将新元素追加进新Slice，Slice.len++，返回新的Slice。

1.5 slice copy

使用copy()内置函数拷贝两个切片时，会将源切片的数据逐个拷贝到目的切片指向的数组中，拷贝数量取两个切片长度的最小值。

例如长度为10的切片拷贝到长度为5的切片时，将会拷贝5个元素。

也就是说，copy过程中不会发生扩容。

1.6 特殊切片

根据数组或切片生成新的切片一般使用slice := array[start:end]方式，这种新生成的切片并没有指定切片的容量，实际上新切片的容量是从start开始直至array的结束。

比如下面两个切片，长度和容量都是一致的，使用共同的内存地址：

sliceA := make([]int, 5, 10)
sliceB := sliceA[0:5]

根据数组或切片生成切片还有另一种写法，即切片同时也指定容量，即slice[start

标签：切片,Slice,string,bucket,Golang,哈希,原理,数据结构,channel
From： https://www.cnblogs.com/twh233/p/17865481.html

Golang-常见数据结构实现原理