Map

Map 是什么

map 是由一组 <key,value> 对组成的抽象数据结构，并且同一个 key 只会出现一次。 Go 的 map 底层是一个哈希表，包含若干 bucket（桶）。每个 bucket 是一个包含多个键值对的结构。

  • map 相关的操作主要有：增删改查
  • 数据结构：
    • 哈希查找表 O(N)
      • 哈希表存在碰撞问题，解决方法
        • 链表法：将一个 bucket 实现成一个链表，落在同一个 bucket 的 key 都会插入这个链表
        • 开放地址法：按照一定的规律，在 bucket 的后面挑选空位，用来放置 key
    • 搜索树：AVL 树，和红黑树 O(logN)

底层原理

  1. map 的内存模型
// src/runtime/map.go
type hmap struct {
    // 元素个数
    count int
    flags uint8
    // buckets 的对数 log-2
    B uint8
    // overflow 的bucket 近似值
    noerflow uint16
    // hash 函数
    hash0 uint32
    // buckets 数组，大小为2^B
    buckets unsafe.Pointer
    // 扩容时，buckets 长度时 oldbuckets 的两倍
    oldbuckets unsafe.Pointer 
    // 扩容进度，小于此地址的bucket 完成迁移
    nevacuate uniptr
    extra *mapextra
}

每个 bucket 中最多可以存储 8 对键值对，Go 使用数组存储这些键值对。当 bucket 的大小超过限制时，系统会进行扩容。 B 是 buckets 数组的长度的对数，buckets 是一个指针，指向一个结构体：

    type bmap struct {
        tophash [bucketCnt]uint8
    }
    
    // 编译后
    type bmap struct {
        topbits [8]uint8
        keys [8]keytype
        values [8]valuetype
        pad uintptr
        overflow uintptr
    }

map 扩容过程是怎样的

触发扩容条件

map会在以下两种情况下触发扩容:

  • 负载因子超过阈值 当map中已存储的元素个数超过当前bucket总数的6.5倍时,就会触发扩容。这个6.5是Go语言中经过测试得出的一个经验值。
  • 溢出桶太多 当溢出桶(overflow buckets)的数量太多时也会触发扩容。具体来说,如果bucket数量小于等于15,溢出桶数量超过bucket数量就会扩容;如果bucket数量大于15,溢出桶数量超过2^15就会扩容。

扩容过程

Go语言采用了渐进式的扩容方式,而不是一次性将所有数据重新哈希。主要步骤如下:

  • hashGrow函数初始化新的bucket数组 扩容时,会新建一个更大的bucket数组,bucket数量通常是原来的两倍。同时会将老的bucket数组赋值给oldbuckets字段。 evacuate函数负责数据迁移 在执行写操作(赋值、删除等)时,会通过evacuate函数将oldbuckets中的数据搬迁到新的bucket数组中。每次最多迁移两个bucket的数据。
  • 增加evacuatedNodes计数 evacuatedNodes记录已迁移的bucket个数。当evacuatedNodes等于oldbuckets长度时,说明所有数据已迁移完毕。
  • 清理oldbuckets 所有数据迁移完毕后,会清理oldbuckets字段,以节省内存。

总的来说,Go语言的map扩容是通过渐进式rehash实现的,避免了一次性rehash带来的延迟。同时还引入了overflow buckets来缓解rehash时数据迁移的压力。这种设计使得map的读写性能更加平滑和可控。

golang map的rehash是如何影响程序性能的

Go语言中map的rehash(重新哈希)过程会对程序性能产生一定影响,主要体现在以下几个方面:

  1. 一次性rehash可能导致停顿 传统的rehash方式是一次性将所有数据重新哈希到新的bucket数组中,这可能会导致程序在rehash期间出现较长时间的停顿,影响程序的响应时间和延迟。
  2. 渐进式rehash的额外开销 Go语言采用了渐进式的rehash方式,避免了一次性rehash带来的停顿,但也引入了一些额外的开销。在执行写操作时,需要检查是否需要rehash,如果需要则执行evacuate函数将部分数据迁移到新的bucket数组中。这些额外的检查和迁移操作会增加写操作的CPU开销。
  3. 内存占用暂时增加 在渐进式rehash过程中,需要同时维护新旧两个bucket数组,直到所有数据迁移完毕。这会导致map在rehash期间的内存占用暂时增加一倍左右。
  4. 读操作需要检查多个bucket 对于正在rehash的map,读操作可能需要查询两个bucket数组,从而增加了读操作的开销。不过这种情况相对较少见。
  5. rehash过程中并发访问可能导致竞争 由于rehash过程中需要读写bucket数组,如果在多个goroutine中并发访问map,可能会导致竞争条件和数据竞争问题。因此map不是线程安全的,在并发场景需要使用sync.Map或者加锁等机制。

