Don’t write complex optimizations until you know you need them, but I think defaulting to code with good O(N) complexity, where it’s simple to do so, is a good default.
The philosophy is really to not waste time implementing optimizations that may not be necessary. Naturally you should reach for the best tool you have in your tool box. So if you language of choice has a hashmap that can be used with no additional work, go for it. But don't wait two days rolling your own red-black tree because it might be better.
Are you sure that std::unordered_map is faster than std::vector? Did you measure?
Every time you access an element in std::vector, you also access nearby ones (thanks to L1 cache, as well as CPU-prefetching of in-line data).
In contrast, your std::unordered_map or hash-table has almost no benefits to L1 cache. (It should be noted that linear-probing, despite being a O(N^2) version of hash-tables worst-case, is actually one of the better performers due to L1 cache + prefetching)
Using maps or sets nowadays is mostly for clarity, as they are used to solve certain kind of problems.
If you need a set, use a set. But don't assume that its faster than a std::vector.
Even then, std::vector has set-like operations through binary_search or std::make_heap in C++, so it really isn't that hard using a sorted (or make_heap'd) std::vector in practice.
--------
Even if you don't plan on doing optimization work, its important to have a proper understanding of a modern CPU. The effects of L1 and prefetching are non-trivial, and make simple arrays and std::vectors extremely fast data structures, far faster than compared to 80s or 90s computers anyway. A lot of optimization advice from the past has become outdated because of the evolution of CPUs.
So its important to bring up these changes in discussion, from time to time, to remind others to restudy computers. Things change.
But inserting into sorted std::vector is o(n log n) in worst case right? (As you have to binary search the position and move other elements). But a hash set with linear probing can give O(1) (amortized) access, while usually maintaining an invariant like total_size > 2*n. I don't think that would be such an impact on cache locality. Linear probing doesn't require linked lists.
Of course this is given that you have a data structure in standard library. But at this point I think hash sets are pretty standard.
Perhaps linear probing is a better example of how BigO analysis can go wrong on modern architectures. Inserting into a hashset with linear-probing is O(n) worst-case, while inserting into a linked list is always O(1) (best case, worst case, and average case).
And yet, linear probing seems to work out best in practice (with a bit of rigging. The total_size > 2*n invariant is one, but so does Robin-hood hashing if you want to keep the table small)
Linear probing vs Linked List implementations of hash-sets seems to be a more clear example of an O(1) vs O(n) anomaly, where the O(n) example is superior.
Inserting into linked list assumes you have found the node to insert in.
I don't remember exact details but in hash set with linear probing, the worst case happens quite rarely given the hash function is good one (which are quite sophisticated these days). It is O(1) amortized. The same applies for hash table with chaining too, that all of your keys may go to same bucket given a sufficiently bad hash function.
Given the other choices, like (as far as I know) SkipList based or tree based variants, hash sets are obvious choice.
Hash-set with Linked List is O(1) all cases.
Hash-set with linear-probing is O(n) worst-case insertion. But happens to be faster in practice with circa 2020-style CPUs (especially with Robin Hood insertion)
Assume the load-factor to be 90%+, so that we actually get a reasonable difference between the two strategies. We have a situation where O(n) is better than O(1).
Except std::vector does not enforce the sorted or heap constraints when adding or removing elements so eventually someone working on your code will break them.
Hmmm... I argue that the hash is nearly free actually.
An unordered_map traversal is probably DDR4 latency bound. That's ~50-nanoseconds (200 clock ticks) per access. What's the CPU going to do in that time?
Well, spending 10 to 20 clock ticks on a typical hash algorithm is fine. Then it will wait the other 180 clock ticks for RAM. If you got hyperthreading, maybe the CPU will go to another thread and do meaningful work while waiting for RAM... but... I think you get the gist.
Even IF the hash were free, the CPU is waiting for RAM anyway. So you got plenty of time to make that hash worthwhile. Even an integer division/modulo operator (worst case ~80 clock ticks) can fit in there while waiting for RAM, with plenty of room to spare.
I guess if everything was in L1 cache, the story is a bit different. A lot of "depends", depends on the data, the access frequency, etc. etc.
If you can't guarantee n is small, I think it is entirely sensible to use a dictionary/hash table instead of looping over an array or list. As long as n is small the overhead is probably irrelevant, and it'll prevent surprises if n gets large as you said. And if the difference actually matters, you get back to rule 1 and 2 and measure first anyway.
On the other hand, the idea that one might be setting traps is slightly weird... if you _know_ 90% that n will be large then pick an algorithm that's efficient (and since it's easy to implement, it's a win-win). If n is always going to be small, then does the choice really matter?
If you are writing the code yourself then the maintenance costs of everyone else after you trying to understand it makes it wrong. However most programming languages have generic programing features such that you can just use an algorithm and so you aren't writing either the algorithm. In that case the code for the fast hash is equal to the O(n^2) code and so of course you select the faster one as a application of don't prematurely pessimise your code rule. If your programing language doesn't already have built in generic algorihtms for your data, then you are using the wrong language (unless your job is to write the generic algorithms for the language in which case this doesn't apply because you can assume your algorithm will be used in a performance critical part at some time)
If I know beforehand we'll handle a lot of data, I can pick something fast and complex to begin with, but that effort is probably mostly a waste.