Cycle Sort

"But," you say, "Hashing a value is O(k), where k is at least log n. Therefore hash tables only support O(log n) access and update, not O(1)." It's become a quite fashionable gotcha, as your upvotes indicate.

The problem is, it's wrong. It's correct in a vacuous, put-it-in-a-footnote sense, but not in any real sense, the way we actually talk about data structures in computer science.

We have a longstanding tradition in computer science of ignoring the O(k) operations that you want to ascribe to hashing. The most relevant example of where we ignore that factor is in--you guessed it--balanced binary trees used as dictionaries. Comparison, like hashing, is also O(k), where k is >= log n. So in the technical sense you're espousing, a balanced binary tree would offer O(log n log n) access and update, rather than the O(log n) access and update that everyone describes it as.

Of course, in reality, everyone considers comparison to be O(1), and thus they say that balanced binary trees have O(log n) lookup. Likewise, everyone considers hashing to be O(1) since it's in the same class of operations as comparison, and thus they say that hash tables have O(1) lookup. This is how the real world of computer science actually talks about things, fashionable Internet objections notwithstanding.

(This is all covered in CLRS, of course, but no one seems to be able to look things up in books anymore. "We assume that the hash value h(k) can be computed in O(1) time...If the number of hash-table slots is at least proportional to the number of elements in the table, we have `n = O(m)` and, consequently, `alpha = n/m = O(m)/m = O(1)`. Thus, searching takes constant time on average. Since insertion takes O(1) worst-case time and deletion takes O(1) worst-case time when the lists are doubly linked, all dictionary operations can be supported in O(1) time on average.")

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.