go数据结构之slice与map

这篇具有很好参考价值的文章主要介绍了go数据结构之slice与map。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1. 切片

1. 切片结构定义

type slice struct {
	array unsafe.Pointer
	len   int
	cap   int
}
  • array:引用的底层数组,动态数组,可以修改
    • 如果多个切片的array指针指向同一个动态数组,则它们都可以对底层这个动态数组元素进行修改。
  • len::长度
  • cap:可以理解为底层动态数组的容量
    • 当切片添加的元素超过cap后,会引发切片底层数组扩容。扩容后array指针指向可能会发生更改

2. 切片有长度

package main

import "fmt"

func main() {
	slice1 := make([]int, 0, 4)
	fmt.Println(len(slice1))
	// panic
	slice1[0] = 1
}
  • 使用下标访问切片,访问范围不能超过切片len

2. 底层动态数组可能会被多个切片引用

package main

import "fmt"

func main() {
	slice1 := make([]int, 4, 8)
	// 4   8
	fmt.Println(len(slice1), " ", cap(slice1))

	slice2 := slice1[2:]
	// 2   6
	fmt.Println(len(slice2), " ", cap(slice2))
}
  • 上述例子中两个切片引用的是同一个底层动态数组,slice1是从动态数组头部开始引用,而slice2则是从动态数组第二个元素开始引用
  • 所以slice1能对底层动态数组全部八个位置都可以修改,而slice2则只能修改底层数组的后六位下标的位置
  • 当底层动态数组只要有一个切片引用,则整个动态数组就不会被回收,即使这个切片引用的是动态数组的局部
    • 如slice2引用会导致整个动态数组八位不能回收,虽然它只能访问和修改后六位

3. 函数中,切片是值传递

package main

import "fmt"

func main() {
	s1 := make([]int, 4, 8)
	fmt.Printf("s1的指针是 %p \n", &s1)
	printPoint(s1)

	fmt.Printf("s1的底层数组是 %p \n", s1)
	printArrPoint(s1)
}
func printPoint(s2 []int) {
	fmt.Printf("s2的指针是 %p \n", &s2)
}

func printArrPoint(s2 []int) {
	fmt.Printf("s2的底层数组是 %p \n", s2)
}
//s1的指针是 0xc000008078
//s2的指针是 0xc000008090 
//s1的底层数组是 0xc000014240 
//s2的底层数组是 0xc000014240 
  • 函数传递切片的时候,其实是把切片复制了一遍
  • 但是两个切片指向了同一个底层动态数组

4. 当切片扩容时,(可能)会指向新的底层数组

package main

import "fmt"

func main() {
	s1 := make([]int, 4, 4)
	s2 := s1
	fmt.Printf("s1的底层数组是 [%p], 容量是 [%v]\n", s1, cap(s1))
	fmt.Printf("s2的底层数组是 [%p], 容量是 [%v]\n", s2, cap(s2))

	s1 = append(s1, 1)
	fmt.Printf("s1的底层数组是 [%p], 容量是 [%v]\n", s1, cap(s1))
	fmt.Printf("s2的底层数组是 [%p], 容量是 [%v]\n", s2, cap(s2))
}
//s1的底层数组是 [0xc000150020], 容量是 [4]
//s2的底层数组是 [0xc000150020], 容量是 [4]
//s1的底层数组是 [0xc0001200c0], 容量是 [8]
//s2的底层数组是 [0xc000150020], 容量是 [4]
  • 当指向同一个底层数组时,s1对数组元素的修改对s2是可见的,当s1指向新的底层数组时,s1则对数组元素的修改则对s2是不可见了,因为它俩指向了不同的底层动态数组

5. 与空比较

package main

import "fmt"

func main() {
	var a []int
	b := make([]int, 0)
	fmt.Printf("a==nil? %v \n", a == nil)
	fmt.Printf("b==nil? %v \n", b == nil)
	fmt.Printf("len(a)==0? %v \n", len(a))
	fmt.Printf("len(b)==0? %v \n", len(b))
	fmt.Printf("a的指针是 [%p]\n", &a)
	fmt.Printf("b的指针是 [%p]\n", &b)
	fmt.Printf("a的底层数组是 [%p]\n", a)
	fmt.Printf("b的底层数组是 [%p]\n", b)
}