总的来说,Go语言的渐进式rehash设计在一定程度上缓解了一次性rehash带来的延迟,但也引入了一些额外的CPU和内存开销。对于大多数应用场景,这些开销是可以接受的,rehash对整体性能的影响也是可控的。但在对延迟或内存占用要求非常严格的场景下,仍需要格外注意rehash可能带来的影响。

go map 如何解决冲突的

  1. 哈希计算：首先，每个键都会通过一个哈希函数进行处理，计算出一个哈希值。Golang 使用一种伪随机的哈希种子来增强哈希算法的随机性和安全性。
  2. 定位桶：根据计算出的哈希值，通过位操作确定键应该放置在哪个桶中。
  3. 遍历桶:一旦确定了桶,Go 会遍历该桶中的所有单元格(cells)。每个桶可以存储多个键值对(通常是8个)。这是通过 for i := uintptr(0); i < bucketCnt; i++ 循环完成的。
  4. 比较 tophash:为了快速筛选,Go 首先比较存储在 tophash 数组中的哈希值的高8位。这是一种优化,可以避免不必要的完整键比较。
  5. 键比较:如果 tophash 匹配,Go 会进行完整的键比较(if t.key.equal(key, k))。如果找到匹配的键,就返回对应的值。
  6. 溢出桶:如果在当前桶中没有找到匹配的键,且存在溢出桶,Go 会继续在溢出桶中查找。这通过 for ; b != nil; b = b.overflow(t) 循环实现。
  7. 插入新键值对:当插入新的键值对时,如果发生冲突(即桶已满),Go 会创建一个新的溢出桶,并将新的键值对插入到这个溢出桶中。
  8. 负载因子和重新哈希:为了保持良好的性能,Go 会在 map 的大小增长到一定程度时进行重新哈希(rehashing)。这个过程会创建一个更大的桶数组,并逐步将旧桶中的数据迁移到新桶中。
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    if h == nil {
        panic("assignment to entry in nil map")
    }
    hash := t.key.alg.hash(key, uintptr(h.hash0))

    // 定位到具体的桶
    bucket := hash & ((1 << h.B) - 1)
    if oldbuckets != nil {
        growWork(t, h, bucket)
    }

    // 主桶
    b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
    top := tophash(hash)

    // 在主桶及溢出桶中查找键或空位
    for {
        for i := uintptr(0); i < bucketCnt; i++ {
            if b.tophash[i] == top && t.key.equal(key, add(b.keys(), i*t.keysize)) {
                // 找到键，进行赋值或返回位置
                return add(b.values(), i*t.valuesize)
            }
            if b.tophash[i] == emptyRest {
                // 找到空位，可以插入新键
                b.tophash[i] = top
                return add(b.keys(), i*t.keysize)
            }
        }
        // 没有找到空位，处理溢出桶
        ovf := b.overflow(t)
        if ovf == nil {
            // 创建新的溢出桶
            ovf = h.newoverflow(t, b)
            b.setoverflow(t, ovf)
        }
        b = ovf
    }
}

数据竞态

数据竞态和内存访问冲突

在没有锁的情况下，一个 goroutine 可能正在读取一个键的值，而另一个 goroutine 同时修改同一个键或其附近的键（因为它们可能在同一个哈希桶中）。这种情况下，读操作可能遇到以下几种问题：

•	读取到部分写入的数据：如果写操作正在修改一个值，而这个值是分几步写入的（例如大型结构或多个字段），读操作可能会看到只写了一部分的数据。
•	无效的内存引用：如果写操作涉及到重新分配内存（如在扩容时），读操作可能引用了已经被释放或重新分配的内存。

Go 运行时的检测机制

从 Go 1.6 开始，Go 运行时增加了对并发访问 map 的检测。如果检测到并发读写，运行时会抛出一个 panic。这是一种保护机制，目的是防止程序在未知的、可能导致更严重问题的状态下继续运行。

底层细节：

在多核处理器环境中，各个核有自己的缓存。当对内存进行写操作时，变更可能首先在一个核的缓存中发生，稍后才通过复杂的缓存一致性协议被写回主内存。这意味着，如果一个核上的线程正在更新 map 的某个元素，而另一个核上的线程试图读取同一个 map，后者可能会看到以下情况之一：

•	已经写入缓存但未写回到主内存的数据：这可能导致读操作看到旧值。
•	部分更新的数据结构：如果写操作涉及多个步骤（例如先写键后写值），读操作可能在这些步骤完成之前发生，导致读取到不一致或不完整的数据。
  1. 编译器和处理器的指令重排序

编译器优化和处理器执行时的指令重排序也可能影响内存操作的实际执行顺序。例如，编译器可能重新排序某些写操作以提高效率，如果没有明确的内存屏障或锁来防止这种重排序，读操作可能会在写操作逻辑上完成之前实际发生，从而观察到不完整的数据。