[Python-Dev] Algoritmic Complexity Attack on Python

[Raymond Hettinger]

>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