Finding unique items: hash vs. sort

Re:Finding unique items: hash vs. sort by nartz on Tuesday January 07, 2020 @11:12PM (#21988236)

Right well, its clear that at least in java, he doesn't pre-allocate the size of the hashmap. Thus, when the hashmap hits its maximum size, of course the resize operation has to copy all of the data into a new map, which makes this no longer O(N) but something like O(NlogN) or O(N^2) depending.

[ Parent | on HN ]

Re:Finding unique items: hash vs. sort by aidenn0 on Wednesday January 08, 2020 @12:32AM (#21988636)

If you do O(N) work every time the hashmap is "full" and double the size of the hashmap, it's still O(N).

Hand-wavy proof:

If your last insert caused a rehash, then you have done O(N) work plus O(N/2) plus O(N/4)... the limit of which is equal to O(2N), and thus only a constant factor more.

[ Parent | on HN ]

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 ]