I feel like often the opposite can be true as well. Obviously hashtables are better for large collections but often collections are very small (sizes typically

I feel like often the opposite can be true as well. Obviously hashtables are better for large collections but often collections are very small (sizes typically follow a power law; most strings will be smaller than the pointer to their first character; most collections will only have a few elements) and arrays can win here due to less indirection and better locality. Compare this to many functional languages (or lisps) where the most convenient data structure to hand is the singly linked list. It was already bad for performance when those languages were invented but in modern times they are relatively much worse than before. Sometimes I think that the performance of C programs come more from the fact that it such a massive pain to do anything in C that you can usually only do the simplest thing and this tends to be fast and reliable. The problem is that if you can’t do a simple thing it will either take a lot of refactoring or you’ll do a complicated thing and your program will randomly segfault. This is also my theory as to why languages like C have better libraries than lisp: it is such a monumental pain to do anything in C that people go to the small extra effort to package up their achievement into a library either for others or in case they need to solve the trivial problem again themselves. Improvements can them come later as needed but get shared. Compare this to, for example, lisp where the attitude is usually that libraries aren’t flexible enough and generally not that hard to implement yourself (so long as you aren’t so worried about data structures), and I think this is the reason there don’t tend to be so many libraries, especially for trivial things.