yes, they are O(n x log n)
in reply to Re^4: "Just use a hash": An overworked mantra?
in thread "Just use a hash": An overworked mantra?
how do the hashes work.
ok, hash is computed (some say these are O(log n) i do not know but this time I trust the links provided to me by davido) and then - based on computed hash - it could be hash hit or miss: either "luck" - (this is what usually happens) - this was different on all previous values.
or - otherwise - hash sum equality with earlier cases of that hash (rare in practice, but this is what is used on hash complexity attack)
in that latter case - insertion/search happens (based on exact operation), which is O(n)
otherwise this hunk of hv.c code is what for:
* The "hash seed" feature was added in Perl 5.8.1 to perturb the resu
* to avoid "algorithmic complexity attacks".
* If USE_HASH_SEED is defined, hash randomisation is done by default
* If USE_HASH_SEED_EXPLICIT is defined, hash randomisation is done
* only if the environment variable PERL_HASH_SEED is set.
* For maximal control, one can define PERL_HASH_SEED.
* (see also perl.c:perl_parse()).