千夜同学 发布的文章

map 的底层实现是一个散列表,因此实现 map 的过程实际上就是实现散表的过程。

在这个散列表中,主要出现的结构体有两个,一个叫 hmap(a header for a go map),一个叫 bmap(a bucket for a Go map,通常叫其 bucket)。

这两种结构的样子分别如下所示:

hmap:

image

只需要关心的只有一个,就是标红的字段 buckets 数组。map 中用于存储的结构是 bucket 数组。而 bucket(bmap) 的结构是怎样的呢?

bucket:

image

相比于 hmap,bucket 的结构显得简单一些,标红的字段依然是核心,我们使用的 map 中的 key 和 value 就存储在这里。高位哈希值数组记录的是当前 bucket 中 key 相关的索引,稍后会详细叙述。还有一个字段是一个指向扩容后的 bucket 的指针,使得 bucket 会形成一个链表结构。

image

由此看出 hmap 和 bucket 的关系是这样的:

image

而 bucket 又是一个链表。

image

哈希表的特点是会有一个哈希函数,对传来的 key 进行哈希运算,得到唯一的值,一般情况下都是一个数值。map 中也有这么一个哈希函数,也会算出唯一的值。

Go 把求得的值按照用途一分为二:高位和低位。

image

蓝色为高位,红色为低位。

然后低位用于寻找当前 key 属于 hmap 中的哪个 bucket,而高位用于寻找 bucket 中的哪个 key。上文中提到,bucket 中有个属性字段是高位哈希值数组,这里存的就是蓝色的高位值,用来声明当前 bucket 中有哪些 key,便于搜索查找。

需要特别指出的一点是,map 中的 key/value 值都是存到同一个数组中的。

image

并不是 key0/value0/key1/value1 的形式,这样做的好处是在 key 和 value 的长度不同的时候,可以消除 padding 带来的空间浪费。

map整个的结构图

image

map的扩容

当以上的哈希表增长的时候,Go 语言会将 bucket 数组的数量扩充一倍,产生一个新的 bucket 数组,并将旧数组的数据迁移至新数组。

加载因子

判断扩充的条件,就是哈希表中的加载因子(loadFactor)。

加载因子是一个阈值,一般表示为:散列包含的元素数 除以 位置总数。是一种 产生冲突机会空间使用 的平衡与折中。

加载因子越小,说明空间空置率高,空间使用率小,但是加载因子越大,说明空间利用率上去了,但是“产生冲突机会”高了。

每种哈希表的都会有一个加载因子,数值超过加载因子就会为哈希表扩容。

加载因子公式

map长度 / 2^B

阈值是 6.5。其中 B 可以理解为已扩容的次数。

当 map 长度增长到大于加载因子所需的 map 长度时,就会将产生一个新的 bucket 数组,然后把旧的 bucket 数组移到一个属性字段 oldbucket 中。

注意:并不是立刻把旧的数组中的元素转义到新的 bucket 当中,而是只有当访问到具体的某个 bucket 的时候,才会把 bucket 中的数据转移到新的 bucket 中。

当扩容的时候,map 结构体中会保存旧的数据,和新生成的数组。

image

上面部分代表旧的有数据的 bucket,下面部分代表新生成的新的 bucket。蓝色代表存有数据的 bucket,橘黄色代表空的 bucket。

image

注意:这里并不会直接删除旧的 bucket,而是把原来的引用去掉,利用 GC 清除内存。

map 中数据的删除

  1. 如果 key 是一个指针类型的,则直接将其置为空,等待 GC 清除。
  2. 如果是值类型的,则清除相关内存。
  3. 同理,对 value 做相同的操作。
  4. 最后把 key 对应的高位值对应的数组 index 置为空。

先声明 map

var m1 map[string]string

再使用 make 函数创建一个非 nil 的 map,nil map 不能赋值。

make 函数会分配和初始化一个哈希 map 数据结构,并返回一个指向该哈希 map 的映射变量。相关数据结构细节由运行时实现,并且不因语言本身所规定。

m1 = make(map[string]string)

最后给已声明的 map 赋值

m1["a"] = "aa"
m1["b"] = "bb"

- 阅读剩余部分 -

开发中经常会遇到需要比较两个 slice 包含的元素是否完全相等的情况,一般来说有两个思路:

  • reflect 比较的方法
  • 循环遍历比较的方法

reflect 比较的方法

func StringSliceReflectEqual(a, b []string) bool {
    return reflect.DeepEqual(a, b)
}

这个写法很简单,就是直接使用 reflect 包的 reflect.DeepEqual 方法来比较 a 和 b 是否相等。

- 阅读剩余部分 -

Array

Go 语言的数组不同于 C 语言或者其他语言的数组,C 语言的数组变量是指向数组第一个元素的指针;而 Go 语言的数组是一个值,Go 语言中的数组是值类型,一个数组变量就表示着整个数组,意味着 Go 语言的数组在传递的时候,传递的是原数组的拷贝。你可以理解为 Go 语言的数组是一种有序的 struct。

func testArray(x [2]int) {
    fmt.Printf("func Array : %p , %v\n", &x, x)
}
    
