Go语言数组、切片、Map的使用和实现原理

数组切片SliceSlice实现原理MapMap实现原理数组Go数组特征数组：是同一种数据类型的固定长度的序列。数组定义：vara[len]int，比如：vara[5]int，数组长度必须是常量，且是类型的组成部分。一旦定义，长度不能变。长度是数组类型的一部

目录

数组

Go 数组特征

  1. 数组：是同一种数据类型的固定长度的序列。
  2. 数组定义：var a [len]int，比如：var a [5]int，数组长度必须是常量，且是类型的组成部分。一旦定义，长度不能变。
  3. 长度是数组类型的一部分，因此，var a[5] int和var a[10]int是不同的类型。
  4. 数组可以通过下标进行访问，下标是从0开始，最后一个元素下标是：len-1 for i := 0; i < len(a); i++ { } for index, v := range a { }
  5. 访问越界，如果下标在数组合法范围之外，则触发访问越界，会panic
  6. 数组是值类型，赋值和传参会复制整个数组，而不是指针。因此改变副本的值，不会改变本身的值。
  7. 支持 "=="、"!=" 操作符，因为内存总是被初始化过的。
  8. 指针数组 [n]T，数组指针 [n]T。

一维数组

package main
import (
    "fmt"
)
var arr0 [5]int = [5]int{1, 2, 3}
var arr1 = [5]int{1, 2, 3, 4, 5}
var arr2 = [...]int{1, 2, 3, 4, 5, 6}
var str = [5]string{3: "hello world", 4: "tom"}

func main() {
    a := [3]int{1, 2}           // 未初始化元素值为 0。
    b := [...]int{1, 2, 3, 4}   // 通过初始化值确定数组长度。
    c := [5]int{2: 100, 4: 200} // 使用引号初始化元素。
    d := [...]struct {
        name string
        age  uint8
    }{
        {"user1", 10}, // 可省略元素类型。
        {"user2", 20}, // 别忘了最后一行的逗号。
    }
    fmt.Println(arr0, arr1, arr2, str)
    fmt.Println(a, b, c, d)
}

多维数组

package main
import (
    "fmt"
)
var arr0 [5][3]int
var arr1 [2][3]int = [...][3]int{{1, 2, 3}, {7, 8, 9}}

func main() {
    a := [2][3]int{{1, 2, 3}, {4, 5, 6}}
    b := [...][2]int{{1, 1}, {2, 2}, {3, 3}} // 第 2 纬度不能用 "..."。
    fmt.Println(arr0, arr1)
    fmt.Println(a, b)
}

多维数组遍历

package main
import (
    "fmt"
)
func main() {

    var f [2][3]int = [...][3]int{{1, 2, 3}, {7, 8, 9}}

    for k1, v1 := range f {
        for k2, v2 := range v1 {
            fmt.Printf("(%d,%d)=%d ", k1, k2, v2)
        }
        fmt.Println()
    }
}

数组拷贝和传参

package main
import "fmt"
func printArr(arr *[5]int) {
    arr[0] = 10
    for i, v := range arr {
        fmt.Println(i, v)
    }
}

func main() {
    var arr1 [5]int
    printArr(&arr1)
    fmt.Println(arr1)
    arr2 := [...]int{2, 4, 6, 8, 10}
    printArr(&arr2)
    fmt.Println(arr2)
}

切片Slice

切片Slice特征

  1. 切片：切片是数组的一个引用，因此切片是引用类型。但自身是结构体，值拷贝传递。
  2. 切片的长度可以改变，因此，切片是一个可变的数组。
  3. 切片遍历方式和数组一样，可以用len()求长度。表示可用元素数量，读写操作不能超过该限制。
  4. cap可以求出slice最大扩张容量，不能超出数组限制。0 <= len(slice) <= len(array)，其中array是slice引用的数组。
  5. 切片的定义：var 变量名 []类型，比如 var str []string var arr []int。
  6. 如果 slice == nil，那么 len、cap 结果都等于 0。

创建切片的各种方式

package main

import "fmt"

