All of this is true, and yet an awful lot of the time in practice, the hash will perform worse than the array.

I was pretty shocked when I discovered this fresh out of school, but in the real world, an awful lot of collections have very few members.

Remember, that O(1) conceals some constant number, and that number is pretty darn big for a hash table.

Also, setting up a hashtable isn’t cheap, and it’s also significantly larger than a plain old array.

So if you have a small number of elements — anecdotally, a rule I have heard is “less than sixteen”, but I have no idea what that’s based on — it might well be that an array will perform better all around.

(But there’s no substitute for benchmarking…)