05-数组和切片

数组的长度必须在声明时给定,且不可变,它是数组类型的一部分

切片的类型字面量中,只有元素类型,长度随着元素数量增长而增长,但不会减小

切片可以看成是对数组的一层简单封装,在每个切片的底层数据结构中,一定会包含一个数组。

  • 数组:是切片的底层数组
  • 切片:是对数组的某个连续片段的引用,切片的容量代表了其可见底层数组的长度,切片的底层数组长度不可变

0.1. 引用类型与值类型

引用类型:

  1. 切片类型(切片是对数组某个连续片段的引用)【相对于slice底层的数组而言,其实slice是一个结构体类型(也就是值类型)】
  2. 字典类型
  3. 通道类型
  4. 函数类型

值类型:

  1. 基础数据类型
  2. 结构体类型
  3. 数组类型
  4. 切片类型【相对于slice底层的数组而言,其实slice是一个结构体类型(也就是值类型)】

Go语言中不存在“传值或传引用”的问题,在Go语言中只要看被传递的值的类型,如果被传递的值是引用类型,那就是“传引用”,如果被传递的值是值类型,那就是“传值”。从传递成本的角度,引用类型的值比值类型的值成本低很多。

// 切片类型
type slice struct {
 array unsafe.Pointer
 len   int
 cap   int
}

// 直接通过索引操作时,是对切片底层的数组进行操作,通过array指针实现
// 切片作为参数时传递的是切片的副本

0.2. 内建函数

  • len():得到数组或切片的长度
  • cap():得到数组或切片的容量
  • make(): 创建切片、字典、通道等
  • append(): 切片中追加值

数组容量永远和长度相等,且不可变

// usage of make()

// 返回值而不是指针
make(types interface{},length int,capacity int)

// types:要创建的类型
// length:该类型的长度
// capacity该类型的容量

0.3. 切片与底层数组

// make函数或切片值字面量初始化时,切片最左边与底层数组最左边对应
slice1 := make([]int,3,5)
sliec2 := []int{1,2,3,4,5,6,7,8}

// 切片表达式创建切片时,切片最左边与底层数组索引对应,slice3的最左边对应slice2的索引3
slice3 := slice2[3:6]
// slice3的容量为可见底层数组的容量,即底层数组减去切片起始索引值

// slice3向右扩展至最大
slice3 = slice3[0:cap(slice3)]

切片表达式是一个开区间,得到的新切片的容量和长度为区间的差值。新切片的起始值为原切片或数组对应的索引值。

切片无法向左扩展,但是可以向右扩展。

0.3.1. 切片扩容

当切片无法容纳更多元素时,Go用语言会进行扩容,不会改变原切片,而是创建一个容量更大的新切片,将原来的元素和新的元素一起拷贝到新的切片中。

一般情况扩容为原来的2倍,当原切片的长度大于等于1024后,一次增长1.25倍的方式逐渐扩容。

0.3.2. 切片底层数组被替换的情况

切片在扩容时,创建了新的切片和新的底层数组,原来的切片和底层数组没有任何改动。

  1. 在底层数组容量(即切片容量)足够的情况下append()函数返回的是指向原底层数组的切片
  2. 在底层数组容量(即切片容量)不够的情况下append()函数返回的是指向新底层数组的新切片

0.4. 可寻址与不可寻址

package main
import (
    "crypto/sha1"
    "fmt"
)

func main() {
    input := []byte("Hello, playground")
    hash := sha1.Sum(input)[:5] //
    fmt.Println(hash)
}
// output
./test.go:8:28: invalid operation sha1.Sum(input)[:5] (slice of unaddressable value)

看一下crypto/sha1库:

// The size of a SHA-1 checksum in bytes.
const Size = 20

// The blocksize of SHA-1 in bytes.
const BlockSize = 64

func Sum(data []byte) [Size]byte {
	var d digest
	d.Reset()
	d.Write(data)
	return d.checkSum()
}

sha1.Sum()返回一个长度是20的数组,而不是切片(如果是切片不会报错)。

Go是返回数值的,所以这里是20字节的数组,而不是指向它的指针。

0.4.1. 不可寻址

大多数匿名值都不可寻址(复合字面值是一个例外)。

