本站首页 收藏本站
广告位联系

APP正在开发中...
返回顶部
您的位置： 主页 > 脚本 > Golang >

收藏
分享到

Golang Map简介以及底层原理介绍

Golang 来源：互联网 作者：佚名 发布时间：2024-10-18 22:36:51 人浏览
摘要

在Go语言中提供了map数据结构来存储键值对数据。map的数据类型为map[K]V，其中K为键的类型，V为值的类型。map的键类型必须支持==操作符，用来比较两个键是否相等。Go语言提供了4种内置的map操

在Go语言中提供了map数据结构来存储键值对数据。map的数据类型为map[K]V，其中K为键的类型，V为值的类型。map的键类型必须支持==操作符，用来比较两个键是否相等。Go语言提供了4种内置的map操作: len、delete、comparison、assign。

Map 定义

1

2

3

4

map_var := make(map[K]V) // 用make函数创建一个空的map，其中K和V分别为键和值的类型

map_var[key] = value // 向map中添加一个键值对

value := map_var[key] // 获取指定键的值

delete(map_var, key) // 从map中删除指定的键及其对应的值

Map Iteration

Go语言提供了两个方法来遍历map中的所有键值对，分别是range方法和Len()方法。

1

2

3

4

5

6

7

8

// 使用range循环遍历map中的所有键值对

for key, value := range map_var {

// TODO ...

}

// 计算map中的元素数量

if len(map_var) > 0 {

// TODO ...

}

Map 的线程安全

在Go语言中，map是非线程安全的，在多线程并发访问时可能导致程序报错。当map被多个协程同时访问时，我们需要使用sync包中的sync.Mutex来确保操作的原子性和并发安全。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

import "sync"

type SafeMap struct {

mu sync.Mutex

m map[string]int

}

func (sm *SafeMap) Get(key string) int {

sm.mu.Lock()

defer sm.mu.Unlock()

return sm.m[key]

}

func (sm *SafeMap) Set(key string, value int) {

sm.mu.Lock()

defer sm.mu.Unlock()

sm.m[key] = value

}

func (sm *SafeMap) Delete(key string) {

sm.mu.Lock()

defer sm.mu.Unlock()

delete(sm.m, key)

}

map 底层原理

Go语言的map在设计上是一种哈希表的数据结构。它利用哈希函数将键映射到不同的存储空间，从而实现高效的查找和插入操作。

哈希函数

哈希函数将字符串映射到一个整数上，这称为哈希值。不同的字符串可能会有相同的哈希值，但相同的字符串必定具有相同的哈希值。哈希函数需要满足两点：

  • 哈希函数的计算结果必须是非负整数，因为负数无法在数组中表示。

  • 两个不同字符串的哈希值尽量不要相等，这样可以避免在查找时产生冲突。

在Go语言中，字符串的哈希函数采用的是FNV-1哈希算法，算法代码如下：

1

2

3

4

5

6

7

8

9

10

11

12

const (

offset64 = 14695981039346656037

prime64 = 1099511628211

)

func stringHash(s string) uint64 {

h := uint64(offset64)

for i := 0; i < len(s); i++ {

h ^= uint64(s[i])

h *= prime64

}

return h

}

哈希冲突

在哈希表中，哈希值相同的多个字符串可能会存储在同一个位置上，这种现象叫做哈希冲突。哈希冲突处理策略有开放寻址法、再哈希法和链地址法。

  • 开放寻址法：将发生冲突的条目逐个检索新的空棑直到找到一个空位置来存储当前键值对

  • 再哈希法：对于发生冲突的键，用另一个不同的哈希函数计算地址

  • 链地址法：对于发生冲突的键，将其存储在一个链表中

Go语言使用链地址法处理哈希冲突。对于每个存储单元，map结构体中还维护了一个[]keyValue类型的链表。

1

2

3

4

5

6

type hmap struct {

count int // 映射中的键值对数量

flags uint8 // 控制哈希表的一些属性

B uint8 // 用于计算哈希地址的初始大小

noverflow uint16 // 链表上的溢出桶的数量

}

Growing

在Go语言中，动态数组会自动地为map分配更多的空间。Growing过程涉及到将原始的数组重新复制到一个更大的数组中，其中原数组的元素需要重新计算其在新数组中的位置，而新数组的元素则需要将其键值对填充到相应的位置。Growing的过程比较复杂，可以由函数hashGrow()来控制。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

// hashGrow() 将map的数组的大小翻倍，并处理哈希冲突。

func hashGrow(h *hmap) {

// ...

buf := make([]keyValue, newCap)

//...

for i := uintptr(0); i < cap; i++ {

// ...

evacuate(h, &h.oldbuckets[i], &buf)

// ...

}

// ...

}

// evacuate() 将一个bucket中的键值对重新映射到新的数组中

func evacuate(h *hmap, oldbuck *bucket, newbuck *[]keyValue) {

// ...

}

map扩容

双倍扩容

Go语言中的哈希表在map的数组容量达到一定程度时，就会自动进行扩容。扩容的依据是当前已存储的元素数量和数组的长度之间的比值：

  • 当map的已存储元素数量小于map数组长度的一半时，元素的数量未达到哈希表效率的最大值，无需扩容；

  • 当map已存储的元素数量大于等于map数组长度的一半时，哈希表的查找效率已达到最大值，所以需要扩容。

