Comment by robertlagrant

I think people do say a hash table is O(1). It's the average time complexity (for some value of average) though, not the worst case.