func main() {
   //1.声明切片
   var s1 []int
   if s1 == nil {
      fmt.Println("是空")
   } else {
      fmt.Println("不是空")
   }
   // 2.:=
   s2 := []int{}
   // 3.make()
   var s3 []int = make([]int, 0)
   fmt.Println(s1, s2, s3)
   // 4.初始化赋值
   var s4 []int = make([]int, 0, 0)
   fmt.Println(s4)
   s5 := []int{1, 2, 3}
   fmt.Println(s5)
   // 5.从数组切片
   arr := [5]int{1, 2, 3, 4, 5}
   var s6 []int
   // 前包后不包
   s6 = arr[1:4]
   fmt.Println(s6)
}

切片初始化

package main

import (
    "fmt"
)

var arr = [...]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
var slice0 []int = arr[2:8]
var slice1 []int = arr[0:6]        //可以简写为 var slice []int = arr[:end]
var slice2 []int = arr[5:10]       //可以简写为 var slice[]int = arr[start:]
var slice3 []int = arr[0:len(arr)] //var slice []int = arr[:]
var slice4 = arr[:len(arr)-1]      //去掉切片的最后一个元素
func main() {
    fmt.Printf("全局变量：arr %v\n", arr)
    fmt.Printf("全局变量：slice0 %v\n", slice0)
    fmt.Printf("全局变量：slice1 %v\n", slice1)
    fmt.Printf("全局变量：slice2 %v\n", slice2)
    fmt.Printf("全局变量：slice3 %v\n", slice3)
    fmt.Printf("全局变量：slice4 %v\n", slice4)
    fmt.Printf("-----------------------------------\n")
    arr2 := [...]int{9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
    slice5 := arr[2:8]
    slice6 := arr[0:6]         //可以简写为 slice := arr[:end]
    slice7 := arr[5:10]        //可以简写为 slice := arr[start:]
    slice8 := arr[0:len(arr)]  //slice := arr[:]
    slice9 := arr[:len(arr)-1] //去掉切片的最后一个元素
    fmt.Printf("局部变量： arr2 %v\n", arr2)
    fmt.Printf("局部变量： slice5 %v\n", slice5)
    fmt.Printf("局部变量： slice6 %v\n", slice6)
    fmt.Printf("局部变量： slice7 %v\n", slice7)
    fmt.Printf("局部变量： slice8 %v\n", slice8)
    fmt.Printf("局部变量： slice9 %v\n", slice9)
}

通过make来创建切片

// 语法
var slice []type = make([]type, len)
slice  := make([]type, len)
slice  := make([]type, len, cap)

// 实例
package main
import (
    "fmt"
)

var slice0 []int = make([]int, 10)
var slice1 = make([]int, 10)
var slice2 = make([]int, 10, 10)

func main() {
    fmt.Printf("make全局slice0 ：%v\n", slice0)
    fmt.Printf("make全局slice1 ：%v\n", slice1)
    fmt.Printf("make全局slice2 ：%v\n", slice2)
    fmt.Println("--------------------------------------")
    slice3 := make([]int, 10)
    slice4 := make([]int, 10)
    slice5 := make([]int, 10, 10) // 使用 make 创建，指定 len 和 cap 值。

    s2 := make([]int, 6, 8) // 使用 make 创建，指定 len 和 cap 值。
    fmt.Println(s2, len(s2), cap(s2))
    s3 := make([]int, 6) // 省略 cap，相当于 cap = len。

    fmt.Printf("make局部slice3 ：%v\n", slice3)
    fmt.Printf("make局部slice4 ：%v\n", slice4)
    fmt.Printf("make局部slice5 ：%v\n", slice5)
}

用append内置函数操作切片（切片追加）

package main
import (
    "fmt"
)
func main() {
  var a = []int{1, 2, 3}
  fmt.Printf("slice a : %v\n", a)
  var b = []int{4, 5, 6}
  fmt.Printf("slice b : %v\n", b)
  c := append(a, b...)
  fmt.Printf("slice c : %v\n", c)
  d := append(c, 7)
  fmt.Printf("slice d : %v\n", d)
  e := append(d, 8, 9, 10)
  fmt.Printf("slice e : %v\n", e)

  s1 := make([]int, 0, 5)
  fmt.Printf("%p\n", &s1)

  s2 := append(s1, 1)  // 向 slice 尾部添加数据，返回新的 slice 对象。
  fmt.Printf("%p\n", &s2)

  fmt.Println(s1, s2)
}

超出原 slice.cap 限制，就会重新分配底层数组，即便原数组并未填满。

package main

import (
    "fmt"
)

func main() {

    data := [...]int{0, 1, 2, 3, 4, 10: 0}
    s := data[:2:3]

    s = append(s, 100, 200) // 一次 append 两个值，超出 s.cap 限制。

    fmt.Println(s, data)         // 重新分配底层数组，与原数组无关。
    fmt.Println(&s[0], &data[0]) // 比对底层数组起始指针。

    m := make([]int, 0, 1)
    c := cap(m)

    for i := 0; i &lt; 50; i++ {
        m = append(m, i)
        if n := cap(m); n > c {
            fmt.Printf("cap: %d -> %d\n", c, n)
            c = n
        }
    }
}

切片拷贝

package main

import (
    "fmt"
)

func main() {

    s1 := []int{1, 2, 3, 4, 5}
    fmt.Printf("slice s1 : %v\n", s1)
    s2 := make([]int, 10)
    fmt.Printf("slice s2 : %v\n", s2)
    copy(s2, s1)    // 切片拷贝函数
    fmt.Printf("copied slice s1 : %v\n", s1)
    fmt.Printf("copied slice s2 : %v\n", s2)
    s3 := []int{1, 2, 3}
    fmt.Printf("slice s3 : %v\n", s3)
    s3 = append(s3, s2...)
    fmt.Printf("appended slice s3 : %v\n", s3)
    s3 = append(s3, 4, 5, 6)
    fmt.Printf("last slice s3 : %v\n", s3)

}

slice遍历

package main

import (
    "fmt"
)

func main() {

    data := [...]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
    slice := data[:]
    for index, value := range slice {
        fmt.Printf("inde : %v , value : %v\n", index, value)
    }

}

切片resize（调整大小）

package main

import (
    "fmt"
)

func main() {
    var a = []int{1, 3, 4, 5}
    fmt.Printf("slice a : %v , len(a) : %v\n", a, len(a))
    b := a[1:2]
    fmt.Printf("slice b : %v , len(b) : %v\n", b, len(b))
    c := b[0:3]
    fmt.Printf("slice c : %v , len(c) : %v\n", c, len(c))
}

字符串和切片（string and slice）

package main

import (
    "fmt"
)

func main() {
    str := "hello world"
    s1 := str[0:5]
    fmt.Println(s1)

    s2 := str[6:]
    fmt.Println(s2)

    s := []byte(str) //中文字符需要用[]rune(str)
    s[6] = 'G'
    s = s[:8]
    s = append(s, '!')
    str = string(s)
    fmt.Println(str)
}

Slice实现原理

切片是 Go 中的一种基本的数据结构，使用这种结构可以用来管理数据集合。切片的设计想法是由动态数组概念而来，为了开发者可以更加方便的使一个数据结构可以自动增加和减少。但是切片本身并不是动态数据或者数组指针。切片常见的操作有 reslice、append、copy。与此同时，切片还具有可索引，可迭代的优秀特性。

切片和数组

用切片传数组参数，既可以达到节约内存的目的，也可以达到合理处理好共享内存的问题。切片的指针和原来数组的指针是不同的。切片是引用传递，所以它们不需要使用额外的内存并且比使用数组更有效率。并非所有时候都适合用切片代替数组，因为切片底层数组可能会在堆上分配内存，而且小数组在栈上拷贝的消耗也未必比make 消耗大。

package main
import "testing"
func array() [1024]int {
    var x [1024]int
    for i := 0; i &lt; len(x); i++ {
        x[i] = i
    }
    return x
}
func slice() []int {
    x := make([]int, 1024)
    for i := 0; i &lt; len(x); i++ {
        x[i] = i
    }
    return x
}
func BenchmarkArray(b *testing.B) {
    for i := 0; i &lt; b.N; i++ {
        array()
    }
}
func BenchmarkSlice(b *testing.B) {
    for i := 0; i &lt; b.N; i++ {
        slice()
    }
}

切片的数据结构

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

切片的结构体由3部分构成，Pointer 是指向一个数组的指针，len 代表当前切片的长度，cap 是当前切片的容量。cap 总是大于等于 len 的。

// 从 slice 中得到一块内存地址
s := make([]byte, 200)
ptr := unsafe.Pointer(&s[0])

// 从 Go 的内存地址中构造一个 slice
var ptr unsafe.Pointer
var s1 = struct {
    addr uintptr
    len int
    cap int
}{ptr, length, length}
s := *(*[]byte)(unsafe.Pointer(&s1))

// 在 Go 的反射中就存在一个与之对应的数据结构 SliceHeader，我们可以用它来构造一个 slice
var o []byte
sliceHeader := (*reflect.SliceHeader)((unsafe.Pointer(&o)))
sliceHeader.Cap = length
sliceHeader.Len = length
sliceHeader.Data = uintptr(ptr)

make 和切片字面量

func makeslice(et *_type, len, cap int) slice {
  // 根据切片的数据类型，获取切片的最大容量
  maxElements := maxSliceCap(et.size)
  // 比较切片的长度，长度值域应该在[0,maxElements]之间
  if len &lt; 0 || uintptr(len) > maxElements {
      panic(errorString("makeslice: len out of range"))
  }
  // 比较切片的容量，容量值域应该在[len,maxElements]之间
  if cap &lt; len || uintptr(cap) > maxElements {
      panic(errorString("makeslice: cap out of range"))
  }
  // 根据切片的容量申请内存
  p := mallocgc(et.size*uintptr(cap), et, true)
  // 返回申请好内存的切片的首地址
  return slice{p, len, cap}
}

func makeslice64(et *_type, len64, cap64 int64) slice {
  len := int(len64)
  if int64(len) != len64 {
      panic(errorString("makeslice: len out of range"))
  }

  cap := int(cap64)
  if int64(cap) != cap64 {
      panic(errorString("makeslice: cap out of range"))
  }

  return makeslice(et, len, cap)
}

切片扩容

func growslice(et *_type, old slice, cap int) slice {
  if raceenabled {
      callerpc := getcallerpc(unsafe.Pointer(&et))
      racereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, funcPC(growslice))
  }
  if msanenabled {
      msanread(old.array, uintptr(old.len*int(et.size)))
  }

  if et.size == 0 {
      // 如果新要扩容的容量比原来的容量还要小，这代表要缩容了，那么可以直接报panic了。
      if cap &lt; old.cap {
          panic(errorString("growslice: cap out of range"))
      }

      // 如果当前切片的大小为0，还调用了扩容方法，那么就新生成一个新的容量的切片返回。
      return slice{unsafe.Pointer(&zerobase), old.len, cap}
  }

// 这里就是扩容的策略
  newcap := old.cap
  doublecap := newcap + newcap
  if cap > doublecap {
      newcap = cap
  } else {
      if old.len &lt; 1024 {
          newcap = doublecap
      } else {
          for newcap &lt; cap {
              newcap += newcap / 4
          }
      }
  }

  // 计算新的切片的容量，长度。
  var lenmem, newlenmem, capmem uintptr
  const ptrSize = unsafe.Sizeof((*byte)(nil))
  switch et.size {
  case 1:
      lenmem = uintptr(old.len)
      newlenmem = uintptr(cap)
      capmem = roundupsize(uintptr(newcap))
      newcap = int(capmem)
  case ptrSize:
      lenmem = uintptr(old.len) * ptrSize
      newlenmem = uintptr(cap) * ptrSize
      capmem = roundupsize(uintptr(newcap) * ptrSize)
      newcap = int(capmem / ptrSize)
  default:
      lenmem = uintptr(old.len) * et.size
      newlenmem = uintptr(cap) * et.size
      capmem = roundupsize(uintptr(newcap) * et.size)
      newcap = int(capmem / et.size)
  }

  // 判断非法的值，保证容量是在增加，并且容量不超过最大容量
  if cap &lt; old.cap || uintptr(newcap) > maxSliceCap(et.size) {
      panic(errorString("growslice: cap out of range"))
  }

  var p unsafe.Pointer
  if et.kind&kindNoPointers != 0 {
      // 在老的切片后面继续扩充容量
      p = mallocgc(capmem, nil, false)
      // 将 lenmem 这个多个 bytes 从 old.array地址 拷贝到 p 的地址处
      memmove(p, old.array, lenmem)
      // 先将 P 地址加上新的容量得到新切片容量的地址，然后将新切片容量地址后面的 capmem-newlenmem 个 bytes 这块内存初始化。为之后继续 append() 操作腾出空间。
      memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
  } else {
      // 重新申请新的数组给新切片
      // 重新申请 capmen 这个大的内存地址，并且初始化为0值
      p = mallocgc(capmem, et, true)
      if !writeBarrier.enabled {
          // 如果还不能打开写锁，那么只能把 lenmem 大小的 bytes 字节从 old.array 拷贝到 p 的地址处
          memmove(p, old.array, lenmem)
      } else {
          // 循环拷贝老的切片的值
          for i := uintptr(0); i &lt; lenmem; i += et.size {
              typedmemmove(et, add(p, i), add(old.array, i))
          }
      }
  }
  // 返回最终新切片，容量更新为最新扩容之后的容量
  return slice{p, old.len, newcap}
}

