About built-in AAs

[Steven Schveighoffer]

On Tue, 16 Aug 2011 20:06:19 -0400, bearophile <bearophileHUGS at lycos.com>  
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