> any sort of generic ordered container that supports O(n) iteration must necessarily require O(n log n) work to construct in the average case

This doesn't apply if the order you want is insertion order.

These hash maps are constructed in O(n) on average, just like any other hash maps.

Java's LinkedHashMap is also constructed in O(n).