3 ms·
I am surprised they get into quadratic algorithmic complexities. If they use the most efficient data structures (e.g., balanced binary trees) their algorithms f
by hristov 15y ago
I am surprised they get into quadratic algorithmic complexities. If they use the most efficient data structures (e.g., balanced binary trees) their algorithms for storage and retrieval should be no higher than O(log(n)). Thus if everything collides at the same entry in a hash table, you should still be able to do stores and reads for O(log(n)) time. And if that is the case, it would be very difficult to execute an attack that would cause significant disturbances even if the bad guys could beat the hash function.
- mikeash 15y agoI believe that using binary trees for hash chaining gives you better worst-case complexity but often worse performance in the common case. When your hashes are reasonably well spread out and the buckets are chained at most a couple of items deep, the overhead of maintaining a binary tree versus a linked list or using open addressing can be a considerable hit.
- tedunangst 15y agoI think you're assuming that python hash tables use linked list buckets. They don't. They use open addressing, and resize the table as necessary. There's no "data structure" that could be switched to a binary tree.
- hristov 15y agoYes, that is what I was assuming.