切片拷贝

func slicecopy(to, fm slice, width uintptr) int {
  // 如果源切片或者目标切片有一个长度为0，那么就不需要拷贝，直接 return 
  if fm.len == 0 || to.len == 0 {
      return 0
  }
  // n 记录下源切片或者目标切片较短的那一个的长度
  n := fm.len
  if to.len &lt; n {
      n = to.len
  }
  // 如果入参 width = 0，也不需要拷贝了，返回较短的切片的长度
  if width == 0 {
      return n
  }
  // 如果开启了竞争检测
  if raceenabled {
      callerpc := getcallerpc(unsafe.Pointer(&to))
      pc := funcPC(slicecopy)
      racewriterangepc(to.array, uintptr(n*int(width)), callerpc, pc)
      racereadrangepc(fm.array, uintptr(n*int(width)), callerpc, pc)
  }
  // 如果开启了 The memory sanitizer (msan)
  if msanenabled {
      msanwrite(to.array, uintptr(n*int(width)))
      msanread(fm.array, uintptr(n*int(width)))
  }

  size := uintptr(n) * width
  if size == 1 { 
      // TODO: is this still worth it with new memmove impl?
      // 如果只有一个元素，那么指针直接转换即可
      *(*byte)(to.array) = *(*byte)(fm.array) // known to be a byte pointer
  } else {
      // 如果不止一个元素，那么就把 size 个 bytes 从 fm.array 地址开始，拷贝到 to.array 地址之后
      memmove(to.array, fm.array, size)
  }
  return n
}

