AA with complex keytype?

[Bill Baxter]

Frits van Bommel wrote:
> Stewart Gordon wrote:
>> Manfred Nowak Wrote:
>>
>>> Frits van Bommel wrote
>> <snip>
>>>> (do current AAs use unbalanced trees?  I have no idea, I just know 
>>>> they use _some_ form of trees)
>>> They are unbalanced.  Look at phobos/internal/aaA.d:278 and following 
>>> lines.
>>
>> Balancing the trees on the fly would be inefficient.  But rehash ought 
>> to balance them while it's at it.

> There are several well-known methods of efficiently keeping binary trees 
> (reasonably) balanced. Off the top of my head there are AVL trees and 
> red-black trees, but those definitely aren't the only ones.
> 
> For implementing a hash-table bucket this is probably not necessary, 
> though. There typically shouldn't be very much elements in a bucket.

So much for O(N lg N) performance in the case of a really bad hash 
function, though.  You'll get O(N) if you happen to insert your values 
such that their hashes are strictly increasing or strictly decreasing. 
In theory anyway. ;-)  I wouldn't be surprised though if in practice the 
simplicity of leaving out balancing outweighs the theoretical advantage 
of balanced trees in 95% of the cases.

Someone who has too much time on their hands should take a look at what 
the code for Python dicts and Lua tables do.  Both of those are reputed 
to be heavily tweaked for super-duper performance.

--bb