//a==nil? true
//b==nil? false 
//len(a)==0? 0 
//len(b)==0? 0 
//a的指针是 [0xc000008078]
//b的指针是 [0xc000008090]
//a的底层数组是 [0x0]
//b的底层数组是 [0xe6b438]

  • 切片只声明未初始化则不会分配底层数组
  • 切片可以和 nil 进行比较,只有当切片底层数据指针为空时切片本身为 nil,这时候切片的长度和容量信息将是无效的。如果有切片的底层数据指针为空,但是长度和容量不为 0 的情况,那么说明切片本身已经被损坏了。

2. map

1. map底层数据结构

type hmap struct {
	count     int              // map 中键值对的数量
	flags     uint8            // map 的标志位,如是否为引用类型等
	B         uint8            // map 的桶大小的对数
	noverflow uint16           // 溢出桶的数量
	hash0     uint32           // 哈希种子值
	buckets   unsafe.Pointer   // 存储桶的指针
	oldbuckets unsafe.Pointer   // 旧桶的指针,用于扩容时的过渡
	nevacuate uintptr          // 扩容时,已迁移的桶的数量
	extra     *mapextra        // 用于存储特殊情况下的扩展信息
}
type mapextra struct {
	overflow    *[]*bmap        // 溢出桶的数组,当哈希表中的键值对数量超过某个阈值时会使用溢出桶
	oldoverflow *[]*bmap        // 旧溢出桶的数组,用于扩容时的过渡
	nextOverflow *bmap          // 链接下一个溢出桶的指针
}
type bmap struct {
	tophash [bucketCnt]uint8
}

//在编译期间会产生新的结构体
type bmap struct {
    tophash [8]uint8 //存储哈希值的高8位
    keys    [8]keytype  //key数组
    values  [8]valuetype // value数组
    pad     uintptr
    overflow *bmap   //溢出bucket的地址
}

go数据结构之slice与map,go,golang,数据结构,算法

  1. map的底层结构时 hmap
  2. 桶数组中每个桶可以存储8个元素,超过了则使用overflow链接到下一个桶(溢出桶),所以使用的是链接法

2. get操作

go数据结构之slice与map,go,golang,数据结构,算法

  1. 首先通过hash函数计算key的哈希值
  2. 通过后B位来定位到哪个桶
  3. 定位到桶之后,首先通过hash值高8位去便利tophash数组(起到一种加速的作用),找到对应的下标i。
  4. 然后比较keys[i]==key,如果为true,则返回values[i]
  5. 如果没有找到,则继续便利tophash数组,找到下一个符合的下标i,重复3,4两步
  6. 如果都没有找到,则去溢出桶里寻找

3. tophash数组的作用

  • 主要起到加速的作用
  • tophash数组是值数组,每个元素物理位置连续
  • 而key数组不一定是值数组,如果key是字符串,则key数组里的元素其实存的不是字符串内容本身,而是一个引用。我们需要再根据这个引用(指针)找到字符串去比较。
  • 所以如果只根据key数组去比较的话,则这个过程中访问的内存地址其实不是连续的,速度会慢很多。

4. put操作

go数据结构之slice与map,go,golang,数据结构,算法

  • 先根据key进行查找(过程跟get差不多),如果找到了,则替换value
  • 如果没找到,定位到对应的桶,找到一个空闲的位置i,进行插入(三个数组对应下标i处都要插入)
  • 如果对应桶没有空闲位置,则通过overflow插入到溢出桶中
  • 必要时可能会引发扩容

5. 等量扩容

go数据结构之slice与map,go,golang,数据结构,算法

  • 当不停地在map中put和delete操作,导致一个桶的溢出桶链很长,但是每个桶里面key存的断断续续也不是很多的时候,会出发等量扩容。
  • 所谓等量扩容本不是真的扩容了,而是碎片整理,将key都整理到一起去
  • 这种情况下元素会发生重排,但不会产生新的桶(正常桶和溢出桶)

6. 二倍扩容

go数据结构之slice与map,go,golang,数据结构,算法

  • 正常桶的桶数组大小会翻倍
  • 存储的元素会重排,元素所在的桶数组下标可能会改变
  • 比如扩容前B=2,扩容后B=3,之前根据key的hash后两位定位,现在看hash的后三位定位。所以对于一个key它新的同下标要么还是原来的 i,要么就是i+len(原来桶数组)

