On Tue, 16 Aug 2011 20:06:19 -0400, bearophile <[email protected]>
wrote:
Walter Bright:
It wasn't changed to simplify code, it was changed because it was
faster.
And uses much less space -- only one pointer per node vs. two.
Right.
I'd add that removing the requirement for opCmp is a reasonable request --
this opens up keys to significantly more data types (those which don't
have a defined order).
As for "attacks", if your code is subject to people sending it
specially crafted
input in the hopes of making it run slowly, you can make specially
crafted input
to make trees run slowly, too.
I think there are search trees like the Red-Black ones that guarantee a
O(n ln n) worst case. I am wrong?
Red black trees would be overkill here. The ideal hash only has one
element per bucket, and at most 2 or 3. This is why you expand the bucket
array even though you only have an element to bucket ratio of .75 or so.
Consider that for one or two (or even sometimes three) elements, a linked
list has identical topology, and it's insertion/removal algorithm is much
less complex.
-Steve
