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，它是一个桶可以容纳的键/元素对的最大数量。

当然，这个“图片”是不准确的，但它给出了键和值存储在哪里/如何存储的想法。