[blyzz]

Supporting insertion order is straightforward (but has some trade-offs) - you store the values in a backing array or linked list, and the hash table array stores pointers to the values.

You could do something similar with a sorted data structure backing the hashmap to get sorted order (a b-tree or something similar).

You could have the hash function preserve order at the cost of it being a very bad hash function. If you had n buckets, then the first 1/n elements in the keyspace would map to bucket 0, then next 1/n elements map to bucket 1, etc.