Go语言的map会优先选择数组大小为原数组大小的2倍，以确保map在存储过程中有足够的空间存放新的元素。当元素数量达到85%时，Go语言就会再次对数组进行扩容，此时数组长度翻倍，以保证数组长度和元素数量的比例始终维持在0.75左右，以平衡效率和空间占用。

Growing过程

当映射中的元素数量超过85%时，Go语言就会触发map的扩容过程。在扩容的过程中，map会将原有的元素复制到新的数组中，并将新数组的初始大小设置为原数组的2倍。对于发生哈希冲突的元素，需要在新的数组中重新计算哈希地址。

避免溢出

当数组中元素的数量超过0x7fffffff(2^31-1，即int类型的最大值)时，就会发生溢出，此时数组的大小将无法达到原数组的2倍。所以Go语言会在初始创建map时，为其初始化一个较小的数组，并设置map的B值，以便在元素数量超过限制时再次进行扩容。当map中元素的数量超过阈值时，会再次翻倍，直到数组大小小于0x7fffffff为止。

代码分析

hashmap.go包含在Go语言源码中的src/container/map.go文件中。其中map结构体的定义和Growing实现都在runtime包中，在src/runtime/map.go文件中。

附录

  • 为什么哈希表的容量要设置为2的n次幂？为什么不是其他数字？

  • Go语言中的map是如何进行线程安全的？原理是什么？

  • map的数据结构是怎样的？如何实现键值对的查找、添加、删除操作？

  • 如何实现Growing过程？

  • 为什么map的扩容条件是85%，而不是100%？

  • 在go语言中如何创建map？

  • 为什么哈希冲突处理策略有开放寻址法、再哈希法和链地址法？

  • 如果存在冲突，键值对是如何存储在数组中的？

  • 为什么Growing过程中会创建一个较大的临时数组，而不是直接在原数组上扩展空间？

  • 如何实现map的迭代？
版权声明 : 本文内容来源于互联网或用户自行发布贡献，该文观点仅代表原作者本人。本站仅提供信息存储空间服务和不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权， 违法违规的内容， 请发送邮件至2530232025#qq.cn(#换@)举报，一经查实，本站将立刻删除。

您可能感兴趣的文章 :

原文链接 :
相关文章
  • golang并发编程使用Select语句的实现介绍
    在 Go 语言中，select语句是一种控制结构，允许一个 Goroutine 同时等待多个通道操作。select语句会阻塞，直到其中的一个case可以继续执行，然
  • go语言time.After()的作用介绍
    time.After是一个非常实用的函数，它返回一个用于读取的单向通道（-chan time.Time），这个通道会在指定的时间间隔之后发送当前时间。这个机
  • go实现一个内存缓存系统的代码
    面试内容： 支持设定过期时间，精度到秒 支持设定最大内存，当内存超出时做出合适的处理 支持并发安全 要求按照以下接口实现 1 2 3 4
  • Golang Map简介以及底层原理介绍
    在Go语言中提供了map数据结构来存储键值对数据。map的数据类型为map[K]V，其中K为键的类型，V为值的类型。map的键类型必须支持==操作符，用
  • Go语言中的switch高级用法介绍
    最近翻开源代码的时候看到了一种很有意思的switch用法，分享一下。 注意这里讨论的不是typed switch，也就是case语句后面是类型的那种。 直
  • Go语言sync.Map介绍及使用场景
    在 Go 语言中，sync.Map是一个并发安全的映射结构，专门用于在高并发场景下处理键值对数据。它的并发安全是通过内部实现机制来保证的，
  • 怎么使用工具自动监测SSL证书有效期并发送提醒
    自从云厂商的免费ssl证书改成3个月，而且证书数量还是20个之后，自己网站的ssl证书就换成了其它免费方案。但是免费方案不会提醒证书过

  • Go语言字符串处理库strings包介绍

    Go语言字符串处理库strings包介绍
    Golang字符串处理库strings 在Go语言中，strings包是一个非常重要且功能丰富的标准库，它提供了一系列用于操作字符串的函数。从基本的字符串
  • Go语言中的指针的使用介绍
    1、Go 语言中指针的介绍 1.1、什么是指针？ 指针是一种变量，它存储了另一个变量的内存地址。在 Go 中，你可以通过取地址操作符获取变量

  • Go环境变量配置，及GOROOT、GOPATH的区别

    Go环境变量配置，及GOROOT、GOPATH的区别
    一、安装Go go下载地址： https://golang.google.cn/dl/ windows下载安装，有两种方式。解压和直接安装 方式一：直接下载安装包。以.msi结尾的文件。
推荐阅读
最新更新
友情链接
  • 本站所有内容来源于互联网或用户自行发布，本站仅提供信息存储空间服务，不拥有版权，不承担法律责任。如有侵犯您的权益，请您联系站长处理！
  • Copyright © 2017-2022 F11.CN All Rights Reserved. F11站长开发者网 版权所有 | 苏ICP备2022031554号-1 | 51LA统计