3 ms·
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
by KirinDave 8y ago
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.
- ww520 8y agoSince 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.
- KirinDave 8y agoThe 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.