Article is about maps internal structure, hashes and performance. How data is actually stored inside. Basics overview Maps (aka associative arrays) is basically key-value storage with really fast lookup. Really basic example: m := ( [ ] ) m[ ] = value, exist := m[ ] make map int string 42 "Hello!" 42 // value = 42 // exist = true Also it is possible to use maps as sets: set := ( [ ] {}) _, exist := set[ ] exist { fmt.Println( ) } make map int struct 42 if "42 is in the set" struct{} is used because of the zero size. Check out small sample here https://play.golang.org/p/Ndn8UqxWYC3 Go deeper Under the hood maps is a hash table (aka hashmap). Sometimes search tree is also used to organize maps in some other languages and cases. Main idea of hash map is to have near-constant O(1) lookup time. Formally lookup time is O(n), in case if hash function gives n collisions, which is almost impossible in real situations. Hash and collisions By definition hash is a function that transforms any value to fixed-size value. In case of Go, it takes any number of bits and transform it to 64. Internal hash implementation could be found here: https://github.com/golang/go/blob/dev.boringcrypto.go1.13/src/runtime/hash64.go When hash function produces same results for different values, this is a collision. Most secure hash functions don't have known collisions. Brief hashmap theory To store key-value pairs, the most naive approach is to create a list and traverse all pairs each lookup with O(n) complexity. Not good. More advanced approach is to create balanced search tree and achieve stable O(log(n)) lookup efficiency, which is good for many cases. Ok, but what if we want to do it even faster? Fastest possible lookup is O(1), we have this speed with arrays. But we do not have keys suitable for array. Solution is to hash keys, and use hashes or part of hashes. Lets create BN buckets. Each bucket is a simple list. Hash function will transform keys like that: hash(key)->{1..BN} Adding new key-value to hashmap is inserting it in bucket. hash(key) Lookup time Let PN be the number of key-value pairs in hashmap. If we have PN ≤ BN and zero collisions, this is ideal case, lookup time is O(1). If PN > BN then at least one bucket will have at least 2 values, so lookup could take 2 steps - locate bucket, and simply iterate through bucket list, till key-value pair is found. Average number of items in buckets is called load factor. Load factor divided by 2 will be the average lookup time, and collisions rate will define dispersion of it. Formally the complexity is still O(n), but in practice collisions is rare enough and keys will spread to buckets almost evenly. Hashmap Go implementation Source code of map is here, and it’s more or less understandable https://github.com/golang/go/blob/master/src/runtime/map.go Maps is a pointer to structure. It is mutable! If you need a new one, you shall create a copy manually. hmap Another important thing, is that hash is based on random seed, so each map is built differently. h.hash0 = fastrand() I think, the idea behind this randomization is to avoid potential vulnerabilities when malicious actor will flood hashmap with collisions and to prevent any attempts to rely on map iteration order. Map is iterable, but not ordered. Even every new iterator of the same map is randomized. m := ( [ ] ) j := ; j < ; j++ { m[j] = j * } k, v := m { fmt.Printf( , k, v) } fmt.Printf( ) k, v := m { fmt.Printf( , k, v) } make map int int for 0 10 2 for range "%d*2=%d " "\n - - -\n" for range "%d*2=%d " // Second loop of the same map would produce different order of elements This code will print results in random order. Check out more code here https://play.golang.org/p/OzEhs4nr_30 Default map size is 1 bucket, bucket size is 8 elements. IRL hash functions usually return 32, 64, 256… bits. So we will take only part of this bits to use as a bucket number. So with 8 buckets, we need only log2(8)=3 low-order bits, (8=2³, for 16 log2(16)=4, 16=2⁴ and so on. bucket := hash & bucketMask(h.B) where h.B is log_2 of BN. Same as 2^h.B = BN bucketMask(h.B) is a simple h.B bits mask, like 00…011…1, where number of 1 bits is h.B Map grow If map grows beyond certain limits, Go will double the number of buckets. Each time number of bucket is increased, it is required to all map content. Under the hood, Go uses sophisticated map grow mechanism for optimal performance. For some time Go keeps old buckets along with new ones, to avoid load peaks and assure that already started iterators would finish safely. rehash Conditions of map grow from source code: overLoadFactor(h.count+ , h.B) || tooManyOverflowBuckets(h.noverflow, h.B) 1 First is a check. Average load of a buckets that triggers growth is This value is hard-coded and based on Go team benchmarks. load factor 6.5 or more. Second check is about overflow buckets count. “Too many” means (approximately) as many overflow buckets as regular buckets. Single bucket hard-coded capacity is 8 elements. When limit is reached, new overflow bucket is chained to full bucket. Interesting thing, that grow trigger is a bit randomized for large maps with ≥2¹⁶ buckets. { h.B < { h.noverflow++ } mask := ( )<<(h.B ) - fastrand()&mask == { h.noverflow++ } } func (h *hmap) incrnoverflow () // We trigger same-size map growth if there are // as many overflow buckets as buckets. // We need to be able to count to 1<<h.B. if 16 return // Increment with probability 1/(1<<(h.B-15)). // When we reach 1<<15 - 1, we will have approximately // as many overflow buckets as buckets. uint32 1 -15 1 // Example: if h.B == 18, then mask == 7, // and fastrand & 7 == 0 with probability 1/8. if 0 Hack map with Unsafe To gather more information, we need to access map internal values, like h.B and buckets content. This will work as is only if internal structure of wont change, this tested for 1.13.8 hmap We need to convert map builtin to struct, in order to gather map internal data. The trick is to use and empty interface. First we convert map pointer to , then convert to struct, this struct matches actual empty interface internal struct. From that struct we could acquire type of map as and struct. hmap unsafe.Pointer &m unsafe.Pointer emptyInterface hmap emptyInterface { _type unsafe.Pointer value unsafe.Pointer } { ei := (*emptyInterface)(unsafe.Pointer(&m)) (*maptype)(ei._type), (*hmap)(ei.value) } type struct func mapTypeAndValue (m {}) interface (*maptype, *hmap) return And use it like this: m := ( [ ] ) t, hm := mapTypeAndValue(m) make map int int We need to copy some constants, structs and functions from Go sources sources version should match compiler version. maptype, hmap src/runtime/map.go, Now we can trace, how map structure buckets number changes with adding new elements. m := ( [ ] ) _, hm := mapTypeAndValue(m) fmt.Printf( ) prevB i := ; i < ; i++ { m[i] = i * hm.B != prevB { fmt.Printf( , hm.count, hm.B, <<hm.B) prevB = hm.B } } make map int int "Elements | h.B | Buckets\n\n" var uint8 for 0 100000000 3 if "%8d | %3d | %8d\n" 1 Code snippet - https://play.golang.org/p/NaoC8fkmy9x Elements | h.B | Buckets 9 | 1 | 2 14 | 2 | 4 27 | 3 | 8 53 | 4 | 16 105 | 5 | 32 209 | 6 | 64 417 | 7 | 128 833 | 8 | 256 1665 | 9 | 512 3329 | 10 | 1024 6657 | 11 | 2048 13313 | 12 | 4096 26625 | 13 | 8192 53249 | 14 | 16384 106497 | 15 | 32768 212993 | 16 | 65536 425985 | 17 | 131072 851969 | 18 | 262144 1703937 | 19 | 524288 3407873 | 20 | 1048576 6815745 | 21 | 2097152 13631489 | 22 | 4194304 27262977 | 23 | 8388608 54525953 | 24 | 16777216 Now let's see how buckets are filled! I will ignore overflow buckets content, for relative simplicity. struct contains pointer to where cells stored in memory. Next we traverse trough memory to acquire all values inside map buckets. Here we need and from to calculate right offsets for buckets and cells. Hmap buckets keysize bucketsize maptype { dataOffset = unsafe.Offsetof( { tophash [bucketCnt] cells }{}.cells) t, h := mapTypeAndValue(m) fmt.Printf( , h.noverflow) numBuckets := << h.B r := ; r < numBuckets*bucketCnt; r++ { bucketIndex := r / bucketCnt cellIndex := r % bucketCnt cellIndex == { fmt.Printf( , bucketIndex) } b := (*bmap)(add(h.buckets, (bucketIndex)* (t.bucketsize))) b.tophash[cellIndex] == { } k := add(unsafe.Pointer(b), dataOffset+ (cellIndex)* (t.keysize)) ei := emptyInterface{ _type: unsafe.Pointer(t.key), value: k, } key := *(* {})(unsafe.Pointer(&ei)) fmt.Printf( , key.( )) } fmt.Printf( ) } { m := ( [ ] ) i := ; i < ; i++ { m[i] = i * } showSpread(m) m = ( [ ] ) i := ; i < ; i++ { m[i] = i * } showSpread(m) } func showSpread (m {}) interface // dataOffset is where the cell data begins in a bmap const struct uint8 int64 "Overflow buckets: %d" 1 for 0 if 0 "\nBucket %3d:" // lookup cell uintptr uintptr if 0 // cell is empty continue uintptr uintptr interface " %3d" int "\n\n" func main () make map int int for 0 50 3 make map int int for 0 8 3 Due to randomized nature of map hash generation, each run result for map bigger than 8 values would be different. Notice that very small map will work just like list! Result example: Overflow buckets: 3 Bucket 0: 26 28 Bucket 1: 0 2 7 8 13 22 31 38 Bucket 2: 6 9 11 16 21 34 35 37 Bucket 3: 1 4 12 14 29 42 48 Bucket 4: 10 32 45 46 Bucket 5: 15 30 33 43 Bucket 6: 25 47 Bucket 7: 3 5 17 18 19 20 23 24 Overflow buckets: 0 Bucket 0: 0 1 2 3 4 5 6 7 Code snippet https://play.golang.org/p/xgyQEatPHgT Predefined size Sometimes you now, how many items you need to put in map. For maps with known size, is better to specify size at the moment of creation. Go will automatically create suitable number of buckets, so expenses of grow process could be avoided. m := ( [ ] , ) _, hm := mapTypeAndValue(m) fmt.Printf( ) fmt.Printf( , hm.count, hm.B, <<hm.B) i := ; i < ; i++ { m[i] = i * } fmt.Printf( , hm.count, hm.B, <<hm.B) make map int int 1000000 "Elements | h.B | Buckets\n\n" "%8d | %3d | %8d\n" 1 for 0 1000000 3 "%8d | %3d | %8d\n" 1 Result: Elements | h.B | Buckets 0 | 18 | 262144 1000000 | 18 | 262144 Code snippet https://play.golang.org/p/cnijjiKwM8o Deletion and ever growing map What you should know about Go builtin maps, that they can . Even if you delete all values from map, number of buckets will remain the same, so is memory consumption. only grow m := ( [ ] ) _, hm := mapTypeAndValue(m) fmt.Printf( ) i := ; i < ; i++ { m[i] = i * } i := ; i < ; i++ { (m, i) } fmt.Printf( , hm.count, hm.B, <<hm.B) make map int int "Elements | h.B | Buckets\n\n" for 0 100000 3 for 0 100000 delete "%8d | %3d | %8d\n" 1 Result: Elements | h.B | Buckets 0 | 14 | 16384 Code snippet https://play.golang.org/p/SPWixru8sdM Links and thanks All code mentioned in article could be found here: https://github.com/kochetkov-av/golang-map-insights Big thanks to author of and of course to The Go Authors! https://lukechampine.com/hackmap.html
