Go 基础知识与框架体系 系列九: hashmap

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

// A header for a Go map.
type hmap struct {
	count int // len()返回的map的大小 即有多少kv对
	flags uint8
	B     uint8  // 表示hash table总共有2^B个buckets 
	hash0 uint32 // hash seed
	buckets    unsafe.Pointer // 按照low hash值可查找的连续分配的数组，初始时为16个Buckets.
	oldbuckets unsafe.Pointer 
	nevacuate  uintptr      
	overflow *[2]*[]*bmap //溢出链 当初始buckets都满了之后会使用overflow
}

// A bucket for a Go map.
type bmap struct {
    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
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// makemap implemments a Go map creation make(map[k]v, hint)
func makemap(t *maptype, hint int64, h *hmap, bucket unsafe.Pointer) *hmap{
  B := uint8(0)
  for ; hint > bucketCnt && float32(hint) > loadFactor*float32(uintptr(1)<<B); B++ {
  }
  // 确定初始B的初始值 这里hint是指kv对的数目 而每个buckets中可以保存8个kv对
  // 因此上式是要找到满足不等式 hint > loadFactor*(2^B) 最小的B
  if B != 0 {
    buckets = newarray(t.bucket, uintptr(1)<<B)
  }
  h = (*hmap)(newobject(t.hmap))
  return h
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

func mapassign1(t *maptype, h *hmap, key unsafe.Pointer, val unsafe.Pointer) {
  hash := alg.hash(key, uintptr(h.hash0))
  if h.buckets == nil {
    h.buckets = newarray(t.bucket, 1)
  }
again:
  //根据低8位hash值找到对应的buckets
  bucket := hash & (uintptr(1)<> (sys.PtrSize*8 - 8))
  for {
    //遍历每一个bucket 对比所有tophash是否与top相等
    //若找到空tophash位置则标记为可插入位置
    for i := uintptr(0); i < bucketCnt; i++ {
      if b.tophash[i] != top {
        if b.tophash[i] == empty && inserti == nil {
          inserti = &b.tophash[i]
        } 
        continue
      }
      //当前tophash对应的key位置可以根据bucket的偏移量找到
      k2 := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
      if !alg.equal(key, k2) {
        continue
      }
      //找到符合tophash对应的key位置
      typedmemmove(t.elem, v2, val)
      goto done
    }
    //若overflow为空则break
    ovf := b.overflow(t)
  }
  // did not find mapping for key.  Allocate new cell & add entry.
  if float32(h.count) >= loadFactor*float32((uintptr(1)<= bucketCnt {
    hashGrow(t, h)
    goto again // Growing the table invalidates everything, so try again
  }
  // all current buckets are full, allocate a new one.
  if inserti == nil {
    newb := (*bmap)(newobject(t.bucket))
    h.setoverflow(t, b, newb)
    inserti = &newb.tophash[0]
  }
  // store new key/value at insert position
  kmem := newobject(t.key)
  vmem := newobject(t.elem)
  typedmemmove(t.key, insertk, key) 
  typedmemmove(t.elem, insertv, val)
  *inserti = top
  h.count++
}