AA with complex keytype?
Frits van Bommel
fvbommel at REMwOVExCAPSs.nl
Fri Feb 9 14:38:41 PST 2007
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)
More information about the Digitalmars-d
mailing list