拉链法

拉链法-每个桶中都应有0-1个元素,有时2-3个。计算哈希、定位桶和遍历链表三个过程是哈希表读写操作的主要开销。
装载因子:
装载因子 := 元素数量 / 桶数量
拉链法的哈希表装载因子不会超过1.哈希表装载因子过大会触发哈希的扩容。创建更多的桶来存储哈希中的元素,保证性能不会出现严重的下降。

map的数据结构

src/runtime/map.go#L115

  1. // A header for a Go map.
  2. type hmap struct {
  3. // Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go.
  4. // Make sure this stays in sync with the compiler's definition.
  5. count int // # live cells == size of map. Must be first (used by len() builtin)
  6. flags uint8
  7. B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
  8. noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
  9. hash0 uint32 // hash seed
  10. buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
  11. oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
  12. nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated)
  13. extra *mapextra // optional fields
  14. }
  1. count表示当前哈希表中的元素数量
  2. B表示当前哈希表持有的buckets数量。但是因为哈希表中桶的数量都是2的倍数,所以该字段会存储对数,也就是len(buckest) == 2^B
  3. hash0是哈希的种子,它能为哈希函数的结果引入随机性。政治在创建哈希表时确定,并在调用哈希函数时作为参数传入;
  4. oldbuckets是哈希再扩容是用于保存之前的buckets的字段。它的大小是当前buckets的一半;
  1. // mapextra holds fields that are not present on all maps.
  2. type mapextra struct {
  3. // If both key and elem do not contain pointers and are inline, then we mark bucket
  4. // type as containing no pointers. This avoids scanning such maps.
  5. // However, bmap.overflow is a pointer. In order to keep overflow buckets
  6. // alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow.
  7. // overflow and oldoverflow are only used if key and elem do not contain pointers.
  8. // overflow contains overflow buckets for hmap.buckets.
  9. // oldoverflow contains overflow buckets for hmap.oldbuckets.
  10. // The indirection allows to store a pointer to the slice in hiter.
  11. overflow *[]*bmap
  12. oldoverflow *[]*bmap
  13. // nextOverflow holds a pointer to a free overflow bucket.
  14. nextOverflow *bmap
  15. }


哈希表 runtime/map.go-hmap 的桶是runtime/map.go-bmap.每一个bmap都能存储8个键值对,当哈希表中存储的数据过多。单个桶已经装满就会使用
extra.nextOverFlow中桶存储溢出的数据。上述两种不同的桶在内存中是连续存储的。分为正常桶和溢出桶。 溢出桶使用c语言实现能够减少扩容的频率所以还在使用中。

桶的结构体 runtime/map.go-bmap 只有一个字段 tophash,tophash 存储了键的哈希的高8位

  1. type bmap struct {
  2. tophash [bucketCnt]uint8
  3. }

runtime.bmap中的其他字段在运行时通过计算内存地址的方式访问的。定义中不包含这些字段。通过编译期间的 cmd/compile/internal/gc/reflect.go-bmap函数重建结构

  1. type bmap struct {
  2. topbits [8]uint8
  3. keys [8]keytype
  4. values [8]valuetype
  5. pad uintptr
  6. overflow uintptr
  7. }

随着哈希表的数据的逐渐增多,会扩容哈希表或者使用额外的桶存储溢出的数据,不会让单个桶中的数据超过8个, 不让单个桶的数据超过8个,溢出桶是临时的解决方案。 创建过多的溢出桶最终也会导致哈希的扩容。

map初始化

字面量

字面量初始化会通过cmd/compile/internal/gc/sinit.go#L753-maplit初始化。

  1. func maplit(n *Node, m *Node, init *Nodes) {
  2. // make the map var
  3. a := nod(OMAKE, nil, nil)
  4. a.Esc = n.Esc
  5. a.List.Set2(typenod(n.Type), nodintconst(int64(n.List.Len())))
  6. litas(m, a, init)
  7. entries := n.List.Slice()
  8. // The order pass already removed any dynamic (runtime-computed) entries.
  9. // All remaining entries are static. Double-check that.
  10. for _, r := range entries {
  11. if !isStaticCompositeLiteral(r.Left) || !isStaticCompositeLiteral(r.Right) {
  12. Fatalf("maplit: entry is not a literal: %v", r)
  13. }
  14. }
  15. if len(entries) > 25 {
  16. }
  17. ...
  18. }

当哈希表中的元素少于或者等于25个时,会将所有的键值对一次性加入到哈希表中。
这种初始化方式与数组和切片的几乎相同。 得到集合类型的初始化在go语言中有相同的处理逻辑。
超过25个元素数量时,编译器会创建两个数组分别存储键和值。键值对然后循环构建成哈希。

字面量初始化过程通过make关键字创建新的哈希并通过原始的[]语法向哈希追加元素。

运行时

创建的哈希被分配到栈上并且容量小于BUCKETSIZE=8时,直接快速初始化。
其他再通过make创建,编译器然后在类型检查期间转换成 src/runtime/map.go#L303-makemap。 字面量最后调用的也是这个函数。

  1. func makemap(t *maptype, hint int, h *hmap) *hmap {
  2. mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
  3. if overflow || mem > maxAlloc {
  4. hint = 0
  5. }
  6. // initialize Hmap
  7. if h == nil {
  8. h = new(hmap)
  9. }
  10. h.hash0 = fastrand()
  11. // Find the size parameter B which will hold the requested # of elements.
  12. // For hint < 0 overLoadFactor returns false since hint < bucketCnt.
  13. B := uint8(0)
  14. for overLoadFactor(hint, B) {
  15. B++
  16. }
  17. h.B = B
  18. // allocate initial hash table
  19. // if B == 0, the buckets field is allocated lazily later (in mapassign)
  20. // If hint is large zeroing this memory could take a while.
  21. if h.B != 0 {
  22. var nextOverflow *bmap
  23. h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
  24. if nextOverflow != nil {
  25. h.extra = new(mapextra)
  26. h.extra.nextOverflow = nextOverflow
  27. }
  28. }
  29. return h
  30. }

函数分为四部分:

  1. 计算哈希占用的内存是否溢出或者超出能分配的最大值。
  2. 调用runtime.fasterand获取一个随机的哈希种子。
  3. 根据传入的hint计算出需要的最小需要的桶数量
  4. 使用runtime.makeBucketArray 创建用于保存桶的数组

读写操作

写操作: 增、删、改
读操作

读操作
直接通过key值进行访问的会被转换成OINDEXMAP操作。 哈希表扩容并不是原子过程, src/runtime/map.go-mapassign 扩容条件:

  1. 装载因子已经超过6.5
  2. 哈希使用了太多溢出桶

还需要判断是否已经处于扩容状态。避免二次扩容造成混乱。

map扩容时机

  1. 装载因子超过阈值。源码定义的阈值是6.5。
  2. overflow 的bucket数量过多:当 B 小于15时,也就是bucket总数2^B小于15时,如果overflow的bucket数量超过2^B;当B>=15,也就是bucket总数2^B大于等于2^15时如果overflow的bucket数量超过2^15。

go的扩容是 渐进式扩容。

map搬迁流程
growWork()->mapassign/mapdelete (插入、修改、删除key的时候) 才会搬迁

问题点: map 在迁移过程中老的bucket 发生了扩容,怎么把老的bucket中的迁移到新的buckets