Yep, this is the thought process I had; a red-black tree or B-tree is something I'd consider for a map that needed sort order, and a hashmap would be what I'd use by default if I didn't care about order.
For additional context, I work almost entirely in Rust nowadays, and BTreeMap and HashMap are the two map types in the standard library (https://doc.rust-lang.org/std/collections/index.html). I've ended up needing insertion-ordered maps quite often in my work though, which is not something I've seen taught very often or in standard libraries, although there are plenty of third-party implementations out there, and in most languages it's not too difficult to hand-roll an implementation using an unordered map and a linked list by keeping both the value and a reference to the node containing the element in the map, which provides constant time insertion, lookup and deletion. (Rust is somewhat notorious for _not_ being a language where implementing something like this by hand is super easy though, since tracking mutable references to individual nodes of a linked list across separate hashmap values is not something the borrow checker is enthusiastic about)
For additional context, I work almost entirely in Rust nowadays, and BTreeMap and HashMap are the two map types in the standard library (https://doc.rust-lang.org/std/collections/index.html). I've ended up needing insertion-ordered maps quite often in my work though, which is not something I've seen taught very often or in standard libraries, although there are plenty of third-party implementations out there, and in most languages it's not too difficult to hand-roll an implementation using an unordered map and a linked list by keeping both the value and a reference to the node containing the element in the map, which provides constant time insertion, lookup and deletion. (Rust is somewhat notorious for _not_ being a language where implementing something like this by hand is super easy though, since tracking mutable references to individual nodes of a linked list across separate hashmap values is not something the borrow checker is enthusiastic about)