Golang Map内部实现原理解析与疑难问题探讨 [深度剖析]

Golang Map内部实现原理解析与疑难问题探讨 [深度剖析] 请纠正我的理解：当一个桶有8个条目时，会创建一个新桶并链接到这个已满的桶。这不会触发重新计算映射中所有元素的哈希码。

然而，当平均每个桶的元素超过6.5个时，将触发调整大小。

问题：

  1. 如果一个映射有10个桶，其中4个桶有一个额外的链接桶，总共14个桶——那么映射会调整大小并分配一个包含28个桶的数组吗？
  2. 如果映射有9个桶，只有8个在桶数组中，一个是链接的，如果现在需要调整大小，新的桶数组不应该是能容纳所需桶数的最小2的幂吗？即32个桶而不是19个？
  3. 如果我想读取/写入一个元素，其哈希函数决定它属于桶B，而桶B有另一个链接桶，Go运行时会遍历这两个桶（它们对应的哈希数组）直到找到我的元素/一个空闲位置吗？
  4. 当做出调整大小的决定时，它只会分配新内存，而实际的复制和哈希码的重新计算，是在每次未来的读取/写入操作中完成的吗？就像每次新的读取/写入复制一个新桶（或单个条目）——并且这种桶的移动不是在确定映射需要调整大小的初始读取/写入操作中一次性完成的？
  5. 调整大小是否仅在每个桶平均拥有超过6.5个元素时触发，这个计数是否包含链接桶（在计算现有桶数时）还是只计算桶数组的大小而不关心链接桶的数量？
  6. 调整大小是否由其他因素触发？以下是一个博客中的例子： LOAD 6.50 %overflow 20.90 bytes/entry 10.79 hitprobe 4.25 missprobe. 6.50 因此，如果元素数/桶数小于6.5，但hitprobe大于4.2，那也会触发调整大小吗？
  7. 一个桶如何在同一个[]byte中存储键值对。这是否是为了避免仅为键/值类型，也为键/值内部的字段进行地址对齐填充？也就是说，如果键内部有一些填充，这个填充也会出现在桶存储其8个键和值的字节切片中吗？
  8. 对于一个新元素，计算其哈希函数。得到的哈希码被分成两部分，高位和低位。低位将决定它被放置在哪个桶中。在给定的桶中，高位被存储到一个数组中，当检索元素时（计算了这个新键的哈希码后），会遍历这个高位数组以寻找匹配。当两个元素具有相同的哈希码时会发生什么？这个高位数组会包含重复的值吗？

请给我建议。我已经看了一些博客和部分代码（https://github.com/golang/go/blob/master/src/runtime/map.go），但我仍然不清楚。


更多关于Golang Map内部实现原理解析与疑难问题探讨 [深度剖析]的实战教程也可以访问 https://www.itying.com/category-94-b0.html

1 回复

更多关于Golang Map内部实现原理解析与疑难问题探讨 [深度剖析]的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


1. 关于桶满时的处理

你的理解基本正确。当一个桶有8个条目时，会创建溢出桶（overflow bucket），但不会立即触发rehash。只有当负载因子超过6.5时，才会触发扩容。

2. 问题解答

问题1：扩容计算

// 假设当前有10个桶，4个溢出桶，总共14个桶
// 当触发扩容时，新桶数 = 旧桶数 * 2 = 20个桶
// 但Go会取最接近的2的幂，所以实际分配32个桶
// 你的理解有误：不是28个桶，而是32个桶

问题2：2的幂分配

// 当前9个桶（8个主桶+1个溢出桶）
// 触发扩容时，新桶数 = 旧桶数 * 2 = 18个桶
// 取最接近的2的幂 = 32个桶
// 你的理解正确：是32个而不是19个

问题3：查找过程

// 查找元素的过程：
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    // 1. 计算哈希
    hash := t.hasher(key, uintptr(h.hash0))
    
    // 2. 确定桶位置
    m := bucketMask(h.B)
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
    
    // 3. 遍历桶链（包括溢出桶）
    for ; b != nil; b = b.overflow(t) {
        for i := 0; i < bucketCnt; i++ {
            // 比较tophash和key
            if b.tophash[i] == top {
                k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
                if t.key.equal(key, k) {
                    // 找到key
                    v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
                    return v
                }
            }
        }
    }
    return unsafe.Pointer(&zeroVal[0])
}

问题4：渐进式rehash

// 扩容是渐进式的，在hmap中维护两个字段：
type hmap struct {
    // ...
    oldbuckets unsafe.Pointer  // 旧桶数组
    nevacuate  uintptr         // 迁移进度
    // ...
}

// 每次读写操作时迁移1-2个桶
func growWork(t *maptype, h *hmap, bucket uintptr) {
    // 迁移指定桶
    evacuate(t, h, bucket&h.oldbucketmask())
    
    // 如果还有待迁移的桶，再迁移一个
    if h.growing() {
        evacuate(t, h, h.nevacuate)
    }
}

问题5：负载因子计算

// 负载因子 = 元素总数 / 桶总数（包括溢出桶）
// 源码中的计算：
func overLoadFactor(count int, B uint8) bool {
    return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}
// bucketCnt = 8, loadFactorNum = 13, loadFactorDen = 2
// 所以阈值是 6.5

问题6：其他触发条件

// 除了负载因子，还有溢出桶过多的情况
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
    if B > 15 {
        B = 15
    }
    return noverflow >= uint16(1)<<(B&15)
}

// 在mapassign函数中：
if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
    hashGrow(t, h)
    goto again
}

问题7：内存布局

// 桶的内存布局（以map[int64]int64为例）：
type bmap struct {
    // tophash数组（8个字节）
    tophash [bucketCnt]uint8
    
    // 接下来是8个key
    // 然后是8个value
    // 最后是溢出桶指针
}

// 实际内存：|tophash[8]|keys[8]|values[8]|overflow|
// 这种布局避免了为每个key/value单独对齐的开销

问题8：哈希冲突处理

// 当两个key哈希值完全相同时：
// 1. tophash数组会存储相同的值
// 2. 通过key的完整比较来区分
// 3. 查找时需要遍历所有相同tophash的条目

// 示例：
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    // ...
    for ; b != nil; b = b.overflow(t) {
        for i := 0; i < bucketCnt; i++ {
            if b.tophash[i] == top {
                k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
                // 即使tophash相同，也要比较完整的key
                if t.key.equal(key, k) {
                    // 找到匹配
                }
            }
        }
    }
    // ...
}

关键点总结

  1. 扩容时机：负载因子 > 6.5 或 溢出桶过多
  2. 新桶数量：总是2的幂，至少是旧桶数的2倍
  3. 查找过程：遍历主桶和所有溢出桶
  4. rehash方式：渐进式，每次操作迁移1-2个桶
  5. 内存布局：连续存储tophash、keys、values以减少内存碎片
  6. 哈希冲突：通过完整key比较解决哈希值完全相同的情况
回到顶部