还有一个拷贝的方法，这个方法原理和 slicecopy 方法类似

func slicestringcopy(to []byte, fm string) int {
  // 如果源切片或者目标切片有一个长度为0，那么就不需要拷贝，直接 return 
  if len(fm) == 0 || len(to) == 0 {
      return 0
  }
  // n 记录下源切片或者目标切片较短的那一个的长度
  n := len(fm)
  if len(to) &lt; n {
      n = len(to)
  }
  // 如果开启了竞争检测
  if raceenabled {
      callerpc := getcallerpc(unsafe.Pointer(&to))
      pc := funcPC(slicestringcopy)
      racewriterangepc(unsafe.Pointer(&to[0]), uintptr(n), callerpc, pc)
  }
  // 如果开启了 The memory sanitizer (msan)
  if msanenabled {
      msanwrite(unsafe.Pointer(&to[0]), uintptr(n))
  }
  // 拷贝字符串至字节数组
  memmove(unsafe.Pointer(&to[0]), stringStructOf(&fm).str, uintptr(n))
  return n
}

Map

map定义

Go语言中 map的定义语法如: map[KeyType]ValueType, KeyType:表示键的类型。 ValueType:表示键对应的值的类型。

map类型的变量默认初始值为nil，需要使用make()函数来分配内存。语法为：make(map[KeyType]ValueType, [cap]), 其中cap表示map的容量，该参数虽然不是必须的，但是我们应该在初始化map的时候就为其指定一个合适的容量。

