不断的谦逊,不断的努力

不断的谦逊,不断的努力

map结构
整体为一个数组,数组每个元素可以理解成一个槽,槽是一个链表结构,槽的每个节点可存8个元素,搞清楚了map的结构,想想对应的增删改查操作也不是那么难
Go map实现原理-LMLPHP
1:槽大小计算&hash算法
我们可以简单的理解成:槽大小为1<<N,每个元素计算出一个hash值hashCode,hash到这些槽中,hash算法:hashCode&1<<N-1,刚好和槽的范围完全重合
关于hash冲突,那是必须的,当你指定预计元素个数时,预计平均一个槽6.5个元素,据我观察好多语言的hash都是采用hashCode&1<<N-1的hash方式,可能是因为实现简单,元素分布比较均匀
hashCode的计算请参考文件:src/runtime/hash64.go   src/runtime/hash32.go
 
2:容量计算和扩容
m := make(map[string]int, hint)
func overLoadFactor(count int64, B uint8) bool {
   return count >= 8 && float32(count) >= 6.5*float32((uint64(1)<<B))
}
b := uint8(0)  //最大128位足够了
for ; overLoadFactor(hint, b); b++ {
}

func makeBucketArray(t *maptype, b uint8) (buckets unsafe.Pointer, nextOverflow *bmap) {
   base := uintptr(1 << b)
   nbuckets := base
   if b >= 4 {
      nbuckets += 1 << (b - 4)    //多分配了1/16的空间,当某个槽满了之后可以可以从这里多取出一个节点
      sz := t.bucket.size * nbuckets
      up := roundupsize(sz)
      if up != sz {
         nbuckets = up / t.bucket.size
      }
   }
   buckets = newarray(t.bucket, int(nbuckets))
   if base != nbuckets {
      nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
      last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
      last.setoverflow(t, (*bmap)(buckets))
   }
   return buckets, nextOverflow
}
初始化容量和扩容都是调上面的方法makeBucketArray
举个例子:m := make(map[int][string], 10),通过上面计算b的方法得出b=2,即4=1<<2个槽,每个槽一个节点,每个节点可容纳8个元素,总共可容纳32个元素,可容纳期望的10个元素
扩容基本采取2*N + N/16的方式(2倍扩容),多出来的N/16用于槽满的情况,新增的节点就从这多出来的地方取,如果多出来的槽也用完了就直接new新的内存
槽大小(t.bucketsize)应该是提前就计算好了的,每个槽能容纳8个元素,当槽满之后,如果还有新增到这个槽的元素,会新增一个槽,以链表的方式连在这个槽的后面
 
扩容后数据怎么复制过来
go并没有采用一下子就将数据全部复制过来的方式,如果数据很多还是非常耗时的,而是在写数据的时候如果命中一个老槽,就将这个槽中的所有数据重新hash到新的数据结果中,在扩容过程中,新老数据结构同时提供数据的查询,写数据的时候只会写入新的数据结构中,同时将命中老数据结构对应槽中的数据重新hash到新的数据结构中。
 
扩容条件
1:已经处于扩容状态就不能再扩容了,就新老两个数据结构,没有第三了
2:元素个数>6.5*槽数量(槽的每个节点能容纳8个元素,但是分布不可能这么均匀的),可以扩容
3:槽节点写满的个数到达一定数量也可以扩容
也就是说,在没有扩容的情况下:元素个数太多 || 槽节点满的数量多,都会触发扩容 
 
一个槽就是多个节点组成的链表,节点数据结构如下:
// A bucket for a Go map.
const bucketCnt = 8
type bmap struct {
   // tophash generally contains the top byte of the hash value
   // for each key in this bucket. If tophash[0] < minTopHash,
   // tophash[0] is a bucket evacuation state instead.
   tophash [bucketCnt]uint8
   // Followed by bucketCnt keys and then bucketCnt values.
   // NOTE: packing all the keys together and then all the values together makes the
   // code a bit more complicated than alternating key/value/key/value/... but it allows
   // us to eliminate padding which would be needed for, e.g., map[int64]int8.
   // Followed by an overflow pointer.
}
节点数据结构:
1:8个标记位的数组,用于标记每个元素的情况,如这个位置是否有元素,8个字节
2:连续的8个key,根据key的类型能计算出8个key的大小
3:连续的8个value,根据value的类型能计算出8个value的大小
4:指向下一个节点的指针,8个字节
但从节点的数据结构中只看到了8个标记位的数组,其他的都没有写出来,但是一个节点的大小是能计算出来的,可以分配一个能容纳以上4个元素的空间,在强制转换成*bmap就行,然后按照地址+偏移量就能计算出每个元素的地址
 
