Go-知识map

Go-知识map

• 1. map 的用法
• • 1.1 map 的声明
  • 1.2 map 的初始化
  • 1.3 map 的使用
  • 1.4 并发不安全
  • 1.5 空map
  • 2. map 的原理
  • • 2.1 map 的数据结构
    • 2.2 bucket 的数据结构
    • 2.3 hash 冲突
    • 2.4 负载因子
    • 3. 扩容
    • • 3.1 扩容条件
      • 3.2 增量扩容
      • 3.3 等量扩容
      • 4. map 操作
      • • 4.1 查询
        • 4.2 添加&更新
        • 4.3 删除
        • 5. ���结

          1. map 的用法

          Go 语言中map的底层使用Hash表实现，并发不安全。

          1.1 map 的声明

          map的声明可以使用普通显示声明，也可以使用简短变量声明操作符。

              a := map[string]string{}var b map[string]string

          1.2 map 的初始化

          map可以在声明的时候，直接初始化，也可以使用make操作初始化。

              a := map[string]string{"name": "zhangsan", "age": "15"}var b map[string]stringb = make(map[string]string, 10)

          使用make初始化，可以指定容量，减少扩容次数。

          1.3 map 的使用

          在Go里面对map进行增删改查很简单：

          m := make(map[string]string, 10)m["name"] = "zhangsan"       // 增加m["name"] = "李四"            // 修改delete(m, "name")            // 删除if _, ok := m["name"]; !ok { // 查询println("不存在")}

          在修改操作中，如果name不存在，那么等价于增加。

          删除元素使用内置函数delete完成，delete没有返回值，在map为nil或者指定的key不存在时，也不会报错，相当于空操作。

          在查询操作中，最多可以给两个参数赋值，第一个为值，第二个为bool变量，用于指示是否存在指定的key，如果不存在那么第一个值为相应类型的零值。

          如果只给一个变量赋值，那么只返回对应的值，如果key不存在，那么为对应类型的零值。

          1.4 并发不安全

          map的操作不是原子的，如果并发操作map，可能产生读写冲突，如果出现读写冲突那么程序直接panic。

          Go在设计map时认为大多数场景下不需要并发读写，如果为了支持并发读写而引入互斥锁，那么会降低map的性能。

          map的实现中增加读写检测机制，如果出现读写冲突，那么程序panic，避免错上加错。

          1.5 空map

          未初始化的map的值为nil，向值为nil的map增加元素会导致程序panic。

          因为修改实质上可以认为是新增操作，所以也会panic。

          func TestMap(t *testing.T) {var m map[string]stringm2 := make(map[string]string)// len 空map和nil mapfmt.Println(len(m))fmt.Println(len(m2))// deletedelete(m, "x")delete(m2, "x")// queryv, ok := m["x"]fmt.Printf("v=%s, ok=%v\n", v, ok)v2, ok2 := m2["x"]fmt.Printf("v2=%s, ok2=%v\n", v2, ok2)}

          删除和查询空map或者nil的map并不会异常，相当于空操作。

          2. map 的原理

          2.1 map 的数据结构

          Go语言的map使用Hash表作为底层实现，一个Hash表里面可以有多个bucket，每个bucket保存了map中的一个或多个Hash相同的键值对。

          map的数据结构由runtime/map.go定义：

          type hmap struct {count     int    // map的size ,也是 len(map) 返回的值flags     uint8B         uint8  // bucket 个数，哈希桶个数noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for detailshash0     uint32 // 哈希种子buckets    unsafe.Pointer // bucket 数组，长度 2^Boldbuckets unsafe.Pointer // 旧的 bucket 数组，用于扩容nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)extra *mapextra // optional fields}

          比如上面是B=2的一个map的数据结构，bucket数组长度是2^2=4，键值对的key经过Hash运算后，对4取余，就是对应的bucket中进行存储。

          bucket就是Hash桶，buckets是Hash桶数组。

          2.2 bucket 的数据结构

          bucket数据结构由runtime/map.go中的bmap定义：

          bucket有一个hash值的数组，存储hash值的高8位。

          其实bucket的数据结构中还有数据区和溢出指针，属于隐式存在的。

          type bmap struct {tophash [8]uint8  // hash 高8位数组data []byte       // key-vlaue 数据 key/key/../value/value..overflow *bmap    // 溢出指针}

          每个bucket可以存储8个键值对，超过8个，就会使用链式结构，存储到溢出指针里面。

          • tophash 是一个长度为8的整型数组，Hash低位相同的key，存储到当前bucket时，会将高位hash存储数组，用于匹配。
          • data 存储的是key-value数据，存储顺序是 key/key/key/…/value/value/value/…；这样存放可以不用考虑字节对齐的问题。
          • overflow 指针指向下一个bucket，将hash低位相同的连起来。

            data和overflow没有在数据结构中定义，运行时通过指针计算内存偏移量访问。

            比如如下是一个map的简易结构：

            2.3 hash 冲突

            当不同key-value的key的hash值的低位相同的时候，就发生了hash冲突，特别是当buckets的长度比较小的时候，发生冲突的概率就比较大。

            当发生了hash冲突的时候，将hash值的高位存储到tophash数组，当超过8个的时候，创建溢出bucket，用链表的方式链接。

            当发生hash冲突并超过8个的时候的示意图如下：

            当出现了hash冲突后，如果hash冲突比较严重，那么map的性能会降低。

            2.4 负载因子

            负载因子用于衡量一个Hash表的冲突情况：

            负载因子=len(keys)/len(buckets)

            比如，对于一个len(buckets)等于4，存储有4个键值对的Hash表来说，Hash表的负载因子等于1。

            负载因子的含义：

            • 负载因子过小，说明空间利用率低
            • 负载因子过大，说明冲突严重，存取效率低

              负载因子过小，可能是预分配的空间太大，也可能是大部分元素被删除造成的。随着键值对不断加入到map中，负载因子会逐渐升高。

              负载因子过大，需要申请更多的bucket，并对所有的键值对重新Hash。

              每种Hash表对负载因子的容忍程度不同。

              • redis: 因为redis的每个bucket中只能存储一个key-value，所以当负载因子大于1就会rehash.
              • Go: 在Go里面每个bucket中可以存储8个key-value，当负载因子大于6.5时才会rehash.
              • Java: Java每个bucket中可以存储更多的key-value，当大于8时，触发树化，小于6时，触发拆树使用链表。

                3. 扩容

                3.1 扩容条件

                扩容可以降低负载因子，保证访问效率。每次有新的key-value要添加进map时，都会检查是否需要扩容，扩容实际上用空间换时间的手段。

                当满足任一条件时，就会触发扩容：负载因子大于6.5，即平均每个bucket存储的key-value达到6.5个以上；overflow的数量达到2^min(15,B)。

                也就是说，当map的整体容量达到一定阈值，触发扩容，或者Hash冲突比较严重的时候，也会触发扩容。

                3.2 增量扩容

                当负载因子过大时，就新建一个newBuckets，len(newBuckets)=len(OldBuckets)*2，然后OldBuckets中的数据拷贝到newBuckets中。

                如果map中存储的key-value比较多，那么一次性拷贝将造成比较大的延时，Go采用逐步拷贝策略，每次访问map触发一次拷贝，每次拷贝2个bucket。

                为了简单，假设map的buckets就一个bucket，并且len(map)=7,负载因子等于7：

                此时负载因子等于7，大于6.5，再次添加key-value就会触发扩容，扩容之后再写入。

                扩容时，首先将oldBuckets指向原来的buckets数组，然后申请newBuckets,长度是原来的两倍(2^B)，并让buckets指向新申请的buckets。

                从oldBuckets拷贝到新的buckets需要重新计算hash，也就是rehash，所以新的数据存储位置不确定，不一定是在bucket1,也有可能是bucket，需要根据hash低位取余len(buckets)计算。

                后面每次访问map，都会rehash两个bucket，需要注意的是，如果bucket存在溢出，那么在处理的时候，溢出的bucket也会rehash，而且即使数据从旧buckets拷贝到新buckets，也会存在溢出等情况。

                扩容完成后可能得情况：

                经过rehash，原本bucket0存储了7个key-value，但是经过rehash，数据被平均分到了两个bucket中了。(这是最理想的情况，实际上hash不会完全均匀分布)

                3.3 等量扩容

                增量扩容出现在map增加key-value导致的负载因子增大，超过6.5，而产生的扩容。

                导致扩容的另一种情况，就是因为删除，导致每个bucket数据大量空闲。

                因为数据不在集中，而bucket中对于原始溢出的数据又是使用链表的方式组织的，那么数据存取的性能就很差。想想Java对于出现Hash冲突的时候，超过8个就会将链表转为红黑树，就是因为链表访问性能太差。

                比如如下map:

                虽然map中只有三个key-value，但是如果要访问第三个key-value，就需要讲过两次链表访问，性能变差。

                这种情况下就会进行类似jvm的gc中的复制拷贝原理，将数据进行碎片整理，清理内存占用的同时，使数据集中起来，提高访问性能。

                这种扩容，并不会增加buckets的数量，只是整理数据。

                4. map 操作

                无论是key-value的添加还是查询曹组哦，都需要根据key的hash值，确定bucket，然后查询bucket中是否存在key。

                4.1 查询

                查询的过程如下：

                • 根据key计算hash
                • 取hash低位与hmap.B取模确定bucket的位置
                • 取Hash高位，在tophash中查询
                • 如果tophash[i]中存储的Hash值与当前key的hash相等，那么取tophash[i]中的key进行比较
                • 如果在当前bucket中没有找到，那么继续找溢出的bucket
                • 如果map处于拷贝中，那么优先从oldBuckets中查找，找不到在从buckets中找。
                • 如果找不到，返回类型零值
                • 如果找到，返回value

                  4.2 添加&更新

                  添加或更新过程：

                  • 根据key计算hash
                  • 根据hash低位计算找到bucket
                  • 查询key是否存在，存在则更新，否则寻找空闲位置增加
                  • 如果map处于拷贝中，那么新元素会直接添加到buckets中。

                    4.3 删除

                    删除也是先查找，找到就删除，找不到就什么都不做。

                    5. 总结

                    map的代码其实比较难懂，里面存在大量的地址计算，而且变量命名实际上并不友好。

                    比如，判断map是否处于拷贝中：

                    如果oldBuckets不为空就是处于拷贝中。

                    在比如，map扩容：

                    在加上map针对32位和64位，以及string做了优化，源码非常难懂：