7. 扩容条件

  • 当装载因子大于6.5时扩容(ladFactor=count/(2^B)
  • 当溢出桶过多时会扩容
    • B<15时,溢出桶数量超过2^B
    • B>=15时,溢出同数量超过2^15

8. 在函数中,也是值传递

  • 跟切片一样,在函数中也是值传递
  • 但是由于底层共享存储结构,所以函数中对map内容修改,出了函数仍是可见

9. map只能与nil比较

package main

import "fmt"

func main() {
	a := make(map[string]int, 0)
	// false
	fmt.Println(a == nil)

	var b map[string]int
	// true
	fmt.Println(b == nil)
}

  • 且只有当map底层数据结构未初始化的时候map==nil才为true

参考:https://juejin.cn/post/7029679896183963678#heading-1文章来源地址https://www.toymoban.com/news/detail-536547.html

到了这里,关于go数据结构之slice与map的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【Go基础】加密算法和数据结构

    加密过程的每一步都是可逆的 加密和解密用的是同一组密钥 异或是最简单的对称加密算法 DES(Data Encryption Standard)数据加密标准,是目前最为流行的加密算法之一 对原始数据(明文)进行分组,每组64位,最后一组不足64位时按一定规则填充,每一组上单独施加DES算法 DES子

    2024年02月02日
    浏览(30)
  • 慕课网Go-2.数组、slice、map、list

    2024年02月15日
    浏览(40)
  • Go后端开发 -- 数组 && slice && map && range

    go中的数组是固定长度的; 声明数组 Go 语言数组声明需要指定元素类型及元素个数,语法格式如下: 例如: 初始化数组 初始化数组中 {} 中的元素个数不能大于 [] 中的数字。 如果忽略 [] 中的数字不设置数组大小,Go 语言会根据元素的个数来设置数组的大小: 以下实例读取

    2024年01月17日
    浏览(47)
  • 【数据结构与算法】C++的STL模板(迭代器iterator、容器vector、队列queue、集合set、映射map)以及算法例题

    更多算法例题链接: 【数据结构与算法】递推法和递归法解题(递归递推算法典型例题) 什么是迭代器(iterator) 迭代器(iterator)的定义: 迭代器是一种检查容器内元素并遍历元素的数据类型。 迭代器提供对一个容器中的对象的访问方法,并且定义了容器中对象的范围。 容器

    2024年04月14日
    浏览(48)
  • 「数据结构」Map&Set

    🎇 个人主页 :Ice_Sugar_7 🎇 所属专栏 :Java数据结构 🎇 欢迎点赞收藏加关注哦! Map和Set是专门用来进行搜索的容器或者数据结构,它们适合动态查找(即在查找时可能会进行一些插入和删除的操作) 我们一般把搜索的数据称为 (Key) ,和对应的称为 值(

    2024年02月22日
    浏览(48)
  • [数据结构]-map和set

    前言 作者 : 小蜗牛向前冲 名言 : 我可以接受失败,但我不能接受放弃   如果觉的博主的文章还不错的话,还请 点赞,收藏,关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正   目录 一、键值对 二、set 1、set的基本知识 2、set的使用  三、map 1、map的基本

    2024年02月04日
    浏览(57)
  • golang返回多层结构数据

    正常情况下,查询出的结果,基本上都是结构体所得 如图所表示,基本上查询出的两个结果 返回结果 比较好的办法是,data1和data2和data3等多个都包含在一个data里面,然后这个data和msg,以及code同一层级,而不是data1和data2和data3这些和msg以及code同一层级 解决办法: 可以事先

    2024年01月22日
    浏览(37)
  • 【数据结构】Golang 实现单链表

    通过指针将一组零散的内存块串联在一起 , 把内存块称为链表的“ 结点 ”。 记录下个结点地址的指针叫作 后继指针 next ,第一个结点叫作 头结点 ,把最后一个结点叫作 尾结点 。 定义单链表 在 golang 中可以通过结构体定义单链表: 操作单链表 使用 golang 实现单链表常用

    2024年02月10日
    浏览(41)
  • ES6 Map数据结构

    ES6 提供的另一种新的引用类型的数据结构 它类似于对象,也是键值对的集合,但是 “键”的范围不限于字符串 ,各种类型的值(包括对象)都可以当作键) 以前引用类型中的 对象也是键值对的集合 但是键限于字符串 总结起来就是: Object 结构提供了“字符串—值”的对

    2024年02月07日
    浏览(37)
  • ES6: Map数据结构

    概念: 类似于对象,也是键值对的集合,但是“键”的范围不限于字符串,各种类型的值(包括对象)都可以当作键。 初识Map 实例的属性和方法 size:返回 Map 结构的成员总数。 Map.prototype.set(key,value) :添加key对应的value,返回 Map 结构本身。 Map.prototype.get(key) :获取key对应的

    2024年02月16日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包