Nicholas Clark wrote:
My understanding is that this makes Perl 5 hash tables amortised O(1).
Hopefully someone else will answer the Perl 6 side properly.
My understanding is that the point of a hash table data structure was
that lookups are amortised O(1). However, doing it right - and certainly
doing it efficiently - depends on understanding various bits of math
that relate to the design of hash functions (basically, the desired
result being to minimize collisions). I had enough "fun" getting my head
around those as an undergrad, so a few years and a trip to the pub later
you've no chance of getting anything intelligent out of me on that
front. :-)
FWIW, Rakudo's (which actually just wrap Parrot's) are O(1) too, though
I suspect we've room to improve the algorithm a bit. See src/hash.c in
Parrot for more.
Thanks,
Jonathan
