Go Map 原理


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 置为空。
阅读全文

Go Map


先声明 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"

阅读全文

Go 比较两个 Slice 是否相等


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

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

reflect 比较的方法

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

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

阅读全文

Go Array & Slice 底层实现


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 Array & Slice


数组

几乎所有计算机语言,数组的实现都是相似的:一段连续的内存,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 初始化。

阅读全文

Go base64


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))
}
阅读全文

Go 计算字符串 md5 值


主要是使用 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
}
阅读全文

Go 字符串分割


将字符串 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)
}
阅读全文

Go 字符串拼接


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,所以性能也不是很。

阅读全文