develooper Front page | perl.perl5.porters | Postings from August 2021

Re: Robin Hood Hashing for the perl core

Thread Previous | Thread Next
Nicholas Clark
August 6, 2021 08:13
Re: Robin Hood Hashing for the perl core
Message ID:
On Tue, Aug 03, 2021 at 02:36:33PM +0000, Ed Avis wrote:

> If the hash implementation fixed an iteration order that didn't give away anything about the hash seed or how to engineer collisions, then it wouldn't need to be randomized.  Some hash implementations allow you to return the keys in the order they were originally inserted, without extra cost.  I think that would be a very desirable feature in any replacement hash implementation.  If the insertion order could be preserved with only a small constant penalty, that would speed up and simplify code where you currently use the much slower Tie::IxHash, and would also speed up code which currently needs 'sort keys', not because alphabetical ordering is particularly important, but just to get deterministic output.
> If your new hash implementation doesn't provide an obvious way to preserve the insertion order of keys, and so randomization will continue to be necessary, then I apologize for letting out one of the bees I have in my bonnet.

It's a good question.

No, it doesn't provide any way to preserve insertion order.

It's inherent in the Robin Hood algorithm that it controls the order within
the hash. It's actually *exploiting* the known order and ordering
constraints it adds to make searching terminate sooner.

So to maintain/remember insertion order would require storing more
information, which increases complexity, and likely size too.

(*likely* size, because by using a different data structure, you can
possibly make size savings elsewhere)

Nicholas Clark

Thread Previous | Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About