Go 的底层地图

Question

总而言之：

• 为什么它们是无序的？

• 实际值存储在内存中的什么位置？

在深入研究运行时包后，我发现底层地图结构如下：

// 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 的（当前）实现是哈希图，但语言规范允许使用任何映射实现，例如哈希图、树图等。而且不必记住顺序，这允许运行时更有效地完成其工作并使用更少的资源记忆。阿德里安的评论很好地总结了秩序是很少需要的，总是维持秩序将是一种浪费。当您确实需要顺序时，可以使用提供顺序的数据结构。由于密钥的哈希值位于存储桶内的有序数组中，为什么每次我循环遍历地图时它的顺序都不同？Go 作者有意将 Map 的迭代顺序随机化（这样我们凡人就不会依赖于固定的顺序）。实际值存储在内存中的什么位置？“哪里”由 指定hmap.buckets。这是一个指针值，它指向内存中的一个数组，一个保存桶的数组。buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.Sohmap.buckets指向保存存储桶的连续内存段。存储桶是由 来“建模”的bmap，但这不是它实际的内存布局。存储桶以一个数组开始，该数组保存存储桶 ( tophash [bucketCnt]uint8) 中键的顶部哈希字节，该数组后面是bucketCnt存储桶的键，然后是bucketCnt存储桶的值。最后还有一个溢出指针。将存储桶想象成这样的概念类型，它“可视化”键和值在内存中的位置：type conceptualBucket struct {    tophash     [bucketCnt]uint8    keys        [bucketCnt]keyType    values      [bucketCnt]valueType    overflowPtr uintptr}注意：bucketCnt是一个编译时间常数8，它是一个桶可以容纳的键/元素对的最大数量。当然，这个“图片”是不准确的，但它给出了键和值存储在哪里/如何存储的想法。