value = map[key] 源码分析 
//go:linkname reflect_mapaccess reflect.mapaccess      map[key]
func reflect_mapaccess(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
   val, ok := mapaccess2(t, h, key)
   if !ok {
      val = nil
   }
   return val
}
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {
   alg := t.key.alg
   //计算hashCode
   hash := alg.hash(key, uintptr(h.hash0))
   m := 1<<h.B - 1
   //hash到对应的槽,go的hash算法就是:hash&(1<<h.B - 1)
   b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize)))
   //老的数据结构对应的槽如果有数据,就从老的取
   if c := h.oldbuckets; c != nil {
      if !h.sameSizeGrow() {
          m >>= 1   //如果正在扩容,老的容量为新的容量的一半
      }
      oldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&m)*uintptr(t.bucketsize)))
      if !evacuated(oldb) {
         b = oldb
      }
   }
   top := uint8(hash >> (sys.PtrSize*8 - 8))
   if top < minTopHash {
      top += minTopHash
   }
   for {
      for i := uintptr(0); i < bucketCnt; i++ {
         if b.tophash[i] != top {    //top标记位表示有值
            continue
         }
         //通过槽首地址+偏移量计算第i个key的位置
         k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
         k = *((*unsafe.Pointer)(k))
         //如果第i个key等于我们要查找的key,就返回第i个value
         if alg.equal(key, k) {
            //通过槽首地址+偏移量计算第i个value的位置
            v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
            v = *((*unsafe.Pointer)(v))
            return v, true
         }
      }
      //b指向下一个节点,如果不为空就继续遍历
      b = b.overflow(t)
      if b == nil {
         return unsafe.Pointer(&zeroVal[0]), false
      }
   }
}

  

map[key] = value 源码分析
//go:linkname reflect_mapassign reflect.mapassign      map[key] = value
func reflect_mapassign(t *maptype, h *hmap, key unsafe.Pointer, val unsafe.Pointer) {
   p := mapassign(t, h, key)  //这里会把key写进去
   typedmemmove(t.elem, p, val) //这里写value
}
// Like mapaccess, but allocates a slot for the key if it is not present in the map.
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
   alg := t.key.alg
   hash := alg.hash(key, uintptr(h.hash0))
   h.flags |= hashWriting
   //没元素就分配1个元素的空间
   if h.buckets == nil {
      h.buckets = newarray(t.bucket, 1)
   }

again:
   //hash到第bucket个槽
   bucket := hash & (uintptr(1)<<h.B - 1)
   //如果正在扩容,会将老数据结果中对应槽中的所有数据都重新hash到新的数据结构中
   if h.growing() {
      growWork(t, h, bucket)
   }
   计算第bucket个槽的地址
   b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
   top := uint8(hash >> (sys.PtrSize*8 - 8))
   if top < minTopHash {
      top += minTopHash
   }

   var inserti *uint8        //标记位
   var insertk unsafe.Pointer//key写在这里
   var val unsafe.Pointer    //value写在这里
   for {
      for i := uintptr(0); i < bucketCnt; i++ {
         if b.tophash[i] != top {
            //第i个元素为空,如果是新增的,新增就往这里写数据啊
            if b.tophash[i] == empty && inserti == nil {
               inserti = &b.tophash[i]
               insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
               val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
            }
            continue
         }
         k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
         if t.indirectkey {
            k = *((*unsafe.Pointer)(k))
         }
         //如果key相等就是更新数据
         if !alg.equal(key, k) {
            continue
         }
         // already have a mapping for key. Update it.
         if t.needkeyupdate {
            typedmemmove(t.key, k, key)
         }
         //更新数据,找到对应的位置返回就行
         val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
         goto done
      }
      //b指向下一个节点,如果不为空就继续遍历
      ovf := b.overflow(t)
      if ovf == nil {
         break
      }
      b = ovf
   }

   //已经处于扩容状态就不能再扩容了,就新老两个数据结构,没有第三了
   //元素个数>6.5*槽数量(槽的每个节点能容纳8个元素,但是分布不可能这么均匀的),可以扩容
   //槽节点写满的个数较多也可以扩容
   if !h.growing() && (overLoadFactor(int64(h.count), h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
      hashGrow(t, h)
      goto again // Growing the table invalidates everything, so try again
   }

   if inserti == nil {
      //当前节点已经满了,重新分配一个节点,新节点会连在当前节点后面
      newb := h.newoverflow(t, b)
      inserti = &newb.tophash[0]
      insertk = add(unsafe.Pointer(newb), dataOffset)
      val = add(insertk, bucketCnt*uintptr(t.keysize))
   }

   //引用类型分配key所需空间,同时把key在槽中对应的位置指向这个空间
   if t.indirectkey {
      kmem := newobject(t.key)
      *(*unsafe.Pointer)(insertk) = kmem
      insertk = kmem
   }
   //引用类型分配value所需空间,同时把value在槽中对应的位置指向这个空间
   if t.indirectvalue {
      vmem := newobject(t.elem)
      *(*unsafe.Pointer)(val) = vmem
   }
   //将key写入刚分配的空间
   typedmemmove(t.key, insertk, key)
   //更新标记位
   *inserti = top
   //元素个数+1
   h.count++

done:
   if h.flags&hashWriting == 0 {
      throw("concurrent map writes")
   }
   h.flags &^= hashWriting
   if t.indirectvalue {
      val = *((*unsafe.Pointer)(val))
   }
   //直接将val返回了,value为一个结构体(非指针)map[key].fieldXXX = 1,这样做是不行的
   //因为val作为返回值会被拷贝,如果val类型结构体(非指针),map[key]返回的就是一个拷贝,并没有更新真正的val,而指针类型却没有这个问题,如果结构体较大最好以指针的方式存入map
   return val
}
 
02-21 10:15