2 ms·
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(
by viraptor 7y ago
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)
- loeg 7y agoRehashing can be done incrementally; aside from the additional memory allocation, incremental rehashing can be O(1) rather than O(n).