The eficiency of hash tables (insertions, in particular), is actually slightly worse than he indicates. They are not amortized O(1) for all data, but only for t

The eficiency of hash tables (insertions, in particular), is actually slightly worse than he indicates. They are not amortized O(1) for all data, but only for typical data (or on average over all possible data sets). To see this, suppose that every item inserted happens to go into the same bucket. The amortized time complexity is linear. On the other hand, insertion is not O(1) even for average data; there is always the periodic table resizing. So: amortized O(1) for average data, not O(1) for average data. The upshot of all this is that hash tables are still pretty good, but insertion is only constant time in a "double average" sense: on average over a large number of consecutive operations (amortization) and over all possible data sets. A note to those who say, "Why not just use a different hash function?": This can greatly decrease the probability of poor hash-table performance. But it does not change the worst case, unless we allow for an arbitrarily large number of hash functions, and one of them is guaranteed to be a good one. I've never seen this done (actually, I'm not sure anyone knows how to do it within reasonable efficiency constraints). And a note to those who say, "But in the real world it doesn't matter": No, sometimes it matters, and sometimes it doesn't. (Don't use Python to program a pacemaker ....)