News for hackers. Stuff that matters.
Re:Why databases use ordered indexes but programming uses ha... by viraptor on Tuesday December 10, 2019 @12:37AM (#21749907)
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)
Re:Why databases use ordered indexes but programming uses ha... by loeg on Tuesday December 10, 2019 @12:44AM (#21749946)
Rehashing can be done incrementally; aside from the additional memory allocation, incremental rehashing can be O(1) rather than O(n).