[eru]

Some implementations have O(n) access in the worst case.

Often people are interested in something like the 99.9999%ile case. And, of course, you can design hash tables with better worst case behaviour.

It's almost trivial to get a hash table with O(log n) worst case access: when you have a collision, just resolve it with a tree instead of a linked list.

With some more fancy math, you can also get O(1) amortized worst case behaviour with arbitrarily high probability that doesn't depend on your input data.