Otherwise it would be more or less a violation of the pigeonhole principle. The insertion order is information, if you don't need to store that anywhere but you promise to give it back anyway that's a hole in your information theory.
It's easy enough (including by accident) to deliver insertion ordered iterator behaviour for small hash maps that have never had any items removed, but after that things get sticky very quickly.
There is no reason for that. A sorted list doesn't need more memory than an unsorted list. And an insertion-sorted map doesn't need to use more memory than a map that doesn't keep the order.
Independently, some properties we deem valuable are often side-products of the way the data-structure works. For example, an efficient binary search tree will naturally tend to be balanced. In the case of efficient hash maps, it is now common to add the key/value pair at the end of an internal vector. Maintaining the insertion order this way doesn't add any cost.
Firstly, and this is orthogonal to my original point, whenever people say "Cost" they actually silently mean "... that I care about" and so we're involuntarily obliged to agree to stop caring about anything else. Because of Hyrum's law even if you don't promise ordering (as Python's "Compact Dict" developer proposes at one point) your users will rely upon it and you're stuck with whatever you implemented. This is a real cost for a language or standard library. Look at the sad state of C++ standard collections.
But my main point is that the requirement for ordering forces you to dispose of otherwise permissible optimisations which could destroy the order. You actually ran head first into this in the article, when repeatedly removing and adding elements blows up by clogging your data structure with tombstones.
Swiss Tables wouldn't clog up with tombstones. Since they don't care about ordering they only need tombstones at all in uncommon special cases (specifically, if the entire rest of the group is full or tombstones), in most cases Swiss Tables get to just set removed (key, value) pairs as empty. But this optimisation isn't open to you.
>Because of Hyrum's law even if you don't promise ordering (as Python's "Compact Dict" developer proposes at one point) your users will rely upon it and you're stuck with whatever you implemented. This is a real cost for a language or standard library. Look at the sad state of C++ standard collections.
Yes but this cost goes away if you commit to it, and the alternative (like what go does) to force the order to change all the time also comes with a complexity cost vs. doing "nothing" and having the order be arbitrary and sometimes, but not actually, reliable.