You may be wondering why you've been downvoted. Everyone knows that hash tables have a linear worst-case. However, hash functions have now advanced to the poi

You may be wondering why you've been downvoted. Everyone knows that hash tables have a linear worst-case. However, hash functions have now advanced to the point that malicious input is the only serious scenario where programmers need to concern themselves with that worst-case. Dumb, blind luck is so terribly unlikely using modern hash functions that programmers really don't need to concern themselves with it these days. While hash tables do heap allocations, they typically do large, infrequent allocations, when the hash table increases in size by some multiplicative factor. Trees, on the other hand, do many small allocations, frequently leading to significant fragmentation and allocator overhead. Even when that fragmentation and allocator overhead is avoided by advanced allocators (e.g., tcmalloc), trees are still much worse than hash tables in that they will typically require O(log n) cache line fills per lookup, rather than the one that hash tables require.