> How do you preserve insertion order in a hash map?

You enhance the stored elements to also be the nodes of a doubly linked list. The overhead is rarely critical in practice. It can be made more efficient if the hash map doesn’t need to support deletion.

> The overhead is rarely critical in practice.

Depends; you add two extra pointers for each element, so your int → int hash table balloons in size.

I repeat: This is rarely critical in practice. Of course there are cases where it becomes critical, but it’s a perfectly good default.

Ah yeah, I've implemented LRU caches this way (hash map with an intrusive linked list overlayed on the values) but didn't put 2 and 2 together :)

Kind of? It usually means you've compromised the data structure somehow but occasionally it shows up incidentally.

For example, if you append the keys/values to an arena instead of inline in the hash you get a different set of performance tradeoffs. However insertion order is then available by walking the arena.

Appending to an arena in the background is a decent choice for variably sized data, as opposed to heap allocating everything one at a time. That probably has to store the size of each item, hence a forward iterator over the arena at zero cost. Minor quibbles around deleting and tombstones notwithstanding.

If your hash map uses open addressing, instead of a sparse array of pair<key, value>, you can have a vector<pair<key,value>> and a sparse array holding offsets into the vector. Depending on the sizes of keys, values, and offsets, as well as the average loading factor, this might or might not save space.

If your hash map uses chaining, then you weave an extra doubly linked list through your entries (see OpenJDK's OrderedHashMap, for a pretty readable open source example).