This was posted on HN recently. Skip to slide 18. In it, the guy talked about premature optimization, curiously, of the same thing: linear iteration over an array vs using a hash implementation.
His example was that in his youth, he was on the Doom forums, and he was doing mods, and took a look at the code that loaded the different asset files. And he was abhorred that the code used an array to linearly iterate over to find the asset to load. He started complaining on the newsgroups, and then Doom guys said you don't know what you're talking about, etc.
In this case, it was where that code just didn't matter in terms of run time, because the order of magnitude difference in looking up an asset and actually loading the asset was huge, and it just didn't matter. And because they used a dumb implementation, they could optimize for developer productivity and go on to code that mattered, like the rendering.
That said, I think the thing to keep in mind is, which parts of your problem space is of the core importance, and keep an eye on difference of order of magnitude in the different solutions you were thinking about implementing