AA with complex keytype?

[Frits van Bommel]

Manfred Nowak wrote:
> Frits van Bommel wrote
> 
>> Since hash functions can be user-defined, and not all users
>> are experts at hashing, you need to consider that use case.
> Currently implemented AA's need to have for a good runtime beahviour at 
> least one of 1) or 2)
> where:
> (1a) toHash implements a good distribution and
> (1b) opCmp==!opEquals or better

I haven't inspected the current AA implementation in detail. Are you 
sure that an opCmp that never returns "greater" (or, equivalently, never 
returns "less") will always work?
It may well be that the current implementation's binary trees degenerate 
into a linked list in that case, but it may also very well be that some 
elements become irretrievable.

> or
> (2a) toHash worse than described by (1a) and
> (2b) opCmp implements an ordering suitable for use in unbalanced binary 
> trees
> 
> There is no evidence, that users that are no experts at hashing will be 
> experts at implementing a suitable ordering, especially if the elements 
> do not have a natural ordering.

Orderings are easier to get right than hash functions, I think. Pretty 
much everybody knows what an ordering looks like, but hash functions 
need to have a good distribution which can be a rather complicated topic.

Of course, since you specified an ordering suitable for an _unbalanced_ 
binary tree that complicates things a bit. But I don't think good 
behavior in there depends much on the comparison function. It's more 
related to in which order you insert the elements. Which orders are good 
and bad _are_ of course dependent on the comparison...

(do current AAs use unbalanced trees? I have no idea, I just know they 
use _some_ form of trees)