People keep skipping a word and a qualifier. The precise description is "hash tables with appropriately chosen growth condition have amortised insert cost of O(1)". The amortised bit effectively hides the occasional rehashing. (It's about throughput, not latency)