總而言之：為什么它們是無序的？實際值存儲在內存中的什么位置？在深入研究運行時包后，我發現底層地圖結構如下：// 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沒有此類信息。由于密鑰的哈希值位于存儲桶內的有序數組中，為什么每次我循環遍歷地圖時它的順序都不同？
1 回答
米琪卡哇伊
TA貢獻1998條經驗 獲得超6個贊
為什么它們是無序的？
因為這為運行時實現地圖類型提供了更大的自由。雖然我們知道 Go 的（當前）實現是哈希圖，但語言規范允許使用任何映射實現，例如哈希圖、樹圖等。而且不必記住順序，這允許運行時更有效地完成其工作并使用更少的資源記憶。
阿德里安的評論很好地總結了秩序是很少需要的，總是維持秩序將是一種浪費。當您確實需要順序時，可以使用提供順序的數據結構。
由于密鑰的哈希值位于存儲桶內的有序數組中，為什么每次我循環遍歷地圖時它的順序都不同？
Go 作者有意將 Map 的迭代順序隨機化（這樣我們凡人就不會依賴于固定的順序）。
實際值存儲在內存中的什么位置？
“哪里”由 指定hmap.buckets。這是一個指針值，它指向內存中的一個數組，一個保存桶的數組。
buckets????unsafe.Pointer?//?array?of?2^B?Buckets.?may?be?nil?if?count==0.
Sohmap.buckets指向保存存儲桶的連續內存段。存儲桶是由 來“建?！钡?code>bmap，但這不是它實際的內存布局。存儲桶以一個數組開始，該數組保存存儲桶 (?tophash [bucketCnt]uint8) 中鍵的頂部哈希字節，該數組后面是bucketCnt存儲桶的鍵，然后是bucketCnt存儲桶的值。最后還有一個溢出指針。
將存儲桶想象成這樣的概念類型，它“可視化”鍵和值在內存中的位置：
type conceptualBucket struct {
? ? tophash? ? ?[bucketCnt]uint8
? ? keys? ? ? ? [bucketCnt]keyType
? ? values? ? ? [bucketCnt]valueType
? ? overflowPtr uintptr
}
注意：bucketCnt是一個編譯時間常數8，它是一個桶可以容納的鍵/元素對的最大數量。
當然，這個“圖片”是不準確的，但它給出了鍵和值存儲在哪里/如何存儲的想法。
- 1 回答
- 0 關注
- 133 瀏覽
添加回答
舉報
0/150
提交
取消