在上面的代码中,sha1.Sum() 的返回值是匿名的,因为我们立即对其进行了切片操作。如果我们将它存在变量中,并因此使其变为非匿名,就是可寻址的,则该代码不会报错,如下所示。

tmp := sha1.Sum(input)
hash := tmp[:5]

因为对数组进行切片操作要求该数组是可寻址的sha1.Sum() 返回的匿名数组是不可寻址的,因此对其进行切片会被编译器拒绝。

如果在这里允许对不可寻址的匿名值进行切片操作,那么 Go 要默默地实现堆存储以容纳 sha1.Sum() 的返回值(然后将该值复制到另一个值),该返回值将一直存在直到那个切片被回收。

注意:Go 语言规范中的许多内容要求或仅对可寻址的值适用。例如,大多数赋值操作需要可寻址性。

0.4.2. 方法调用

假设有一个类型 T,并且在 *T 上定义了一些方法,例如 *T.Op()。就像 Go 允许在不取消引用指针的情况下进行字段引用一样,可以在非指针值上调用指针方法:

type T struct{

}

func (t *T)Op(){

}

// afunc() 返回一个 T
func aFunc() T{
    return T
}

var x T
x.Op()  // 这是 (&x).Op() 的简便写法

// 此简便写法需要获取地址,因此需要可寻址性,以下操作报错
aFunc().Op()

// 但是这个可以运行
var x T = aFunc()
x.Op()

并发访问切片

由于 slice/map 是引用类型,golang 函数是传值调用,所用参数副本依然是原来的 slice/map, 并发访问同一个资源会导致竞态条件。

package main

import (
	"fmt"
	"sync"
)

func main() {
	var (
		slc []int
		n   = 1000
		wg  sync.WaitGroup
	)

	wg.Add(n)
	for i := 0; i < n; i++ {
		go func() {
			slc = append(slc, 1)
			wg.Done()
		}()
	}
	wg.Wait()

	fmt.Println("len->", len(slc))
	fmt.Println("cap->", cap(slc))
}

// output
len-> 997
cap-> 1024

真实的输出并没有达到我们的预期,len(slice) < n

slice是对数组一个连续片段的引用,当 slice 长度增加的时候,底层的数组会被换掉。当在换底层数组之前,切片同时被多个 goroutine 拿到,并执行 append 操作。那么很多 goroutine 的 append 结果会被覆盖,导致 n 个 gouroutine append 后,长度小于n。

go 1.9 增加sync.map实现并发安全,slice咋整?

加锁

优点是比较简单,适合对性能要求不高的场景。

package main

import (
	"fmt"
	"sync"
)

func main() {
	var (
		slc  []int
		n    = 1000
		wg   sync.WaitGroup
		lock sync.Mutex
	)

	wg.Add(n)
	for i := 0; i < n; i++ {
		go func() {
			lock.Lock()
			defer lock.Unlock()
			slc = append(slc, 1)
			wg.Done()
		}()
	}
	wg.Wait()

	fmt.Println("len->", len(slc))
	fmt.Println("cap->", cap(slc))
}

channl串行化

实现相对复杂,优点是性能很好,利用了channel的优势。

package main

import (
	"fmt"
	"sync"
)

type Service struct {
	ch   chan int // 同步channel
	data []int    // 存储数据的slice
}

func (s *Service) Schedule() {
	for i := range s.ch {
		s.data = append(s.data, i)
	}
}

func (s *Service) Close() {
	close(s.ch)
}

func (s *Service) AddData(v int) {
	s.ch <- v
}

func NewScheduler(size int, done func()) *Service {
	s := &Service{
		ch:   make(chan int, size),
		data: make([]int, 0),
	}

	go func() {
		s.Schedule()
		done()
	}()

	return s
}

func main() {
	var (
		n  = 1000
		wg sync.WaitGroup
	)

	c := make(chan struct{})

	s := NewScheduler(n, func() { c <- struct{}{} })

	wg.Add(n)
	for i := 0; i < n; i++ {
		go func(v int) {
			defer wg.Done()
			s.AddData(v)
		}(i)
	}
	wg.Wait()
	s.Close()
	<-c

	fmt.Println("len->", len(s.data))
	fmt.Println("cap->", cap(s.data))
}
上次修改: 25 November 2019