The part I find particularly silly is where he writes: For example, assume that the hash table implementation shrinks the table if the number of full bucke

The part I find particularly silly is where he writes: For example, assume that the hash table implementation shrinks the table if the number of full buckets drops below half, and grows the table if it becomes over full. If the table starts out with 100 buckets, and the number of buckets falls to 49, the size is shrunk to 50. I've never seen a hashtable that actually works this way. It's common knowledge that performance of hashtables degrades long before the "full" point. (I particularly like the explanation of that here: http://eigenclass.org/R2/writings/separate-chaining-vs-double-hashing http://eigenclass.org/R2/writings/separate-chaining-vs-doubl...)