func main() {
    arrayA := [2]int{100, 200}
    var arrayB [2]int
    arrayB = arrayA
    fmt.Printf("arrayA : %p , %v\n", &arrayA, arrayA)
    fmt.Printf("arrayB : %p , %v\n", &arrayB, arrayB)
    testArray(arrayA)
}

打印结果:

arrayA : 0xc4200bebf0 , [100 200]
arrayB : 0xc4200bec00 , [100 200]
func Array : 0xc4200bec30 , [100 200]

- 阅读剩余部分 -

数组

几乎所有计算机语言,数组的实现都是相似的:一段连续的内存,Go 语言也一样,Go 语言的数组底层实现就是一段连续的内存空间。每个元素有唯一一个索引(或者叫下标)来访问。

如下图所示,下图是 [5]int{1:10, 2:20} 数组的内部实现逻辑图:

image

由于内存连续,CPU 很容易计算索引(即数组的下标),可以快速迭代数组里的所有元素。

slice

切片是一个很小的对象,是对数组进行了抽象,并提供相关的操作方法。切片有三个属性字段:长度、容量和指向数组的指针。严格地讲,切片有容量(capacity)和长度(length)两个属性。

切片有两种定义方式,一种是先声明一个变量是切片,然后使用内置函数 make 去初始化这个切片。另外一种是通过取数组切片来赋值。

package main
    
import (
    "fmt"
)
    
func main() {
    var x = make([]float64, 5)
    fmt.Println("Capcity:", cap(x), "Length:", len(x))
    var y = make([]float64, 5, 10)
    fmt.Println("Capcity:", cap(y), "Length:", len(y))
    for i := 0; i < len(x); i++ {
        x[i] = float64(i)
    }
    fmt.Println(x)
    for i := 0; i < len(y); i++ {
        y[i] = float64(i)
    }
    fmt.Println(y)
}

输出结果为

Capcity: 5 Length: 5
Capcity: 10 Length: 5
[0 1 2 3 4]
[0 1 2 3 4]

上面我们首先用 make 函数定义切片 x,这个时候 x 的容量是 5,长度也是 5。然后使用 make 函数定义了切片 y,这个时候 y 的容量是 10,长度是 5。然后我们再分别为切片 x 和 y 的元素赋值,最后输出。

所以使用 make 函数定义切片的时候,有两种方式,一种只指定长度,这个时候切片的长度和容量是相同的。另外一种是同时指定切片长度和容量。虽然切片的容量可以大于长度,但是赋值的时候要注意最大的索引仍然是 len(x)-1。否则会报索引超出边界错误。

另外一种是通过数组切片赋值,采用 [low_index:high_index] 的方式获取数值切片,其中切片元素包括 low_index 的元素,但是不包括 high_index 的元素。

package main
    
import (
    "fmt"
)
    
func main() {
    var arr1 = [5]int{1, 2, 3, 4, 5}
    var s1 = arr1[2:3]
    var s2 = arr1[:3]
    var s3 = arr1[2:]
    var s4 = arr1[:]
    fmt.Println(s1)
    fmt.Println(s2)
    fmt.Println(s3)
    fmt.Println(s4)
}

输出结果为

[3]
[1 2 3]
[3 4 5]
[1 2 3 4 5]

在上面的例子中,我们还省略了 low_index 或 high_index。

如果省略了 low_index,那么等价于从索引 0 开始;如果省略了 high_index,则默认 high_index 等于 len(arr1),即切片长度。

这里为了体现切片的长度可以变化,我们看一下下面的例子:

package main
    
import (
    "fmt"
)
    
func main() {
    var arr1 = make([]int, 5, 10)
    for i := 0; i < len(arr1); i++ {
        arr1[i] = i
    }
    fmt.Println(arr1)
    arr1 = append(arr1, 5, 6, 7, 8)
    fmt.Println("Capacity:", cap(arr1), "Length:", len(arr1))
    fmt.Println(arr1)
}

输出结果为

[0 1 2 3 4]
Capacity: 10 Length: 9
[0 1 2 3 4 5 6 7 8]

image

上图中,ptr 指的是指向 array 的 pointer,len 是指切片的长度, cap 指的是切片的容量。

对于s := make([]byte, 5) 和 s := []byte{...} 的方式

image

对于 s = s[2:4] 的方式

image

对于 nil 的切片即 var s []byte 对应的逻辑图是

image

在此有一个说明:nil 切片和空切片是不太一样的,空切片即 s := make([]byte, 0) 或者 s := []byte{} 出来的切片
空切片的逻辑图为:

image

空切片指针不为 nil,而 nil 切片指针为 nil。但是,不管是空切片还是 nil 切片,对其调用内置函数 append()、len 和 cap 的效果都是一样的,感受不到任何区别。

扩容

这里我们初始化 arr1 为容量 10,长度为 5 的切片,然后为前面的 5 个元素赋值。然后输出结果。然后我们再使用 Go 内置方法 append 来为 arr1 追加四个元素,这个时候再看一下 arr1 的容量和长度以及切片元素,我们发现切片的长度确实变了。

