golang map（golang变量(二)——map和slice详解）
- golang变量(二)——map和slice详解
- goland map底层原理
- golang中map能嵌套map吗
- golang中map的key的类型
- golang 从 map 获取值时的值拷贝问题
- golang hashmap的使用及实现
- Golang 并发读写map安全问题详解
衍生类型，interface{} , map, ，struct等
map类似于java的hashmap，python的dict，php的hash array。
常规的for循环，可以用for k,v :=range m {}. 但在下面清空有一个坑注意：
著名的map*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中，但如果使用不好，会有下面的问题：
预期是，但实际结果是：
注意slice是值传递，修改一下：
输出如下：
== 只能用于判断常规数据类型，无法使用用于slice和map判断，用于判断map和slice可以使用reflect.DeepEqual，这个函数用了递归来判断每层的k，v是否一致。
当然还有其他方式，比如转换成json，但小心有一些异常的bug，比如html编码，具体这个json问题，待后面在分析。
map 是Go语言中基础的数据结构，在日常的使用中经常被用到。但是它底层是如何实现的呢？
总体来说golang的map是hashmap，是使用数组+链表的形式实现的，使用拉链法消除hash冲突。
golang的map由两种重要的结构，hmap和bmap(下文中都有解释)，主要就是hmap中包含一个指向bmap数组的指针，key经过hash函数之后得到一个数，这个数低位用于选择bmap(当作bmap数组指针的下表)，高位用于放在bmap的uint8数组中，用于快速试错。然后一个bmap可以指向下一个bmap(拉链)。
Golang中map的底层实现是一个散列表，因此实现map的过程实际上就是实现散表的过程。在这个散列表中，主要出现的结构体有两个，一个叫 hmap (a header for a go map)，一个叫 bmap (a bucket for a Go map，通常叫其bucket)。这两种结构的样子分别如下所示：
hmap :
图中有很多字段，但是便于理解map的架构，你只需要关心的只有一个，就是标红的字段： buckets数组 。Golang的map中用于存储的结构是bucket数组。而bucket(即bmap)的结构是怎样的呢？
bucket ：
相比于hmap，bucket的结构显得简单一些，标红的字段依然是“核心”，我们使用的map中的key和value就存储在这里。“高位哈希值”数组记录的是当前bucket中key相关的“索引”，稍后会详细叙述。还有一个字段是一个指向扩容后的bucket的指针，使得bucket会形成一个链表结构。例如下图：
由此看出hmap和bucket的关系是这样的：
而bucket又是一个链表，所以，整体的结构应该是这样的：
哈希表的特点是会有一个哈希函数，对你传来的key进行哈希运算，得到唯一的值，一般情况下都是一个数值。Golang的map中也有这么一个哈希函数，也会算出唯一的值，对于这个值的使用，Golang也是很有意思。
Golang把求得的值按照用途一分为二：高位和低位。
如图所示，蓝色为高位，红色为低位。 然后低位用于寻找当前key属于hmap中的哪个bucket，而高位用于寻找bucket中的哪个key。上文中提到：bucket中有个属性字段是“高位哈希值”数组，这里存的就是蓝色的高位值，用来声明当前bucket中有哪些“key”，便于搜索查找。 需要特别指出的一点是：我们map中的key/value值都是存到同一个数组中的。数组中的顺序是这样的:
并不是key0/value0/key1/value1的形式，这样做的好处是：在key和value的长度不同的时候，可 以消除padding(内存对齐)带来的空间浪费 。
现在，我们可以得到Go语言map的整个的结构图了：(hash结果的低位用于选择把KV放在bmap数组中的哪一个bmap中，高位用于key的快速预览，用于快速试错)
map的扩容
当以上的哈希表增长的时候，Go语言会将bucket数组的数量扩充一倍，产生一个新的bucket数组，并将旧数组的数据迁移至新数组。
加载因子
判断扩充的条件，就是哈希表中的加载因子(即loadFactor)。
加载因子是一个阈值，一般表示为：散列包含的元素数 除以 位置总数。是一种“产生冲突机会”和“空间使用”的平衡与折中：加载因子越小，说明空间空置率高，空间使用率小，但是加载因子越大，说明空间利用率上去了，但是“产生冲突机会”高了。
每种哈希表的都会有一个加载因子，数值超过加载因子就会为哈希表扩容。
Golang的map的加载因子的公式是：map长度 / 2^B(这是代表bmap数组的长度，B是取的低位的位数)阈值是6.5。其中B可以理解为已扩容的次数。
当Go的map长度增长到大于加载因子所需的map长度时，Go语言就会将产生一个新的bucket数组，然后把旧的bucket数组移到一个属性字段oldbucket中。注意：并不是立刻把旧的数组中的元素转义到新的bucket当中，而是，只有当访问到具体的某个bucket的时候，会把bucket中的数据转移到新的bucket中。
如下图所示：当扩容的时候，Go的map结构体中，会保存旧的数据，和新生成的数组
上面部分代表旧的有数据的bucket，下面部分代表新生成的新的bucket。蓝色代表存有数据的bucket，橘黄色代表空的bucket。
扩容时map并不会立即把新数据做迁移，而是当访问原来旧bucket的数据的时候，才把旧数据做迁移，如下图：
注意：这里并不会直接删除旧的bucket，而是把原来的引用去掉，利用GC清除内存。
map中数据的删除
如果理解了map的整体结构，那么查找、更新、删除的基本步骤应该都很清楚了。这里不再赘述。
值得注意的是，找到了map中的数据之后，针对key和value分别做如下操作：
1
2
3
4
1、如果``key``是一个指针类型的，则直接将其置为空，等待GC清除；
2、如果是值类型的，则清除相关内存。
3、同理，对``value``做相同的操作。
4、最后把key对应的高位值对应的数组index置为空。
自然是可以的，当然map不能作为另一个map的key，只能做value。请参考以下例子：
package?main
import?“fmt“
type?t_classmates?mapint
func?main()?{
??domitory?:=?make(mapt_classmates)
??class1?:=?make(t_classmates)
??class1?=?23
??class1?=?24
??domitory?=?class1
??domitory?=?t_classmates{“wangwu“:?25,?“zhaoliu“:?26,}
??fmt.Println(domitory)
}
golang 中 map 的 key 必须是可比较的，再简单点是可以使用 == 运算符进行比较。
很显然 slice，map，function 不可以，
所以 数字、string、bool、array、channel、指针可以，以及 包含前面类型的 struct
leetcode 49 题 所以恰好要取一个 string 的 hash 值，题解中大神云集，各种质数相乘，字符排序后作为 key 的，更有甚者将数组作为 key，我觉得很巧妙都很巧妙。
我们知道 golang 中，slice， map， channel 是引用类型，函数之间传递都是以值拷贝的形式进行的，引用类型经过函数传递，依然是引用类型。
在上述例子中，我们从 map 中想拿出一个值，这个值是一个简单结构体，拿出这个值后，不确定这个值和 map 中的值是什么关系，如果不小心修改，是否会造成 map 值变更。
我们希望 golang 中更多的是值传递，这样能避免数据存储在堆上，造成 gc 负担。
可以看到，修改值后，map 中的值保持不变。说明 map 获取的值也是值传递出来的。
由于go语言是一个强类型的语言，因此hashmap也是有类型的，具体体现在key和value都必须指定类型，比如声明一个key为string，value也是string的map，
需要这样做
大部分类型都能做key，某些类型是不能的，共同的特点是： 不能使用== 来比较，包括: slice, map, function
在迭代的过程中是可以对map进行删除和更新操作的，规则如下：
golang的map是hash结构的，意味着平均访问时间是O(1)的。同传统的hashmap一样，由一个个bucket组成:
那我们怎么访问到对应的bucket呢，我们需要得到对应key的hash值
各个参数的意思：
目前采用的是这一行:
| 6.50 | 20.90 | 10.79 | 4.25 | 6.50 |
下面先写一段测试程序，然后看下运行结果：
运行结果：
发生了错误，提示：fatal error: concurrent map read and map write， map 发生了同时读和写了； 但是这个错误并不是每次运行都会出现，就是有的时候会出现，有的时候并不会出现，根据笔者多次运行结果(其他例子，读者可以自己尝试下)来看还会有另外一种报错就是：fatal error: concurrent map writes，就是map发生了同时写，但是只是读是不会有问题的。关于不同的运行结果小伙伴们可以自己写几个例子去测试下。下面就这两个错误的发生，笔者给出如下解释：
（1） fatal error: concurrent map read and map write
就是当一个goroutine在写数据，而同时另外一个goroutine要读数据就会报错，不过这个报错也很好理解：还没写完就读，读的数据会有问题，或者反过来还没读完就开始写了，同样会导致读取的数据有问题；
（2） fatal error: concurrent map writes
两个goroutine 同时写一个内存地址，这种操作也是不允许的，会导致一些比较奇怪的问题；
总体来看其实就是写map的操作和其他的读或者写同时发生了，导致的报错，做过几年开发的人可能会想到使用锁来解决，比如写map某个key的时候，通过锁来保证其他goroutine不能再对其写或者读了。
实现思路：
（1） 当写map的某个key时，通过锁来保证其他goroutine不能再对其写或者读了。
（2） 当读map的某个key时，通过锁来保证其他的goroutine不能再对其写，但是可以读。
于是我们马上想到golang 的读写锁貌似符合需求，下面来实现下：
再来看下运行结果：
发现没有报错了，并且多次运行的结果都不会报错，说明这个方法是有用的，不过在go1.9版本后就有sync.Map了，不过这个适用场景是读多写少的场景，如果写很多的话效率比较差，具体的原因在这里笔者就不介绍了，后面会写篇文章详细介绍下。
今天的文章就到这里了，如果有不对的地方欢迎小伙伴给我留言，看到会即时回复的。