map基本使用

map中的数据都是成对出现的，map的基本使用示例代码如下：

func main() {
  scoreMap := make(map[string]int, 8)
  scoreMap["张三"] = 90
  scoreMap["小明"] = 100
  fmt.Println(scoreMap)
  fmt.Println(scoreMap["小明"])
  fmt.Printf("type of a:%T\n", scoreMap)

  userInfo := map[string]string{
    "username": "pprof.cn",
    "password": "123456",
  }
  fmt.Println(userInfo) //
}

判断某个键是否存在

Go语言中有个判断map中键是否存在的特殊写法，格式如下: value, ok := map[key]

func main() {
  scoreMap := make(map[string]int)
  scoreMap["张三"] = 90
  scoreMap["小明"] = 100
  // 如果key存在ok为true,v为对应的值；不存在ok为false,v为值类型的零值
  v, ok := scoreMap["张三"]
  if ok {
      fmt.Println(v)
  } else {
      fmt.Println("查无此人")
  }
}

map的遍历

func main() {
  scoreMap := make(map[string]int)
  scoreMap["张三"] = 90
  scoreMap["小明"] = 100
  scoreMap["王五"] = 60
  for k, v := range scoreMap {
      fmt.Println(k, v)
  }
}

// 遍历key
func main() {
  scoreMap := make(map[string]int)
  scoreMap["张三"] = 90
  scoreMap["小明"] = 100
  scoreMap["王五"] = 60
  for k := range scoreMap {
      fmt.Println(k)
  }
}

