[Python-Dev] Algoritmic Complexity Attack on Python (original) (raw)

Raymond Hettinger python@rcn.com
Thu, 29 May 2003 16:55:35 -0400

For instance, hash tables are usually thought of as being constant time operations, but with large numbers of collisions will degrade to a linked list and may lead to a 100-10,000 times performance degradation.

True enough. And it's not hard to create tons of keys that will collide (Uncle Tim even gives an example in the source for those who care to read). Going from O(1) to O(n) for each insertion would be a bit painful during the process of building up a large dictionary.

So, did your research show a prevalence of or even existence of online applications that allow someone to submit high volumes of meaningless keys to be saved in a hash table?

Raymond Hettinger