About built-in AAs

[bearophile]

Walter Bright:

> > I think there are search trees like the Red-Black ones that guarantee a O(n ln n) worst case. I am wrong?
> 
> Just feed it more data.

If you feed it more data, even if all items pruce collision because they all hash to the same bucket, if you use Red-Black trees to handle the items in the same bucket you keep having a O(n ln n) behaviour, that's usually fast enough. With Python and the new D AAs you instead get a quadratic one. This quadratic behaviour gives troubles way before the physical RAM is exhausted.

Bye,
bearophile