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 lo

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-memory%20hash%20tables%20for%20accumulating%20text%20vocabularies.pdf http://www.mathcs.emory.edu/~whalen/Hash/Hash_Articles/In-me...