News for hackers. Stuff that matters.

A comment on Removing Array Duplicates. Parent comment

Re:Removing Array Duplicates by KirinDave on Friday April 12, 2019 @11:07AM (#19645427)
Many hash tables use tree structures rather than actual key hashing because it turns out that this is usually faster on modern machines. So many hash tables are technically O(n log n) for some high log factor like 32.

I've posted what I think is the optimal solution and the research behind it above, if you're curious how to hit O(n) time without brutal constants.

[ Parent | on HN ]
Re:Removing Array Duplicates by ww520 on Friday April 12, 2019 @08:47PM (#19650326)
Since the array size is known ahead of time, it's easy to initialize a hash table with an optimal capacity. No need to use fancy tree structure.
[ Parent | on HN ]
Re:Removing Array Duplicates by KirinDave on Saturday April 13, 2019 @01:35AM (#19651274)
The size of the table isn't the trick. It's the perfect hash function that you want. If you have that then you've already solved the problem at hand.
[ Parent | on HN ]