另外我们再用 append 方法给 arr1 多追加几个元素,试图超过 arr1 原来定义的容量大小。

package main
    
import (
    "fmt"
)
    
func main() {
    var arr1 = make([]int, 5, 10)
    for i := 0; i < len(arr1); i++ {
        arr1[i] = i
    }
    arr1 = append(arr1, 5, 6, 7, 8, 9, 10)
    fmt.Println("Capacity:", cap(arr1), "Length:", len(arr1))
    fmt.Println(arr1)
}

输出结果为

Capacity: 20 Length: 11
[0 1 2 3 4 5 6 7 8 9 10]

我们发现 arr1 的长度变为 11,因为元素个数现在为 11 个。另外我们发现 arr1 的容量也变了,变为原来的两倍。这是因为 Go 在默认的情况下,如果追加的元素超过了容量大小,Go 会自动地重新为切片分配容量,容量大小为原来的两倍。

上面我们介绍了,可以使用 append 函数给切片增加元素,现在我们再来介绍一个 copy 函数用来从一个切片拷贝元素到另一个切片。

package main
    
import (
    "fmt"
)
    
func main() {
    slice1 := []int{1, 2, 3, 4, 5, 6}
    slice2 := make([]int, 5, 10)
    copy(slice2, slice1)
    fmt.Println(slice1)
    fmt.Println(slice2)
}

输出结果

[1 2 3 4 5 6]
[1 2 3 4 5]

在上面的例子中,我们将 slice1 的元素拷贝到 slice2,因为 slice2 的长度为 5,所以最多拷贝 5 个元素。

应用

package main

import (
    "fmt"
    "reflect"
)

func main() {
    // index
    arrayA := [...]int{0: 1, 2: 1, 3: 4}
    fmt.Println(arrayA)

    // type
    arrayB := [...]int{1, 2, 3}
    arrayC := [...]int{1, 2, 3, 4}
    fmt.Println(reflect.TypeOf(arrayB))
    fmt.Println(reflect.TypeOf(arrayC))
    fmt.Println(reflect.TypeOf(arrayB) == reflect.TypeOf(arrayC))

    array := [4]int{10, 20, 30, 40}
    slice := array[0:2]
    fmt.Println(slice)

    newSlice := append(append(append(slice, 50), 100), 150)
    fmt.Println(newSlice)

    newSlice[1] = newSlice[1] + 1
    fmt.Println(newSlice)

    sliceInt := []int{1, 2, 3, 4, 5, 6}
    newSliceInt := append(sliceInt, 1)
    fmt.Println(newSliceInt)
}
r := [...]int{99:-1}

定义了一个含有 100 个元素的数组 r,最后一个元素输出化为 -1,其他的元素都是用 0 初始化。

package main

import (
    "encoding/base64"
    "fmt"
    "log"
)

func main() {
    input := []byte("hello golang base64")

    // base64 encode
    encodeString := base64.StdEncoding.EncodeToString(input)
    fmt.Println(encodeString)

    // base decode
    decodeBytes, err := base64.StdEncoding.DecodeString(encodeString)
    if err != nil {
        log.Fatalln(err)
    }
    fmt.Println(string(decodeBytes))
}

主要是使用 crypto/md5、encoding/hex 两个包

字符串:

package utils

import (
    "crypto/md5"
    "encoding/hex"
)

// MakeMD func
func MakeMD(initString string) string {
    m := md5.New()
    m.Write([]byte(initString))
    md := m.Sum(nil)
    mdString := hex.EncodeToString(md)
    return mdString
}

将字符串 s 以空格为分隔符拆分成若干个字符串,若成功则返回分割后的字符串切片。

str := "Hello World Too"
for _, v := range strings.Fields(str) {
    fmt.Println(v)
}

将字符串 s 中的字符串以字符 sep 为分隔符拆分成若干个元素的字符串切片,并返回字符串切片。

for _, v := range strings.Split(str, " ") {
    fmt.Println(v)
}

将字符串 s 中的字符串以字符 sep 为分隔符拆分成若干个字符串切片并且保留原字符串中的分隔符号,并返回字符串切片。

for _, v := range strings.SplitAfter(str, ",") {
    fmt.Println(v)
}

1.直接使用运算符

func BenchmarkAddStringWithOperator(b *testing.B) {
    hello := "hello"
    world := "world"
    for i := 0; i < b.N; i++ {
        _ = hello + "," + world
    }
}

go 里面的字符串都是不可变的,每次运算都会产生一个新的字符串,所以会产生很多临时的无用的字符串,不仅没有用,还会给 gc 带来额外的负担,所以性能比较差。

2.fmt.Sprintf()

func BenchmarkAddStringWithSprintf(b *testing.B) {
    hello := "hello"
    world := "world"
    for i := 0; i < b.N; i++ {
        _ = fmt.Sprintf("%s,%s", hello, world)
    }
}

内部使用 []byte 实现,不像直接运算符这种会产生很多临时的字符串,但是内部的逻辑比较复杂,有很多额外的判断,还用到了 interface,所以性能也不是很。

- 阅读剩余部分 -