kroidkrensen

I ran experiments back in the day that varied the size of the hash table, and tried extremes where there were extremely long chains (high collisions). Take a look at pages 274 and 275, you'll be perhaps surprised how fast hash tables are when there are collisions -- especially if you use the move-to-front heuristic. (I agree with the other comments that the article is primarily concerned with the read use case.) http://www.mathcs.emory.edu/~whalen/Hash/Hash_Articles/In-me...

There are two articles that are linked to in the text, one that describes comparisons of binary tress, self-adjusting tress, and hash tables. There's a second article that compares B-trees, hash tables, and a few other structures -- that's this one: http://ww2.cs.mu.oz.au/~jz/fulltext/acmtois02.pdf

I'm the author of the article. I've tried that -- the downside is that the data structures (nodes in particular) take more space, and have more costs to manage / reorganize. Using a linked list with move-to-front-on-access works better in all experiments I've tried.

I;'m the author. It's not hand waving, it's an attempt to write a simple, approachable article -- I'm not trying to be Knuth.

If you want details, read the two articles that are linked into the text -- in those I delve into plenty of details, and include real-world experiments.