Hashmap

创建 map 创建 map 的语法很简单 // 不指定map长度 ageMp := make(map[string]int) // 指定map长度 ageMp := make(map[string]int, 8) // ageMp 为 nil，不能向其添加元素，会直接panic var ageMp map[string]int 通过汇编语言，我们能够跟踪到 map 的创建最终会调用 runtime.makemap 方法 // makemap implements Go map creation for make(map[k]v, hint). // If the compiler has determined that the map or the first bucket // can be created on the stack, h and/or bucket may be non-nil. // If h != nil, the map can be created directly in h. // If h.buckets != nil, bucket pointed to can be used as the first bucket. // 翻译：makemap实现了make(map[k]v, hint)这种形式语法的Go map创建。 // 如果编译器已经确定该map或者第一个bucket能够在这个栈上创建，那么h和(或)bucket可能为非nil。 // 如果h不是nil，那么该map能直接创建在这个h上。 // 如果h.buckets不是nil, 则被指向的bucket能被用来做第一个bucket func makemap(t *maptype, hint int, h *hmap) *hmap { // 计算指定的大小所需要的内容是否超出出系统允许的最大分配大小 mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size) if overflow || mem > maxAlloc { hint = 0 } // 初始化hmap，并指定随机种子 if h == nil { h = new(hmap) } h.hash0 = fastrand() // Find the size parameter B which will hold the requested # of elements. // For hint < 0 overLoadFactor returns false since hint < bucketCnt. // 通过overLoadFactor(hint, B)函数找到一个能装下指定map大小个元素个数的最小B，要满足 装载因子*2^B < hint B := uint8(0) for overLoadFactor(hint, B) { B++ } h.B = B // allocate initial hash table // if B == 0, the buckets field is allocated lazily later (in mapassign) // If hint is large zeroing this memory could take a while. // 开始对hash table进行初始化。如果B==0则buckets 进行懒初始化操作（赋值的时候才进行初始化），如果B值特别大，则初始化需要一段时间，主要通过 makeBucketArray() 函数实现 if h.B != 0 { var nextOverflow *bmap h.buckets, nextOverflow = makeBucketArray(t, h.B, nil) if nextOverflow != nil { h.extra = new(mapextra) // 溢出桶地址赋值 h.extra.nextOverflow = nextOverflow } } return h } // makeBucketArray initializes a backing array for map buckets. // 1<<b is the minimum number of buckets to allocate. // dirtyalloc should either be nil or a bucket array previously // allocated by makeBucketArray with the same t and b parameters. // If dirtyalloc is nil a new backing array will be alloced and // otherwise dirtyalloc will be cleared and reused as backing array. // 翻译：makeBucketArray为map buckets初始化一个备用数组 // 2^b是该buckets长度的最小值 // dirtyalloc之前应该是nil或者bucket数组 // 如果dirtyalloc 为nil，将分配一个新的后备数组，否则将清除dirtyalloc 并作为后备数组重用。 func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) { base := bucketShift(b) // base = 2^b nbuckets := base // For small b, overflow buckets are unlikely. // Avoid the overhead of the calculation. // 对于小的b，不太可能会需要溢出桶，可以避免这部分计算开销 // 对于b>4（桶的数量> 2^4）的话，则需要创建2^(b-4)个溢出桶。 if b >= 4 { // 加上溢出桶的数量 nbuckets += bucketShift(b - 4) // 总大小 sz := t.bucket.size * nbuckets // 针对所需要的内存大小，mallocgc将分配的内存块大小 up := roundupsize(sz) if up != sz { // 如果总大小和mallocgc将分配的内存块大小不同，以mallocgc分配的为准，计算nbuckets nbuckets = up / t.bucket.size } } if dirtyalloc == nil { buckets = newarray(t.bucket, int(nbuckets)) } else { // dirtyalloc was previously generated by // the above newarray(t.bucket, int(nbuckets)) // but may not be empty. buckets = dirtyalloc size := t.bucket.size * nbuckets if t.bucket.ptrdata != 0 { memclrHasPointers(buckets, size) } else { memclrNoHeapPointers(buckets, size) } } if base != nbuckets { // We preallocated some overflow buckets. // To keep the overhead of tracking these overflow buckets to a minimum, // we use the convention that if a preallocated overflow bucket's overflow // pointer is nil, then there are more available by bumping the pointer. // We need a safe non-nil pointer for the last overflow bucket; just use buckets. // 我们提前分配了一些溢出桶，为了使得追踪溢出桶的开销最小，我们这样约定: // 如果溢出桶的overflow指针为nil，那么代表还有空间在出现哈希碰撞时使用， // 溢出桶的最后一个桶的overflow需要指向一个安全的非空指针，这里指向了buckets的第一个桶 // 具体的用处在map写入时，需要创建溢出桶时会用到，具体在newoverflow函数中 nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize))) // 指向第一个溢出桶 last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize))) // 指向最后一个溢出桶 last.setoverflow(t, (*bmap)(buckets)) // 溢出桶的最后一个桶的overflow指向了buckets的第一个桶 } return buckets, nextOverflow } 从上面代码可以得知，2^B 并不等于 buckets 的大小，它只是创建 buckets 时的 base 部分，在该部分后，还有溢出桶。所以正常桶和溢出桶在内存上的分布是连续的，溢出桶的指针记录在了 hmap 的 extra 字段中。 ...

本文中使用的 go 版本： go version go1.17.2 darwin/amd64 内容概述 本文介绍 golang 中经常用到的结构-map，简称哈希表、字典。介绍其结构及设计思路。 map 在源码中的结构——hmap Go 语言采用的核心数据结构是哈希查找表，使用链表解决哈希冲突。 在源码中$GOROOT/src/runtime/map.go，map 的核心结构体是这样的： // A header for a Go map. type hmap struct { count int // map中的元素数量，即len(map)时的返回值 flags uint8 B uint8 // buckets的以2为底的对数, 即2^B=buckets noverflow uint16 // 溢出桶的近似数; see incrnoverflow for details hash0 uint32 // 哈希种子 buckets unsafe.Pointer // 2^B个bucket的数组，may be nil if count==0. oldbuckets unsafe.Pointer // 哈希在扩容时用于保存之前 buckets 的字段，它的大小是当前 buckets 的一半； nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated) extra *mapextra // optional fields } 在上面我们需要关注的核心是buckets，它是一个指针，最终指向了bmap结构体数组 ...