4 ms·
> If you do a worst-case analysis, hash tables just degenerate to a single linked list (everything gets hashed to the same bucket), and you don't gain anything
by lxe 6y ago
> If you do a worst-case analysis, hash tables just degenerate to a single linked list (everything gets hashed to the same bucket), and you don't gain anything by using them. That's where you have 0(n) performance.
I don't gain anything from going outside because if you do a worst-case analysis I can get hit by lightning and die.
- pkolaczk 6y agoThe worst case for a hashtable degenerating to a linked list can be often exploited to form a DOS attack. It is enough that user controls the keys inserted to the hashtable and the hash function is not cryptographically secure (typically they are not for performance reasons). That's why it is much wiser to use a binary tree for resolving collisions. So in this case - the worst case analysis is useful.