响应式网站生成,企业vi设计案例欣赏,公司没有自己的网站,可以做免费推广的网站吗#xff08;一#xff09;基础操作
版本#xff1a;Go SDK 1.20.6
1、初始化
map分别支持字面量初始化和内置函数make()初始化。
字面量初始化#xff1a; m : map[string] int {apple: 2,banana: 3,}使用内置函数make()初始化#xff1a; m …一基础操作
版本Go SDK 1.20.6
1、初始化
map分别支持字面量初始化和内置函数make()初始化。
字面量初始化 m : map[string] int {apple: 2,banana: 3,}使用内置函数make()初始化 m : make(map[string]int,10) // 指定容量可以有效减少内存分配次数有利于提升程序性能m[apple] 2m[banana] 3注意未初始化的map变量的默认值为nil向值为nil的map添加元素时会触发panicassignment to entry in nil map赋值给空的map如 var m map[string]intm[apple] 2 // 触发panic 2、增删改查
map的增删改查比较随意… m : make(map[string]int,10)m[apple] 2 // 添加m[apple] 3 // 修改delete(m,apple) // 删除v : m[apple] // 查询v,exist : m[apple] // 查询if exist {fmt.Println(v)}
这里有几个需要注意的地方
在上面的修改操作中如果键apple不存在则会直接执行添加操作。删除元素使用内置函数delete()完成delete()没有返回值在map为nil或指定的键不存在的情况下delete()也不会报错相当于空操作。如果使用的是第一种方式查询当key不存在时会返回value对应的零值比如上面会返回0。当使用第二种时第一个变量为值第二个为bool类型的变量用于指示是否存在指定的键如果键不存在那么第一个值为同样为对应零值。map操作不是原子的当多个协程同时操作map时有可能会产生读写冲突读写会触发panic
内置函数len()可以查询map的长度该长度反应map中存储的键值对数。
二实现原理
1、数据结构
Go语言的map使用Hash表作为底层实现一个Hash表里可以有多个bucket而每个bucket保存了map中的一个或一组键值对。
1map的数据结构
map的数据结构由 runtime/map.go:hmap 定义
type hmap struct {count int // 当前保存的元素个数flags uint8 // 状态标志B uint8 // bucket 数组的大小noverflow uint16 // 溢出桶的大概数量hash0 uint32 // 哈希种子buckets unsafe.Pointer // bucket 数组数组的长度为2^Boldbuckets unsafe.Pointer // 老旧bucket数组用于扩容nevacuate uintptr // 表示扩容进度小于此地址的buckets代表已搬迁完成extra *mapextra // optional fields
}下图展示了一个hmap.B2t的map。 2bucket的数据结构
bucket桶数据结构由runtime/map.go:bmap定义
type bmap struct {tophash [bucketCnt]uint8 // 长度为8的数组
}
// 底层定义的常量
const (bucketCntBits 3bucketCnt 1 bucketCntBits // 一个桶最多有8个位置
)这是我在书上看到的bucket数据结构并做出了如下解释 bucket数据结构中的data和overflow成员并没有显示地在结构体中声明运行时在访问bucket时直接通过指针的偏移量来访问这些虚拟成员
type bmap struct {tophash [8]uint8 // 存储Hash值的高8位data []byte // key value 数据key/key/key/.../value/value/value...overflow *bmap // 溢出bucket的地址
}每个bucket可以存储8个键值对
tophash 是一个长度为8的整型数组Hash值低位相同的键存入当前bucket时会将Hash值的高位存储在数组中以方便后续匹配。data 区存放的是key-value数据存放顺序是 key/key/key/…/value/value/value如此存放是为了节省字节对齐带来的空间浪费。overflow 指针指向的是下一个bucket据此将所有冲突的键连接起来。
所以tophash到底有什么用 具体来说如果两个键的哈希值的低位相同但高位不同它们可能会被映射到同一个桶位置。为了区分它们可以将高位存储在 tophash[i] 数组中。这样在查找时可以首先比较低位哈希值如果相等再比较高位以确保正确地匹配到相应的键。 在这种情况下当添加元素时如果 tophash[i] 中存储的哈希值与当前 key 的哈希值不相等可能表示哈希冲突。这时可能需要通过线性搜索或其他冲突解决方法在当前桶中查找匹配的键。在查找的过程中可以利用 tophash[i] 数组中的高位信息来进一步确保正确匹配。 总体而言这种做法是一种提高哈希表性能的优化策略通过更多的信息来区分相同低位哈希值的键以减少哈希冲突的影响。在实现哈希表时具体的优化方法可能会因语言或库的不同而有所不同。
2、哈希冲突
当有两个或以上数量的键被“Hash”到同一个bucket时我们称这些键发生了冲突。Go使用链地址法来解决冲突。 关于哈希冲突的详细解释可以移步我的这篇博客哈希表是什么
3、负载因子
负载因子用于衡量一个Hash表冲突情况公式为 负载因子 键数量/bucket数量 负载因子过小或过大都不理想
负载因子过小说明空间利用率低。负载因子说明冲突严重存取效率低
当Hash表的负载因子过大时需要申请更多的bucket并对所有的键值对重新组织使其均匀地分布到这些bucket中这个过程称为rehash。
4、扩容
1扩容条件 为了保证访问效率降低负载因子常用的手段是扩容当新元素将要添加进map时会判断是否需要扩容。 触发扩容需要满足以下任一条件
平均负载因子大于6.5overflow的数量达到2^min(15,B)
2增量扩容 当负载因子过大时就新建一个bucket数组新的bucket数组的长度为原来的2倍然后旧bucket数组中的数据逐步搬迁到新的bucket数组中。
增量扩容的具体过程是这样的 1、新建桶数组 当触发增量扩容时Go 会创建一个新的、更大的桶数组。 2、元素迁移 然后它会逐步将旧桶中的元素重新分配到新的桶数组中避免一次性大规模的重新哈希。 3、渐进迁移 在元素逐步迁移的过程中新添加的元素会直接被放入新的桶数组中而不会立即迁移。这保证了新元素的添加不会在迁移期间导致性能下降。 4、逐步替换 最终当所有元素都成功迁移到新的桶数组后旧的桶数组会被废弃新桶数组取而代之完成了增量扩容的过程。 5、这种增量方式的扩容避免了在添加元素时出现大规模的哈希冲突或性能下降因为它避免了在一次性扩容中发生的大量元素重新哈希的操作。这种方法相对于整体性地重新哈希整个 map 来说更加有效和高效。 扩容后示意图 搬迁完成后示意图 5、增删改查
无论是元素的添加还是查询操作都需要现根据键的Hash值确定一个bucket并查询该bucket中是否存在指定的键。
对于查询操作而言查到指定的键后获取值后就返回否则返回类型的空值。对于添加操作而言查到指定的键意味着当前添加操作实际上是更新操作否则在bucket中查找一个空余位置并插入。
1查找过程
查找过程简述如下
计算 Hash 值 对于给定的 key通过哈希函数计算其对应的哈希值。确定桶位置 将计算得到的哈希值与当前 map 的桶数量 hmap.B 取模以确定 key 应该放置在哪个桶中。这个桶就是存储相应 key-value 对的地方。查找 TopHash 从 tophash 数组中获取与当前桶位置对应的 tophash[i]其中 i 是 hash (hmap.B - 1)。比较 Hash 值 如果 tophash[i] 中存储的哈希值与当前 key 的哈希值相等那么表示可能找到了对应的桶需要进一步检查。比较实际值 如果 tophash[i] 中存储的哈希值相等接下来会比较实际的 key 值。如果找到了匹配的哈希值但实际 key 不相等这可能是碰撞需要继续查找。从桶中查找 如果在当前桶中没有找到匹配的 key就需要从溢出的桶中继续查找。溢出桶是因为哈希冲突导致多个 key 映射到同一个桶的情况。返回结果 如果找到匹配的 key就返回对应的 value。如果遍历完所有相关的桶仍然没有找到匹配的 key则返回相应类型的零值。
如果当前map处于搬迁过程中则优先从oldbuckets数组中查找查找到不再从新的buckets数组中查找。
2添加过程
新元素的添加过程简书如下
根据key值算出Hash值取Hash值低位与hmap.B取模来确定bucket位置查找该key是否已经存在如果存在则直接更新值如果该key不存在则从该bucket中寻找空余位置并插入
如果当前map出于搬迁过程中则新元素会直接添加到新的buckets数组中但查找过程仍从oldbuckets数组中开始
3删除操作
删除元素实际上是先查找元素如果元素存在则把元素从相应的bucket中清除如果不存在则什么也不做
