go map 数据结构

Go map实现原理

创新互联是一家集网站建设,吴川企业网站建设,吴川品牌网站建设,网站定制,吴川网站建设报价,网络营销,网络优化,吴川网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。

深入Go的Map使用和实现原理

go 中的 map 也是 hashmap，由哈和(bucket)数组组成，每个 bucket 可以存放若干元素(默认8个)，当超过 8 个元素后，hmap会使用extra中的overflow指向新的 bucket 来拓展该bucket；

bucket 数组 tophash 数组 data字节数组 overflow 链表

哈希冲突后的数据结构：

overflow 表示溢出的意思

负载因子用于表示哈希冲突的情况 = 键数量 / bucket 的数量

哈希因子需要控制在合适的大小，超过阙值后需要 rehash

* 哈希因子过小，说明空间利用率低

* 哈希因子过大，说明冲突严重，存取效率低

每个 hash 表的实现对负载因子的容忍程度不同，redis 中负载因子为 1 时就会触发 rehash，因为 redis 的每个 bucket 只能存储一个键值对。而 go 的能存储 8 个，负载因子为 6.5；

4.1 扩容的前提条件

为保证访问效率，当新元素要添加时，都会检查是否需要扩容，扩容实际是空间换时间；

4.2 增量扩容

负载因子超过阙值后，新建一个 buckets，长度为原来的2倍，旧 buckets 的数量逐渐搬迁至新的 buckets 中。

如果数据量较大，采取渐进式hash， 每次访问 map 都会触发一次搬迁 ，每次搬迁2个键值对，搬迁完成后将会删除 oldbuckets；

4.3 缩容

通过不断地删除，键值对集中在一小部分地 bucket 中，overflow 中大部分是空的，经过重新组织后 bucket 的数量会减少，提高访问效率；

golang变量(二)——map和slice详解

衍生类型，interface{} , map, [] ，struct等

map类似于java的hashmap，python的dict，php的hash array。

常规的for循环，可以用for k,v :=range m {}. 但在下面清空有一个坑注意：

著名的map[string]*struct 副本问题

结果：

Go 中不存在引用传递，所有的参数传递都是值传递，而map是等同于指针类型的，所以在把map变量传递给函数时，函数对map的修改，也会实质改变map的值。

slice类似于其他语言的数组（list，array），slice初始化和map一样，这里不在重复

除了Pointer数组外，len表示使用长度，cap是总容量，make([]int, len, cap)可以预申请 比较大的容量，这样可以减少容量拓展的消耗，前提是要用到。

cap是计算切片容量，len是计算变量长度的，两者不一样。具体例子如下：

结果：

分析：cap是计算当前slice已分配的容量大小，采用的是预分配的伙伴算法（当容量满时，拓展分配一倍的容量）。

append是slice非常常用的函数，用于添加数据到slice中，但如果使用不好，会有下面的问题：

预期是[1 2 3 4 5 6 7 8 9 10]， [1 2 3 4 5 6 7 8 9 10 11 12]，但实际结果是：

注意slice是值传递，修改一下：

输出如下：

== 只能用于判断常规数据类型，无法使用用于slice和map判断，用于判断map和slice可以使用reflect.DeepEqual，这个函数用了递归来判断每层的k，v是否一致。

当然还有其他方式，比如转换成json，但小心有一些异常的bug，比如html编码，具体这个json问题，待后面在分析。

Go语言——sync.Map详解

sync.Map是1.9才推荐的并发安全的map，除了互斥量以外，还运用了原子操作，所以在这之前，有必要了解下 Go语言——原子操作

go1.10\src\sync\map.go

entry分为三种情况：

从read中读取key，如果key存在就tryStore。

注意这里开始需要加锁，因为需要操作dirty。

条目在read中，首先取消标记，然后将条目保存到dirty里。（因为标记的数据不在dirty里）

最后原子保存value到条目里面，这里注意read和dirty都有条目。

总结一下Store：

这里可以看到dirty保存了数据的修改，除非可以直接原子更新read，继续保持read clean。

有了之前的经验，可以猜测下load流程：

与猜测的 区别 ：

由于数据保存两份，所以删除考虑：

先看第二种情况。加锁直接删除dirty数据。思考下貌似没什么问题，本身就是脏数据。

第一种和第三种情况唯一的区别就是条目是否被标记。标记代表删除，所以直接返回。否则CAS操作置为nil。这里总感觉少点什么，因为条目其实还是存在的，虽然指针nil。

看了一圈貌似没找到标记的逻辑，因为删除只是将他变成nil。

之前以为这个逻辑就是简单的将为标记的条目拷贝给dirty，现在看来大有文章。

p == nil，说明条目已经被delete了，CAS将他置为标记删除。然后这个条目就不会保存在dirty里面。

这里其实就跟miss逻辑串起来了，因为miss达到阈值之后，dirty会全量变成read，也就是说标记删除在这一步最终删除。这个还是很巧妙的。

真正的删除逻辑：

很绕。。。。

本文名称：c模仿go语言中的map go语言 C语言
转载来于：http://lswzjz.com/article/dodjejh.html