[Python-Dev] Algoritmic Complexity Attack on Python
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?