> 1. (Self-balancing binary trees). The idea here is that a balanced binary > tree has worst-case insertion time O(log N), while the linked list we > normally use has worst-case insertion time O(N). This means that the > worst-case execution time for N insertions into a hashtable goes from > O(N^2) to O(N log N), i.e. from catastrophic to "a few times slower than > usual". > > I don't think this solution is viable for PHP. Supporting binary trees next > to linked list collision resolution will make the hashtable implementation > *a lot* more complicated -- and it isn't exactly simple as is.
I have written self-balancing binary trees on multiple occasions. I know that we want to minimize complexity but if the complexity actually helps solve this issue I think it would be worth it. I assume you didn't create a proof of concept for this option – is that correct? I think fataling because of collisions is a poor solution to this problem because fataling in some cases may contribute to a successful DOS attack (I do not think Aerys is the only piece of software that would be vulnerable to this). I am sure PHP is not the only language that has experienced pain with HashDos – how have other languages handled it? -- PHP Internals - PHP Runtime Development Mailing List To unsubscribe, visit: http://www.php.net/unsub.php
