News for hackers. Stuff that matters.

A comment on Finding unique items: hash vs. sort. Parent comment

Re:Finding unique items: hash vs. sort by matvore on Wednesday January 08, 2020 @12:32AM (#21988639)
No, it's still O(N) amortized. Imagine if the hashmap doubles in capacity whenever it is full or hits its max load factor. Then you end up having O(N) copy operations. O(2 * N) = O(N)
[ Parent | on HN ]
Re:Finding unique items: hash vs. sort by yxhuvud on Wednesday January 08, 2020 @02:06AM (#21989042)
While your objection stands, repeated trainings of a hash table can be very impactful on the actual walltime spent, and it is a bad benchmark not to include the optimization of preallocating.
[ Parent | on HN ]