当前位置:网站首页>深入理解Golang之Map
深入理解Golang之Map
2022-08-02 14:10:00 【星星泡个饭】
目录
写在前面
Map的实现主要有两种方式:哈希表(hash table)和搜索树(search tree)。例如Java中的hashMap是基于哈希表实现,而C++中的Map是基于一种平衡搜索二叉树——红黑树而实现的。Go中map的基于哈希表(也被称为散列表)实现。
哈希函数
哈希函数(常被称为散列函数)是可以用于将任意大小的数据映射到固定大小值的函数,它是根据关键字设计的,有很多函数,主要原理就是根据数组的大小求模运算。
(关键字)%(数组的大小)
数组的大小一般设计为质数,因为需要均匀的散布
如何解决哈希冲突的问题?
1.链表地址法
写结构体的时候加入next指针
遇到冲突时,将数据写到next的位置
下面以一个简单的哈希函数 H(key) = key MOD 7(除数取余法)对一组元素 [50, 700, 76, 85, 92, 73,101] 进行映射,通过图示来理解链地址法处理Hash冲突的处理逻辑。
2.开放地址法
把其他下标的地址都对外开放
开放地址的方法:1.线性探测法2.平方探测(二次方探测)3.双哈希
开放地址—线性探测法
如果遇到冲突,就往下一个地址寻找空位,新位置=原始位置+i ( i是查找的次数 )
其中15,2,28,4进行模运算,都为2,遇到冲突,就会往下一个地址寻找空位
12,38进行模运算,都为12,遇到冲突,就会往下一个地址寻找空位
开放地址—平方探测法
如果遇到冲突,就往(原地址 + i ² )的位置寻找空位,新位置=原始位置+ i ² ( i是查找的次数 )
开放地址—双哈希
要设置第二个哈希的函数,例如:hash2(key)=R-(key mod R)
R要取比数组尺寸小的指指数
例如R取7 hash2(关键字)=7-(关键字%7)
如果遇到冲突,新位置=原始位置+i*hash2(关键字)
哈希表满了怎么办?
再次哈希
- 当哈希表数据存储量超过70%,那么就自动新建一个新的哈希表
- 新表的尺寸是旧表的2倍以上,选择一个质数
- 把之前的数据再次通过哈希计算搬到新表里
Go Map实现
map数据结构
map中的数据被存放于一个数组中的,数组的元素是桶(bucket),每个桶至多包含8个键值对数据。哈希值低位(low-order bits)用于选择桶,哈希值高位(high-order bits)用于在一个独立的桶中区别出键。哈希值高低位示意图如下
Go语言中的map是也基于哈希表实现的,它解决哈希冲突的方式是链地址法,即通过使用数组+链表的数据结构来表达map
map的结构体为hmap
// A header for a Go map.
type hmap struct {
count int // 代表哈希表中的元素个数,调用len(map)时,返回的就是该字段值。
flags uint8 // 状态标志,下文常量中会解释四种状态位含义。
B uint8 // buckets(桶)的对数log_2(哈希表元素数量最大可达到装载因子*2^B)
noverflow uint16 // 溢出桶的大概数量。
hash0 uint32 // 哈希种子
buckets unsafe.Pointer // 指向buckets数组的指针,数组大小为2^B,如果元素个数为0,它为nil。
oldbuckets unsafe.Pointer // 如果发生扩容,oldbuckets是指向老的buckets数组的指针,老的buckets数组大小是新的buckets的1/2。非扩容状态下,它为nil。
nevacuate uintptr // 表示扩容进度,小于此地址的buckets代表已搬迁完成。
extra *mapextra // 这个字段是为了优化GC扫描而设计的。当key和value均不包含指针,并且都可以inline时使用。extra是指向mapextra类型的指针。
bmap结构体(map的桶)
// A bucket for a Go map.
type bmap struct {
// tophash包含此桶中每个键的哈希值最高字节(高8位)信息(也就是前面所述的high-order bits)。
// 如果tophash[0] < minTopHash,tophash[0]则代表桶的搬迁(evacuation)状态。
tophash [bucketCnt]uint8
}
在8个键值对数据后面有一个overflow指针,因为桶中最多只能装8个键值对,如果有多余的键值对落到了当前桶,那么就需要再构建一个桶(称为溢出桶),通过overflow指针链接起来。溢出桶的内存布局和常规桶相同,是为了减少扩容次数而引入的,当一个桶存满了还有可用的溢出桶时,就会在桶后面链一个溢出桶
边栏推荐
- What should I do if the Win10 system sets the application identity to automatically prompt for access denied?
- Win7怎么干净启动?如何只加载基本服务启动Win7系统
- win10 system update error code 0x80244022 how to do
- 基于无监督医学图像配准论文(1)
- STL容器自定义内存分配器
- Detailed explanation of RecyclerView series article directory
- STM32F1和F4的区别
- PyTorch(11)---卷积神经网络_一个小的神经网络搭建model
- DP4301无线收发SUB-1G芯片兼容CC1101智能家居
- Win11怎么在右键菜单添加一键关机选项
猜你喜欢
How to set the win10 taskbar does not merge icons
PyTorch④---DataLoader的使用
FP7195大功率零压差全程无频闪调光DC-DC恒流芯片(兼容调光器:PWM调光,无极调光,0/1-10V调光)
轻量化AlphaPose
刷卡芯片CI520可直接PIN对PIN替换CV520支持SPI通讯接口
A clean start Windows 7?How to load only the basic service start Windows 7 system
PHY6222蓝牙5.2支持MESH组网M0内核超低功耗
2020-02-06-快速搭建个人博客
How to update Win11 sound card driver?Win11 sound card driver update method
General syntax and usage instructions of SQL (picture and text)
随机推荐
PyTorch⑤---卷积神经网络_卷积层
define #使用
flink+sklearn——使用jpmml实现flink上的机器学习模型部署
FP7122降压恒流内置MOS耐压100V共正极阳极PWM调光方案原理图
为android系统添加产品的过程
Win11 system cannot find dll file how to fix
没学好统计学的下场
FP7195芯片PWM转模拟调光至0.1%低亮度时恒流一致性的控制原理
Policy Evaluation收敛性、炼丹与数学家
ECP2459耐压60V降压BUCK电路用于WIFI模块供电方案原理图
PHY6222蓝牙5.2支持MESH组网M0内核超低功耗
Mysql connection error solution
CMAKE
PyTorch②---transforms结构及用法
cmake配置libtorch报错Failed to compute shorthash for libnvrtc.so
7. How to add the Click to RecyclerView and LongClick events
Mysql连接错误解决
【深度学习中的损失函数整理与总结】
pytorch模型转libtorch和onnx格式的通用代码
boost库智能指针