I think the operative word is "premature". If you actually have a reasonable idea of how much data you're going to be working with, it's not premature at that point to put some time into optimization.

Also, I would restate the rule as something like "don't spend too much time prematurely optimizing. If you're building a lookup, it's obviously a Good Thing to use a hash instead of a linked list, and in 99% of cases shouldn't take you any longer to code.