[SeanLuke]

< 293 MB <-- After we remove 1 million elements

Let's be kind and assume that prior to removal, the map has just trebled in size and the extra space wasn't used. Doesn't this imply that a map has an overhead of about 100 bytes per key/value pair? How can this be so?

[skywhopper]

There's some some waste involved in not pre-allocating the map to begin with. Check the output of this variation (https://go.dev/play/p/vQwg3GajzXx -- n shrunk to 1,000 to stay within the playground's memory constraints) which fills the map again after the GC. You'll see the map doesn't grow back to the max size.

And if you specify the size of the map up front in the `make()` function, it never grows or shrinks (or not significantly): https://go.dev/play/p/AGW35kMMOc5

IIRC, what's happening is that whenever the map hits what was pre-allocated, it expands by a certain growth factor of the current size. So at some point between 1 and 1,000,000 a big chunk was allocated that went over what was necessary for 1,000,000 entries. In my testing it happened around i == 851_500:

   i == 851000: 258507 KB
   i == 852000: 479212 KB

[SeanLuke]

Hashtables often treble when they reach 50% utilization. I think I'm already factoring that in. It's still 100 bytes overhead!

[EdiX]

If you are referring to the change from 461 MB to 293 MB that's because he didn't call runtime.GC right after the insertion loop.