Golang map實現原理深入分析

type hmap struct {
   // map中存入元素的個數， golang中調用len(map)的時候直接返回該字段
   count     int
   // 狀態標記位，通過與定義的枚舉值進行&操作可以判斷當前是否處於這種狀態
   flags     uint8
   B         uint8  // 2^B 表示bucket的數量， B 表示取hash後多少位來做bucket的分組
   noverflow uint16 // overflow bucket 的數量的近似數
   hash0     uint32 // hash seed （hash 種子） 一般是一個素數
   buckets    unsafe.Pointer // 共有2^B個 bucket ，但是如果沒有元素存入，這個字段可能為nil
   oldbuckets unsafe.Pointer // 在擴容期間，將舊的bucket數組放在這裡， 新buckets會是這個的兩倍大
   nevacuate  uintptr        // 表示已經完成擴容遷移的bucket的指針， 地址小於當前指針的bucket已經遷移完成
   extra *mapextra // optional fields
}

// A bucket for a Go map.
type bmap struct {
   tophash [bucketCnt]uint8
}

type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr        // 內存對齊使用，可能不需要
    overflow uintptr        // 當bucket 的8個key 存滿瞭之後
}

func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {
    // map 為空，或者元素數為 0，直接返回未找到
    if h == nil || h.count == 0 {
        return unsafe.Pointer(&zeroVal[0]), false
    }
    // 不支持並發讀寫
    if h.flags&hashWriting != 0 {
        throw("concurrent map read and map write")
    }
    // 根據hash 函數算出hash值，註意key的類型不同可能使用的hash函數也不同
    hash := t.hasher(key, uintptr(h.hash0))
    // 如果 B = 5，那麼結果用二進制表示就是 11111 ， 返回的是B位全1的值
    m := bucketMask(h.B)
    // 根據hash的後B位，定位在bucket數組中的位置
    b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize)))
    // 當 h.oldbuckets 非空時，說明 map 發生瞭擴容
    // 這時候，新的 buckets 裡可能還沒有老的內容
    // 所以一定要在老的裡面找，否則有可能發生“消失”的詭異現象
    if c := h.oldbuckets; c != nil {
        if !h.sameSizeGrow() {
            // 說明之前隻有一半的 bucket，需要除 2
            m >>= 1
        }
        oldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&m)*uintptr(t.bucketsize)))
        if !evacuated(oldb) {
            b = oldb
        }
    }
    // tophash 取其高 8bit 的值
    top := tophash(hash)
    // 一個 bucket 在存儲滿 8 個元素後，就再也放不下瞭，這時候會創建新的 bucket，掛在原來的 bucket 的 overflow 指針成員上
    // 遍歷當前bucket的所有鏈式bucket
    for ; b != nil; b = b.overflow(t) {
        // 在bucket的8個位置上查詢
        for i := uintptr(0); i < bucketCnt; i++ {
            // 如果找到瞭相等的 tophash，那說明就是這個 bucket 瞭
            if b.tophash[i] != top {
                continue
            }
            // 根據內存結構定位key的位置
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if t.indirectkey {
                k = *((*unsafe.Pointer)(k))
            }
            // 校驗找到的key是否匹配
            if t.key.equal(key, k) {
                // 定位v的位置
                v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
                if t.indirectvalue {
                    v = *((*unsafe.Pointer)(v))
                }
                return v, true
            }
        }
    }
    // 所有 bucket 都沒有找到，返回零值和 false
    return unsafe.Pointer(&zeroVal[0]), false
}

objMap := make(map[string]int)
for i := 0; i < 5; i++ {
   objMap[strconv.Itoa(i)] = i
}
for i := 0 ; i < 5; i ++ {
   var valStr1, valStr2 string
   for k, v := range objMap {
      fmt.Println(k)
      fmt.Println(v)
      valStr1 += k
   }
   for k, v := range objMap {
      fmt.Println(k)
      fmt.Println(v)
      valStr2 += k
   }
   fmt.Println(valStr1 == valStr2)
   if valStr1 != valStr2 {
      fmt.Println("not equal")
   }
}
fmt.Println("end")

// 不支持並發讀寫
    if h.flags&hashWriting != 0 {
        throw("concurrent map read and map write")
    }