Re:Myths about Hash Tables
by marshray on Monday October 01, 2012 @07:44PM
(#4599934)
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.
Re:Myths about Hash Tables
by aidenn0 on Tuesday October 02, 2012 @12:48AM
(#4600649)
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.
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.