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
