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...