Re:Myths about Hash Tables
by aidenn0 on Monday October 01, 2012 @06:11PM
(#4599612)
Indeed, I find academia is averse to hashtables (because of the poor worst-case performance) but engineers think they are the best thing since sliced bread.
[ Parent
| on HN ]
This "worst-case" issue seems silly to me.
If all your elements magically hash to the same bucket somehow and you end up having to make a list or a tree out of them, you're still no worse off than if you used a list or a tree in the first place.
Most hash-table implementations either re-hash or use an O(n) lookup structure. And replace "magically" with "a malicious attacker" and you see it does come up more often.
Though in general, you are right that academics tend to be over-obsessed with worst-case performance; see e.g. heap-sort.
Agreed! And taken to the logical extreme often times they are used as an excuse for lazy thinking. One example is stream processing where you're processing lots of messages per second and typically have some sort of originating request ID. Keeping a map of request ID's -> handlers gets very expensive if your goal is low latency (because you perform the map lookup on every operation).