使用delete()函数删除键值对

使用delete()内建函数从map中删除一组键值对，delete()函数的格式如下：

delete(map, key)

其中，

  • map:表示要删除键值对的map
  • key:表示要删除的键值对的键
func main(){
  scoreMap := make(map[string]int)
  scoreMap["张三"] = 90
  scoreMap["小明"] = 100
  scoreMap["王五"] = 60
  delete(scoreMap, "小明")//将小明:100从map中删除
  for k,v := range scoreMap{
      fmt.Println(k, v)
  }
}

按照指定顺序遍历map

func main() {
  rand.Seed(time.Now().UnixNano()) //初始化随机数种子

  var scoreMap = make(map[string]int, 200)

  for i := 0; i &lt; 100; i++ {
      key := fmt.Sprintf("stu%02d", i) //生成stu开头的字符串
      value := rand.Intn(100)          //生成0~99的随机整数
      scoreMap[key] = value
  }
  //取出map中的所有key存入切片keys
  var keys = make([]string, 0, 200)
  for key := range scoreMap {
      keys = append(keys, key)
  }
  //对切片进行排序
  sort.Strings(keys)
  //按照排序后的key遍历map
  for _, key := range keys {
      fmt.Println(key, scoreMap[key])
  }
}

元素为map类型的切片

func main() {
  var mapSlice = make([]map[string]string, 3)
  for index, value := range mapSlice {
      fmt.Printf("index:%d value:%v\n", index, value)
  }
  fmt.Println("after init")
  // 对切片中的map元素进行初始化
  mapSlice[0] = make(map[string]string, 10)
  mapSlice[0]["name"] = "王五"
  mapSlice[0]["password"] = "123456"
  mapSlice[0]["address"] = "红旗大街"
  for index, value := range mapSlice {
      fmt.Printf("index:%d value:%v\n", index, value)
  }
}

值为切片类型的map

func main() {
  var sliceMap = make(map[string][]string, 3)
  fmt.Println(sliceMap)
  fmt.Println("after init")
  key := "中国"
  value, ok := sliceMap[key]
  if !ok {
      value = make([]string, 0, 2)
  }
  value = append(value, "北京", "上海")
  sliceMap[key] = value
  fmt.Println(sliceMap)
}

Map实现原理

Map是一种通过key来获取value的一个数据结构，其底层存储方式为数组，在存储时key不能重复，当key重复时，value进行覆盖，我们通过key进行hash运算（可以简单理解为把key转化为一个整形数字）然后对数组的长度取余，得到key存储在数组的哪个下标位置，最后将key和value组装为一个结构体，放入数组下标处

  length = len(array) = 4
  hashkey1 = hash(xiaoming) = 4
  index1  = hashkey1% length= 0
  hashkey2 = hash(xiaoli) = 6
  index2  = hashkey2% length= 2

Go中Map的使用

//直接创建初始化一个mao
var mapInit = map[string]string {"xiaoli":"湖南", "xiaoliu":"天津"}
//声明一个map类型变量,
//map的key的类型是string，value的类型是string
var mapTemp map[string]string
//使用make函数初始化这个变量,并指定大小(也可以不指定)
mapTemp = make(map[string]string,10)
//存储key ，value
mapTemp["xiaoming"] = "北京"
mapTemp["xiaowang"]= "河北"
//根据key获取value,
//如果key存在，则ok是true，否则是flase
//v1用来接收key对应的value,当ok是false时，v1是nil
v1,ok := mapTemp["xiaoming"]
fmt.Println(ok,v1)
//当key=xiaowang存在时打印value
if v2,ok := mapTemp["xiaowang"]; ok{
    fmt.Println(v2)
}
//遍历map,打印key和value
for k,v := range mapTemp{
    fmt.Println(k,v)
}
//删除map中的key
delete(mapTemp,"xiaoming")
//获取map的大小
l := len(mapTemp)
fmt.Println(l)

