引擎盖下的地图

Question

在阅读了戴夫·切尼（Dave Cheney）关于Go的地图的博客文章之后，对我来说，还有几件事尚不清楚。

TLDR：

• 为什么它们无序？
• 实际值存储在哪里？

深入研究运行时程序包后，我发现基本的映射结构如下：

// A header for a Go map.
type hmap struct {
    // Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go.
    // Make sure this stays in sync with the compiler's definition.
    count     int // # live cells == size of map.  Must be first (used by len() builtin)
    flags     uint8
    B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
    noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
    hash0     uint32 // hash seed

    buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
    oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
    nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

    extra *mapextra // optional fields
}

buckets -是存储区数组，其中索引是键的哈希值的低位，其中存储区为：

// A bucket for a Go map.
type bmap struct {
    // tophash generally contains the top byte of the hash value
    // for each key in this bucket. If tophash[0] < minTopHash,
    // tophash[0] is a bucket evacuation state instead.
    tophash [bucketCnt]uint8
    // Followed by bucketCnt keys and then bucketCnt elems.
    // NOTE: packing all the keys together and then all the elems together makes the
    // code a bit more complicated than alternating key/elem/key/elem/... but it allows
    // us to eliminate padding which would be needed for, e.g., map[int64]int8.
    // Followed by an overflow pointer.
}

..好吧，这只是uint8每个项目是键的哈希值的第一个字节的数组。键值对存储为key/key value/value（每个存储桶八对）。但是到底在哪里？考虑到映射可能包含（几乎）任何类型的值。应该有某种指针可以放置在存储值数组的内存中，但bmap没有此类信息。

而且由于键的哈希值位于存储桶中的有序数组中，为什么每次我遍历地图时它的顺序都不同？

Answer 1

• 为什么它们无序？
  
  

因为这为运行时提供了 更大的自由
以实现映射类型。尽管我们知道Go的（当前）实现是一个哈希图，但语言规范允许使用任何地图实现（例如哈希图，树图等）。也不必记住顺序，这使运行时可以更有效地完成工作，减少使用记忆。

Adrian的评论很好地总结了很少需要订单，而始终保持订单是浪费。当您确实需要订购时，可以使用提供订购的数据结构。

而且由于键的哈希值位于存储桶中的有序数组中，为什么每次我遍历地图时它的顺序都不同？

Go的作者有意使地图的迭代顺序随机化（因此我们凡人不会依赖固定的顺序）。

• 实际值存储在哪里？
  
  

“ where”由指定hmap.buckets。这是一个指针值，它指向内存中的一个数组，该数组保存存储桶。

buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.

因此，hmap.buckets指向存储桶的连续内存段。存储桶由进行“建模”
bmap，但这不是其实际的内存布局。存储桶的开头是一个存储桶（tophash [bucketCnt]uint8）中存储键的最高哈希字节的数组，该数组
后面bucketCnt是存储桶的键，然后bucketCnt是存储桶的值。最后，有一个溢出指针。

将存储桶想像成这种 概念性 类型，它可以“可视化”键和值在内存中的位置：

type conceptualBucket struct {
    tophash     [bucketCnt]uint8
    keys        [bucketCnt]keyType
    values      [bucketCnt]valueType
    overflowPtr uintptr
}

注意：bucketCnt是一个编译时间常数，为8，它是存储桶可以容纳的密钥/元素对的最大数量。

当然，这种“图片”是不准确的，但是它给出了存储键和值的位置/方式的想法。