Go中Map的实现原理

go底层map到底怎么存储呢?接下来我们一探究竟。map的源码位于 src/runtime/map.go中 笔者go的版本是1.12在go中，map同样也是数组存储的的，每个数组下标处存储的是一个bucket,这个bucket的类型见下面代码，每个bucket中可以存储8个kv键值对，当每个bucket存储的kv对到达8个之后，会通过overflow指针指向一个新的bucket，从而形成一个链表,看bmap的结构，我想大家应该很纳闷，没看见kv的结构和overflow指针啊，事实上，这两个结构体并没有显示定义，是通过指针运算进行访问的。

go的整体内存结构，阅读一下map存储的源码，当往map中存储一个kv对时，通过k获取hash值，hash值的低八位和bucket数组长度取余，定位到在数组中的那个下标，hash值的高八位存储在bucket中的tophash中，用来快速判断key是否存在，key和value的具体值则通过指针运算存储，当一个bucket满时，通过overfolw指针链接到下一个bucket。

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    //获取hash算法
    alg := t.key.alg
    //计算hash值
    hash := alg.hash(key, uintptr(h.hash0))
    //如果bucket数组一开始为空，则初始化
    if h.buckets == nil {
        h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
    }
again:
    // 定位存储在哪一个bucket中
    bucket := hash & bucketMask(h.B)
    //得到bucket的结构体
    b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) +bucket*uintptr(t.bucketsize)))
    //获取高八位hash值
    top := tophash(hash)
    var inserti *uint8
    var insertk unsafe.Pointer
    var val unsafe.Pointer
bucketloop:
    //死循环
    for {
        //循环bucket中的tophash数组
        for i := uintptr(0); i &lt; bucketCnt; i++ {
            //如果hash不相等
            if b.tophash[i] != top {
             //判断是否为空，为空则插入
                if isEmpty(b.tophash[i]) && inserti == nil {
                    inserti = &b.tophash[i]
                    insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
                    val = add( unsafe.Pointer(b), 
                    dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize) )
                }
              //插入成功，终止最外层循环
                if b.tophash[i] == emptyRest {
                    break bucketloop
                }
                continue
            }
            //到这里说明高八位hash一样，获取已存在的key
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if t.indirectkey() {
                k = *((*unsafe.Pointer)(k))
            }
            //判断两个key是否相等，不相等就循环下一个
            if !alg.equal(key, k) {
                continue
            }
            // 如果相等则更新
            if t.needkeyupdate() {
                typedmemmove(t.key, k, key)
            }
            //获取已存在的value
            val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
            goto done
        }
        //如果上一个bucket没能插入，则通过overflow获取链表上的下一个bucket
        ovf := b.overflow(t)
        if ovf == nil {
            break
        }
        b = ovf
    }

    if inserti == nil {
        // all current buckets are full, allocate a new one.
        newb := h.newoverflow(t, b)
        inserti = &newb.tophash[0]
        insertk = add(unsafe.Pointer(newb), dataOffset)
        val = add(insertk, bucketCnt*uintptr(t.keysize))
    }

    // store new key/value at insert position
    if t.indirectkey() {
        kmem := newobject(t.key)
        *(*unsafe.Pointer)(insertk) = kmem
        insertk = kmem
    }
    if t.indirectvalue() {
        vmem := newobject(t.elem)
        *(*unsafe.Pointer)(val) = vmem
    }
    typedmemmove(t.key, insertk, key)
    //将高八位hash值存储
    *inserti = top
    h.count++
    return val
}
点赞 0
收藏 1
分享
该文章收录于 Go语言开发基础到通关
2 订阅 26 篇文章

0 条评论

请先 登录 后评论
天涯学馆
天涯学馆
0x9d6d...50d5
资深大厂程序员，12年开发经验，致力于探索前沿技术！

天涯学馆

如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！